AtCoder Beginner Contest 092

ぼちぼち出来た. Dはとりたかったがとれず.

A - Traveling Budget

AとB, CとDの大小比較をして小さい方を選ぶ.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int a, b, c, d;
  cin >> a >> b >> c >> d;

  cout << min(a, b) + min(c, d) << endl;
}

B - Chocolate

i人目の参加者は(D - 1) / A[i] + 1個チョコレートを食べる.
これを各A[i]ごとに計算して足していき, 最後にXを足す.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int n, d, x;
  cin >> n >> d >> x;
  int a[n];
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }

  int ch = 0;
  for(int i = 0; i < n; i++) {
    ch += (d - 1) / a[i] + 1;
  }
  ch += x;
  cout << ch << endl;
}

C - Traveling Plan

まず予定通り観光した場合の金額の総和を求める.
i番目の観光スポットを訪れなかった場合, 金額の総和は,
(予定通り観光した場合の金額) - (i-1番目からi番目に行く金額) - (i番目からi+1番目に行く金額) + (i-1番目からi+1番目に行く金額)
となる.
i = 1, Nの場合原点も考慮する.

#include <bits/stdc++.h>

using namespace std;

int abs(int x) {
  if(x < 0) {
    return (-1) * x;
  }
  else {
    return x;
  }
}

int main(void) {
  int n;
  cin >> n;
  int a[n];
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }

  long long sum = abs(a[0]);
  for(int i = 1; i < n; i++) {
    sum += abs(a[i] - a[i - 1]);
  }
  sum += abs(a[n - 1]);

  cout << sum - abs(a[0]) - abs(a[1] - a[0]) + abs(a[1]) << endl;
  for(int i = 1; i < n - 1; i++) {
    long long tmp = sum;
    tmp = tmp - abs(a[i] - a[i - 1]) - abs(a[i + 1] - a[i]) + abs(a[i + 1] - a[i - 1]);
    cout << tmp << endl;
  }
  cout << sum - abs(a[n - 1] - a[n - 2]) - abs(a[n - 1]) + abs(a[n - 2]) << endl;
}

D - Grid Components

本番では解けず. 解説PDFを読みながら解いた.
イデア勝負の問題だったので諦めずにもう少し時間をかければよかった.
解答見ながら実装してる時グリッドのサイズを出力し忘れて時間溶かした.
問題はちゃんと読もうね.
ソースのみ以下に記載.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int a, b;
  cin >> a >> b;

  string ans[100];
  for(int i = 0; i < 50; i++) {
    for(int j = 0; j < 100; j++) {
      ans[i] += '.';
      ans[i + 50] += '#';
    }
  }

  int count = 1;
  for(int i = 0; i < 49; i += 2) {
    int tmp = i % 2;
    for(int j = 0 + tmp; j < 100; j += 2) {
      if(b == count) {
	break;
      }
      ans[i][j] = '#';
      count++;
    }
  }

  count = 1;
  for(int i = 51; i < 100; i += 2) {
    int tmp = i % 2;
    for(int j = 0 + tmp; j < 100; j += 2) {
      if(a == count) {
	break;
      }
      ans[i][j] = '.';
      count++;
    }
  }

  cout << "100 100" << endl;
  
  for(int i = 0; i < 100; i++) {
    cout << ans[i] << endl;
  }
}

Educational Codeforces Round 39 (Div.2)

誤読で本番1問も解けなかった(完).

A - Partition

数列を左と右に分けて左をB, 右をCとした時の最大値だと勝手に思い込んでいたけど,
そうではなくて, ある数がBとCのどちらに属するかは自由に決めていいので,
単にプラスならB, マイナスならCに放り込めばいいだけだった.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int n;
  cin >> n;
  int a[n];
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }

  int sum = 0;
  for(int i = 0; i < n; i++) {
    if(a[i] < 0) {
      sum -= a[i];
    }
    else {
      sum += a[i];
    }
  }

  cout << sum << endl;
}

B - Weird Subtraction Process

問題文通り愚直に書いたらTLEした. 以下の提出を参考にした.

http://codeforces.com/contest/946/submission/35997312

引き算を%で余りとる計算に変えるとループが圧倒的に少なくなった. そりゃそうだ.
ビット演算をこんな風に使うの面白い.

#include <bits/stdc++.h>

using namespace std;

long long a, b;

int main(void) {
  cin >> a >> b;
  // ビット演算
  while(a && b) {
    if(a >= 2 * b) {
      a %= 2 * b;
    }
    else if(b >= 2 * a) {
      b %= 2 * a;
    }
    else {
      break;
    }
  }
  cout << a << " " << b << endl;
}

C - String Transformation

これもaからzまで連続している必要があると勘違いしていたけどそうではなかった.
a~zが連続している必要があるなら置き換えられない文字が出てきた場合にもう一度'a'から
探しなおす(インクリメントする変数を'a'にリセットする)操作が必要だけど,
そうではないのでその部分を削除した.

// Subsequenceは連続していなくてもよい
// abczzzzzzzefgh...でもよい
#include <bits/stdc++.h>

using namespace std;

int main(void) {
  string s;
  cin >> s;

  char c = 'a';
  for(int i = 0; i < s.length(); i++) {
    if(s[i] <= c) {
      s[i] = c;
      c++;
      if(c > 'z') {
	cout << s << endl;
	return 0;
      }
    }
  }
  cout << "-1" << endl;
}

誤読を防ごう. めんどくさがらずに毎回Google翻訳にかけよう.

AtCoder Grand Contest 021

目標: 300点を速解きする.
1WAしたので速くはないですね. B以降は着手してないです.

A - Digit Sum 2

i桁目を9にしてi+1桁目から1引く, 出来ないなら桁借りする.
これを繰り返す. 出来た数の各桁を足して答え.

#include <bits/stdc++.h>

using namespace std;

string n;

void diff(int i) {
  if(n[i] == '0') {
    n[i] = '9';
    diff(i - 1);
  }
  else {
    n[i]--;
  }
}

int main(void) {
  cin >> n;

  if(n.length() == 1) {
    cout << n << endl;
    return 0;
  }
  for(int i = n.length() - 1; i > 0; i--) {
    if(n[i] != '9') {
      n[i] = '9';
      diff(i - 1);
    }
  }

  int ans = 0;
  for(int i = 0; i < n.length(); i++) {
    ans += n[i] - '0';
  }

  cout << ans << endl;
}

Codeforces Round #465 (Div. 2)

A - Fafa and his Company

n - i人をi個のグループに均等に分けられるiの数を求めればよいので,
(n - i) % iが0ならカウントする.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int n;
  cin >> n;

  int count = 0;
  for(int i = 1; i <= n / 2; i++) {
    if((n - i) % i == 0) {
      count++;
    }
  }

  cout << count << endl;
}

B - Fafa and the Gates

国境上にいた回数ではなく, 国境をまたいだ回数を求めるので,
i回移動した状態とi - 2回移動した状態それぞれで,
x[i] - y[i]
x[i - 2] - y[i - 2]
を計算し, 符号が違う場合はカウントする.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int n;
  cin >> n;
  string s;
  cin >> s;

  int x[n], y[n];
  x[0] = 0;
  y[0] = 0;
  for(int i = 0; i < n; i++) {
    if(s[i] == 'U') {
      y[i + 1] = y[i] + 1;
      x[i + 1] = x[i];
    }
    if(s[i] == 'R') {
      x[i + 1] = x[i] + 1;
      y[i + 1] = y[i];
    }
  }

  int count = 0;
  for(int i = 3; i <= n; i += 2) {
    if((x[i] - y[i] < 0 && x[i - 2] - y[i - 2] > 0)
       || (x[i] - y[i] > 0 && x[i - 2] - y[i - 2] < 0)) {
      count++;
    }
  }

  cout << count << endl;
}

C - Fifa and Fafa

自力で解けず.
Wi-Fiの円の中心の座標の出し方がわからなかったけど,単にsin, cosと比を使えば出せますね.頑張りましょう.
Editorialにはコード例が無かったので以下の提出を解答代わりに読んだ.

http://codeforces.com/contest/935/submission/35484685

doubleの計算だから誤差を考慮しなければいけないと思ったけど
プロコンの実数計算はそんなに誤差気にしなくていいんですかね?
気に入った競プロerをお気に入り登録して提出をみれば答え合わせになってよいかもしれない.

Atcoder Beginner Contest 088

A - Infinite Coins

Nを500で割った余りがA以下ならば"Yes".

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int n, a;
  cin >> n >> a;

  int m = n % 500;
  if(m <= a) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

B - Card Game for Two

AliceとBobは大きいカードから順に交互に取っていくので, カードをソートして
交互に和をとればよい.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int n;
  cin >> n;
  vector <int> a;
  for(int i = 0; i < n; i++) {
    int x;
    cin >> x;
    a.push_back(x);
  }

  int Alice = 0, Bob = 0;
  sort(a.rbegin(), a.rend());
  for(int i = 0; i < n; i++) {
    if(i % 2 == 0) {
      Alice += a[i];
    }
    else {
      Bob += a[i];
    }
  }

  cout << Alice - Bob << endl;
}

C - Takahashi's Information

自力では解けなかった.
高橋君の情報が正しいなら
a[1] = 0
b[i] = c[1][i] - a[1]
a[i] = c[i][1] - b[1]
となるので, c[i][j] = a[i] + b[j]が成り立つかどうかを確かめればよい(らしい).

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int c[4][4];
  for(int i = 1; i <= 3; i++) {
    for(int j = 1; j <= 3; j++) {
      cin >> c[i][j];
    }
  }

  int a[4], b[4];
  a[1] = 0;
  for(int i = 1; i <= 3; i++) {
    b[i] = c[1][i] - a[1];
  }
  for(int i = 2; i <= 3; i++) {
    a[i] = c[i][1] - b[1];
  }

  for(int i = 1; i <= 3; i++) {
    for(int j = 1; j <= 3; j++) {
      if(c[i][j] != a[i] + b[j]) {
	cout << "No" << endl;
	return 0;
      }
    }
  }
  cout << "Yes" << endl;
}

D - Grid Repainting

2次元迷路の最短路の長さを求めて白いマスの数から引けばよい.
最短路の長さは幅優先探索(蟻本そのまま)で解ける.

#include <bits/stdc++.h>

using namespace std;

int h, w;
char maze[51][51];
int d[51][51];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void bfs() {
  queue< pair<int, int> > que;
  for(int i = 1; i <= h; i++) {
    for(int j = 1; j <= w; j++) {
      d[i][j] = INT_MAX;
    }
  }
  que.push(pair<int, int> (1, 1));
  d[1][1] = 0;

  while(que.size()) {
    pair <int, int> p = que.front();
    que.pop();
    if(p.first == h && p.second == w) {
      break;
    }
    for(int i = 0; i < 4; i++) {
      int nx = p.first + dx[i];
      int ny = p.second + dy[i];
      if(1 <= nx && nx <= h && 1 <= ny && ny <= w && maze[nx][ny] != '#' && d[nx][ny] == INT_MAX) {
	que.push(pair<int, int>(nx, ny));
	d[nx][ny] = d[p.first][p.second] + 1;
      }
    }
  }
  return;
}

int main(void) {
  cin >> h >> w;
  for(int i = 1; i <= h; i++) {
    for(int j = 1; j <= w; j++) {
      cin >> maze[i][j];
    }
  }

  int count = 0;
  for(int i = 1; i <= h; i++) {
    for(int j = 1; j <= w; j++) {
      if(maze[i][j] == '.') {
	count++;
      }
    }
  }

  bfs();
  int mn = d[h][w];
  if(mn == INT_MAX) {
    cout << "-1" << endl;
    return 0;
  }
  cout << count - (mn + 1) << endl;
}

Codeforces Round #464 (Div. 2)

休みのうちはいいけど大学始まってからはどれくらいのペースでできるのだろうか.

A - Love Triangle

配列の中身を添え字にするのを3回繰り返して元に戻れば"Yes".

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int n;
  cin >> n;
  int f[n + 1];
  for(int i = 1; i <= n; i++) {
    cin >> f[i];
  }

  for(int i = 1; i <= n; i++) {
    if(i == f[f[f[i]]]) {
      cout << "YES" << endl;
      return 0;
    }
  }

  cout << "NO" << endl;
}

B - Hamster Farm

余りが最小になる箱の種類を求めればよい.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  long long n;
  int k;
  cin >> n >> k;
  long long a[k + 1];
  for(int i = 1; i <= k; i++) {
    cin >> a[i];
  }

  long long min = n;
  int ans = 0;
  for(int i = 1; i <= k; i++) {
    if(min >= n % a[i]) {
      min = n % a[i];
      ans = i;
    }
  }
  cout << ans << " " << (long long)n / a[ans] << endl;
}

C - Convenient For Everybody

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int n;
  cin >> n;
  int a[n];
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }
  int s, f;
  cin >> s >> f;

  int mx = 0;
  int ans = 1;
  // 先頭のタイムゾーンがi時
  for(int i = 1; i <= n; i++) {
    int people = 0;
    // 全タイムゾーンの参加できる人数を求める
    for(int j = 0; j < n; j++) {
      int localstart = i + j;
      if(localstart > n) {
	localstart -= n;
      }
      int localfinish = localstart + 1;
      if(localfinish > n) {
        localfinish -= n;
      }
      // cout << "localstart: " << localstart << " " << "localfinish: " << localfinish << endl;
      if(s <=  localstart && localfinish <= f && localstart < localfinish) {
	people += a[j];
      }
    }
    // cout << "i: " << i << " " << "people: " << people << endl;
    if(mx < people) {
      mx = people;
      ans = i;
    }
  }

  cout << ans << endl;
}

最初は上記のような全探索を書いたがWAだしO(n^2).
テストケースを試すうちに区間で区切った人数を足せばよいことに気づいたけど時間切れ.
Editorialが出てないっぽい(2018/02/20現在)けどタグにbinary_searchとあるので想定解はO(nlogn)とか?
らてさんの提出を解答代わりに読んだ.

http://codeforces.com/contest/939/submission/35403238

f - sの幅で人数を足した時の最大の場合が答え.
n番目のタイムゾーンと1番目のタイムゾーンをまたいだ場合も考えることに注意(上はこれでWAしている).

Codeforces Round #462 (Div. 2)

今回は恥ずかしながら0完です.

A - Compatible Pair

両者のランタンから最大になりうる組み合わせをいくつか持ってきて比較, 最大になる
組み合わせに含まれるLittle Tommy側の要素をマスクしてもう一度比較, といった
感じでコンテスト中(とその後)に考えて書いたコードが以下.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int n, m;
  cin >> n >> m;
  vector<int> a, b;
  for(int i = 0; i < n; i++) {
    int x;
    cin >> x;
    a.push_back(x);
  }
  for(int i = 0; i < m; i++) {
    int x;
    cin >> x;
    b.push_back(x);
  }

  sort(a.begin(), a.end());
  sort(b.begin(), b.end());

  long long int l = b[0] * a[0];
  long long int r = b[m - 1] * a[n - 1];
  long long int s = b[0] * a[n - 1];
  long long int u = b[m - 1] * a[0];
  if(s < 0 && u < 0) {
    if(l > r) {
      long long int ll = b[0] * a[1];
      long long int rr = r;
      cout << max(ll, rr) << endl;
    }
    else if(l == r) {
      cout << l << endl; 
    }
    else {
      long long int ll = l;
      long long int rr = b[m - 1] * a[n - 2];
      cout << max(ll, rr) << endl;
    }
  }
  else {
    if(s > u) {
      long long int ss = b[0] * a[n - 2];
      long long int uu = u;
      cout << max(ss, uu) << endl;
    }
    else if(s == u) {
      cout << s << endl;
    }
    else {
      long long int ss = s;
      long long int uu = b[m - 1] * a[1];
      cout << max(ss, uu) << endl;
    }
  }
  return 0;
}

が, これはWAだった.
Editorialで2 <= n, m <= 50なので全探索でよいと知ってズッコけた.
入力のサイズはよく確認しよう.
以下, Editorial見ながら書いたコード.
Little Tommyのランタンa[i]をマスクした場合のランタンの積の最大値nowを求める.
iを動かした場合の最小のnowが答え.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int n, m;
  cin >> n >> m;
  int a[n], b[m];
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for(int i = 0; i < m; i++) {
    cin >> b[i];
  }

  long long res = LLONG_MAX;
  for(int i = 0; i < n; i++) {
    long long now = LLONG_MIN;
    for(int j = 0; j < n; j++) {
      if(j != i) {
	for(int k = 0; k < m; k++) {
	  now = max(now, (long long)a[j]*b[k]);
	}
      }
    }
    res = min(res, now);
  }
  cout << res << endl;
}

B - A Prosperous Lot

kが2以上なら"8"を出力してkを2減らす.
kが1なら"6"を出力してkを1減らす.
kが0なら終了.
kが36より大きい場合, 答えが10^18より大きくなるので"-1"を出力.
コンテスト中は10^18を18ケタと勘違いし(本当は19ケタ),
"-1"の条件をk > 34としてしまった.
あとkが1の場合の出力を"0"にしていたので入力が1だとWAになった.
問題文のOutputのpositiveが太字になってるの多分これのこと.

// 10^18は19ケタ

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int k;
  cin >> k;
  if(k > 36) {
    cout << "-1" << endl;
    return 0;
  }

  while(true) {
    if(k >= 2) {
      cout << "8";
      k -= 2;
    }
    else if(k == 1) {
      cout << "6";
      k -= 1;
    }
    else {
      break;
    }
  }
  cout << endl;
  return 0;
}