AtCoder Beginner Contest 100

ABC-の3完です. 緑到達, 初水色パフォーマンスなど嬉しい回だった.

A - Happy Birthday!

互い違いにケーキを取るとするとどちらも最大8個なので, どちらかが8個を超えていれば":(", それ以外は"Yay!".

#include <bits/stdc++.h>

using namespace std;

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

  if(a <= 8 && b <= 8) {
    cout << "Yay!" << endl;
  }
  else {
    cout << ":(" << endl;
  }
}

B - Ringo's Favorite Numbers

基本的にはn*(100^d)を出力すればよいが, n==100の場合だけ100^(d+1)で割り切れる数となってしまうので注意が必要(1WA).

#include <bits/stdc++.h>

using namespace std;

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

  int tmp;
  if(d == 0) {
    tmp = 1;
  }
  else if(d == 1){
    tmp = 100;
  }
  else {
    tmp = 10000;
  }

  if(n == 100) {
    n++;
  }

  cout << tmp * n << endl;
}

C - *3 or /2

3倍して大きくなる分にはいつでも整数なのでこちらは気にせず, 2で割る操作のみを考えればよい.1つの要素だけ2倍して残りの要素を3倍すると操作回数は最大になる. 配列の要素それぞれを2で割って回数を数えて出力する.

#include <bits/stdc++.h>

using namespace std;

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

  int count = 0;
  for(int i = 0; i < n; i++) {
    while(a[i] % 2 == 0) {
      a[i] /= 2;
      count++;
    }
  }

  cout << count << endl;
}

D - Patisserie ABC

なんにもわからなかった. editorial見て解いただけ.

長い時間書きかけで放っておいたせいでDのときどんなこと考えたか忘れた.

AtCoder Beginner Contest 097

ABc-で2完+部分点でした. Cが厳しかった.

A - Colorful Transceivers

CとAの距離がd以下ならばAとCは直接会話できるので"Yes".
AとBの距離がd以下かつCとAの距離がd以下ならばAとCは間接的に会話できるのでこれも"Yes".
それ以外は"No".

#include <bits/stdc++.h>

using namespace std;

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

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

  if(abs(c - a) <= d) {
    cout << "Yes" << endl;
  }
  else if(abs(b - a) <= d && abs(c - b) <= d) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

B - Exponential

2以上X未満の数をべき乗して作れる1000未満の数を全探索して最大のものを出力する.
何故かエラトステネスのふるいが貼っつけられてますが別にいらない.

#include <bits/stdc++.h>
#define MAX_N 2000

using namespace std;

int prime[MAX_N];  // i番目の素数
bool is_prime[MAX_N + 1];  // is_prime[i]がtrueならiは素数

// n以下の素数の数を返す
int sieve(int n) {
  int p = 0;
  for(int i = 0; i <= n; i++) {
    is_prime[i] = true;
  }
  is_prime[0] = is_prime[1] = false;
  for(int i = 2; i <= n; i++) {
    if (is_prime[i]) {
      prime[p++] = i;
      for(int j = 2 * i; j <= n; j += i) {
	is_prime[j] = false;
      }
    }
  }
  return p;
}

int main(void) {
  int n = sieve(1001);
  int x;
  cin >> x;

  int mx = 1;
  for(int i = 2; i < x; i++) {
    int p = 0;
    int tmp = 1;
    while(tmp <= x) {
      tmp *= i;
      p++;
    }
    tmp /= i;
    p--;
    if(mx < tmp && 1 < p) {
      //      cout << "i: " << i << endl;
      mx = tmp;
    }
  }
  cout << mx << endl;
}

C - K-th Substring

コンテスト中は部分点のみ解いた.
部分文字列をsetに全部放り込んでそこからK番目に小さいものを出力する.

#include <bits/stdc++.h>

using namespace std;

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

  set <string> t;
  for(int i = 1; i <= s.length(); i++) {
    for(int j = 0; j < s.length() - i + 1; j++) {
      string u;
      for(int k = 0; k < i; k++) {
	u.push_back(s[j + k]);
      }
      t.insert(u);
    }
  }
  long long count = 0;
  for(auto i: t) {
    count++;
    if(count == k) {
      cout << i << endl;
      return 0;
    }
  }
}

よく見たら入力のkとfor文の添字のkかぶってるじゃん. よく部分点取れたな.

editorialによると答えの文字列の長さは高々Kとなる.
よってsetに入れるsubstringは長さK以下でO(NK)個.
これは思いつきたかったな. string.substr(i, j)の存在を知れたのは勉強になった.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  string S;
  int K;
  cin >> S >> K;

  set <string> t;
  for(int i = 1; i <= K; i++) {
    for(int j = 0; j + i - 1 < S.length(); j++) {
      string u = S.substr(j, i);
      t.insert(u);
    }
  }
  long long count = 0;
  for(auto i: t) {
    count++;
    if(count == K) {
      cout << i << endl;
      return 0;
    }
  }
}

Educational Codeforces Round 43 (Div.2)

ABC---でこどふぉ初3完です. うれしいね.

A - Minimum Binary Number

1ケタの場合はそのまま出力.
2ケタ以上の場合, '1'はすべて左に寄せて消せば1個になる. 最終的には "1000" のように
最上位ケタに'1'が1つ, 残りは'0'となる.
よって入力の'0'の数を数えて, '1'を出力した後に数えた分'0'を出力すればよい.

#include <bits/stdc++.h>

using namespace std;

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

  if(n == 1 && s[0] == '0') {
    cout << "0" << endl;
    return 0;
  }

  long long count1 = 0, count0 = 0;
  for(int i = 0; i < n; i++) {
    if(s[i] == '1') {
      count1++;
    }
    else {
      count0++;
    }
  }
  string ans;
  ans.push_back('1');
  for(int i = 0; i < count0; i++) {
    ans.push_back('0');
  }
  cout << ans << endl;
}

B - Lara Croft and the New Game

(1, 1)から(n, 1)に降りたあと残りを蛇行しながら上に昇る.
移動コマ数kがnより小さければ最終地点は(k + 1, 1).
そうでない場合, 蛇行した分を計算する.
昇った行数はk / (m - 1)行となる. 残りの歩数は最終地点にたどり着くまでに昇った行数が奇数なら右から, 偶数なら左から数える.
コンテスト中はなぜか一番下の行を特別扱いしていたけど, そうする必要はない. editorialは一番下の行を特別扱いしていない.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  long long n, m, k;
  cin >> n >> m >> k;

  if(k <= n - 1) {
    cout << k + 1 << " 1" << endl;
    return 0;
  }
  k -= n - 1;
  if(k <= m - 1) {
    cout << n << " " << k + 1 << endl;
    return 0;
  }
  k -= m - 1;
  long long r = k / (m - 1);
  long long c = k % (m - 1);

  if(c == 0) {
    if(r % 2 == 0) {
      cout << n - r << " " << m << endl;
    }
    else {
      cout << n - r << " " << "2" << endl;
    }
  }
  else {
    if(r % 2 == 0) {
      cout << n - r - 1 << " " << m - c + 1 << endl;
    }
    else {
      cout << n - r - 1 << " " << 2 + c - 1 << endl;
    }
  }
}

C - Nested Segments

各[li, ri]に対してtuple配列を作って(li, ri, i)で保存する.
このtuple配列をsortすると第1要素lの昇順に並ぶ.
この配列の隣り合った2つの要素であるj番目とj+1番目を比較する.
このとき考えられるのは
(lj < l(j+1), lj == l(j+1)) * (rj < r(j+1), rj == r(j+1), rj > r(j+1))の6通り.
lj < l(j+1) かつ rj < r(j+1)の場合はjをインクリメントして次の比較をする.
そうでない場合はどちらかがもう片方を包含?(lie within)しているので答えとして出力. 答えにはtupleの3番目の要素を使う.
包含関係が1つでもあればそれを出力すればいいので全部調べなくてもよい. 隣り合っていない要素(例:j番目とj+k番目)の包含関係は見逃すけどその場合は別の包含関係(j+1番目とj+k番目とか)が成り立つので問題ない.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  long long n;
  cin >> n;
  vector <tuple <long long, long long, long long>> lr;
  for(int i = 0; i < n; i++) {
    long long x, y;
    cin >> x >> y;
    lr.push_back(tuple <long long, long long, long long> (x, y, i + 1));
  }

  //  cout << "-------------------" << endl;
  sort(lr.begin(), lr.end());
  //  for(int i = 0; i < n; i++) {
  //    cout << get<0>(lr[i]) << " " << get<1>(lr[i]) << " " << get<2>(lr[i]) << endl;
  //  }

  for(int i = 0; i < n - 1; i++) {
    if(get<0>(lr[i]) == get<0>(lr[i + 1])) {
      if(get<1>(lr[i]) <= get<1>(lr[i + 1])) {
	cout << get<2>(lr[i]) << " " << get<2>(lr[i + 1]) << endl;
      }
      else {
	cout << get<2>(lr[i + 1]) << " " << get<2>(lr[i]) << endl;
      }
      return 0;
    }
    else {
      if(get<1>(lr[i]) >= get<1>(lr[i + 1])) {
	cout << get<2>(lr[i + 1]) << " " << get<2>(lr[i]) << endl;
	return 0;
      }
    }
  }

  cout << "-1 -1" << endl;
}

Dはまた今度.

AtCoder Grand Contest 023

0完太陽でした. 悲しいね.

A - Zero-Sum Ranges

以下の提出と公式editorialを参考に解きなおした.
https://beta.atcoder.jp/contests/agc023/submissions/2426038

editorialの解説は読んだらわかったけどなんでこんなコードになるのかしばらくわからなかった.
combination(nCk)を使わなくてもretにmp[sum]の値を逐次足していけば同様の計算になるってことだと思う(自信なし).

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int n;
  cin >> n;
  map <long long, int> mp;
  long long sum = 0;
  mp[0]++;

  long long ret = 0;
  for(int i = 0; i < n; i++) {
    //    cout << "i: " << i << endl;
    //    cout << "sum: " << sum << endl;
    //    cout << "ret: " << ret << endl;
    int x;
    cin >> x;
    //    cout << "a[" << i << "]: " << x << endl;
    //    cout << "-------------------------" << endl;
    sum += x;
    ret += mp[sum];
    mp[sum]++;
  }

  cout << ret << endl;
}

AtCoder Beginner Contest 093

ABC-の3完でした. D解説読んでもよくわからないので死.
出たコンテストについては何かしら書こうと思ってはいるけど蓄積している.
ABC094とGCJRound1Aも早めに消化したい.

A - abc of ABC

'a', 'b', 'c'が文中に含まれているかどうか確認する.
これ単純にソートして一致するか見ればラクじゃん.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  string s;
  cin >> s;
  bool a = false, b = false, c = false;
  for(int i = 0; i < 3; i++) {
    if(s[i] == 'a') {
      a = true;
    }
    else if(s[i] == 'b') {
      b = true;
    }
    else if(s[i] == 'c') {
      c = true;
    }
  }
  if(a && b && c) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

B - Small and Large Integers

単純に端からk個出力すればよい.
被りが無いようにmapを使っているけどkをb-a+1以下にしているのでその必要はないはず.

#include <bits/stdc++.h>

using namespace std;

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

  map<int, bool> m;

  if(k > b - a + 1) {
    k = b - a + 1;
  }
  for(int i = 0; i < k; i++) {
    m[a + i] = true;
    cout << a + i << endl;
  }
  for(int i = k - 1; i >= 0; i--) {
    if(!m[b - i]) {
      cout << b - i << endl;
    }
  }
}

C - Same Integers

最小値に2を加える操作を最大値と最小値の差が1になるまで繰り返し, 操作回数をカウントしておく.
最大値と最小値の差が1のとき,

1. 最小値が2つ, 最大値が1つ
2. 最小値が1つ, 最大値が2つ

の2通りになる. 最小値が2つの場合は2つの数字に1を1回加えて終了なので操作回数は1ふえる.
最小値が1つの場合は最小値に2を1回加える → 最小値が2つになるので2つの数字に1を1回加える,
とすると終了なので操作回数は2増える.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  vector <int> a(3);
  cin >> a[0] >> a[1] >> a[2];

  sort(a.begin(), a.end()); 
  int mx = a[2];
  int mn = a[0];
  int count = 0;
  while(mx - mn > 1) {
    int diff = mx - mn;
    count += diff / 2;
    // cout << "count: " << count << endl; 
    a[0] += diff / 2 * 2;
    // cout << "a[0]: " << a[0] << endl;
    sort(a.begin(), a.end());
    mx = a[2];
    mn = a[0];
  }
  if(a[2] - a[1] == 1) {
    count++;
  }
  else if(a[2] - a[1] == 0 && a[1] - a[0] == 1) {
    count += 2;
  }
  cout << count << endl;
}

Google Code Jam Qualification Round 2018

AB--のLarge2完です. あまり知識ゲーではなかったのでなんとかqual突破できた.
あまり書くこと無い気がする.

A - Saving The Universe Again

一番ダメージが小さい場合は'S'がすべて左端に寄っている場合であるから
'S'の数がシールドの耐久値より多ければ"IMPOSSIBLE".
そうでない場合は,

1. 今の文字列のダメージを計算.
2. 耐えられないなら文字列の一番後ろの"CS"を"SC"にして1に戻る.
3. 耐えられるなら出力して終了.

最近はデバッグ用の出力を消さずにコメントアウトで残してます.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int t;
  cin >> t;
  int d[t];
  string p[t];
  for(int i = 0; i < t; i++) {
    cin >> d[i] >> p[i];
    // cout << endl;
    // cout << "d[" << i << "]: " << d[i] << endl;
    // cout << "p[" << i << "]: " << p[i] << endl;
  }

  
  for(int i = 0; i < t; i++) {
    int numberofS = 0;
    for(int j = 0; j < p[i].length(); j++) {
      if(p[i][j] == 'S') {
	numberofS++;
      }
    }
    if(numberofS > d[i]) {
      cout << "Case #" << i + 1 << ": IMPOSSIBLE" << endl;
      continue;
    }
    int change = 0;
    while(true) {
      int damage = 0;
      int beam = 1;
      for(int j = 0; j < p[i].length(); j++) {
	if(p[i][j] == 'C') {
	  beam *= 2;
	}
	else if(p[i][j] == 'S'){
	  damage += beam;
	}
      }
      // cout << "damage: " << damage << endl;
      if(damage <= d[i]) {
	break;
      }

      int tmp = p[i].rfind("CS");
      // cout << tmp << endl;
      // cout << tmp + 1 << endl;
      p[i][tmp] = 'S';
      p[i][tmp + 1] = 'C';
      // cout << "p[" << i << "]: " << p[i] << endl;
      change++;
    }
    cout << "Case #" << i + 1 << ": " << change << endl;
  }
}

B - Trouble Sort

TroubleSortはインデックスが奇数番目同士, 偶数番目同士を入れ替える.
奇数番目と偶数番目が入れ替わることはない. よって入力配列を奇数番目と
偶数番目に分けてソートし, 最後に交互に1列に並べてソートできているか
どうかを確かめればよい.

#include <bits/stdc++.h>

using namespace std;

int n;
int v[1000000];

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

  vector <string> answer(t);
  for(int i = 0; i < t; i++) {
    cin >> n;
    vector <int> odd, even;
    for(int j = 0; j < n; j++) {
      cin >> v[j];
      if(j % 2 == 0) {
	even.push_back(v[j]);
      }
      else {
	odd.push_back(v[j]);
      }
    }
    sort(even.begin(), even.end());
    sort(odd.begin(), odd.end());
    vector <int> w;
    for(int j = 0; j < n / 2 + 1; j++) {
      if(j < even.size()) {
	w.push_back(even[j]);
      }
      if(j < odd.size()) {
	w.push_back(odd[j]);
      }
    }
    bool nondec = true;
    int index;
    for(int j = 1; j < n; j++) {
      if(w[j] < w[j - 1]) {
	// cout << "v[" << j << "]: " << v[j] << endl;
	// cout << "v[" << j - 1 << "]: " << v[j - 1] << endl;
	nondec = false;
	index = j - 1;
	break;
      }
    }
    if(nondec) {
      answer[i] += "Case #" + to_string(i + 1) + ": OK";
    }
    else {
      answer[i] += "Case #" + to_string(i + 1) + ": " + to_string(index);
    }
  }

  for(int i = 0; i < t; i++) {
    cout << answer[i] << endl;
  }
}

ABLarge解けてるから大丈夫だろうと思いABCに移動, ABC終わってからやる気力は無く寝てしまった.

Educational Codeforces Round 41 (Div.2)

今回は1完です. Bのケアレスミスに気づきたかったね.

A - Tetris

各列に積み上がっていくブロックの数のうち最小のものを出力する.
つまり一番低い列の高さが答え.

#include <bits/stdc++.h>

using namespace std;

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

  int r[n];
  for(int i = 0; i < n; i++) {
    r[i] = 0;
  }
  for(int i = 0; i < m; i++) {
    int x;
    cin >> x;
    r[x - 1]++;
  }

  int mn = 2000000000;
  for(int i = 0; i < n; i++) {
    mn = min(mn, r[i]);
  }

  cout << mn << endl;
}

B - Lecture Sleep

t[i](1 <= i <= n)が1であるときのa[i]の値の総和を求めこれをbaseとする.
配列aから連続するk個の要素を取り出し, その中でインデックスが同じかつ配列tの要素が0である
配列aの要素の総和addを求める.
例えばk = 3で, 指定したインデックスの範囲がi = 2, 3, 4となるとき配列aと配列tは,
i 2 3 4
t 1 0 0
a 4 8 7
となる. このときadd = a[3] + a[4] = 15となる.
addの値を可能な連続するk個の範囲すべてで計算してその最大値とbaseを足したものが答え.
これを愚直に書くとO(n * k)になるが連続する大きさkの範囲から外れた要素をaddから引いて
大きさkの範囲に新たに加わった要素をaddに足すとO(n)でできる.
この記事の最初にケアレスミスしたって書いたけどどこをケアレスミスしたか忘れた. 時間空けすぎた.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int n, k;
  cin >> n >> k;
  int a[n + 1];
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
    // cout << "a[" << i << "]: " << a[i] << endl;
  }
  int t[n + 1];
  for(int i = 1; i <= n; i++) {
    cin >> t[i];
  }

  long long mx = 0;
  for(int i = 1; i <= n; i++) {
    if(t[i] == 1) {
      mx += a[i];
    }
  }

  long long base = mx;
  for(int i = 1; i <= k; i++) {
    if(t[i] == 0) {
      base += a[i];
    }
  }
  mx = max(mx, base);
  // cout << "base: " << base << endl;
  for(int i = 2; i <= n - k + 1; i++) {
    if(t[i - 1] == 0) {
      base -= a[i - 1];
    }
    if(t[i + k - 1] == 0) {
      base += a[i + k - 1];
    }
    mx = max(mx, base);
    // cout << base << endl;
  }

  cout << mx << endl;
}

C - Chessboard

自力で出来なかったのでEditorial見ながら解いた.
チェス盤は左下の角が必ず黒ということを知らなかったので倍のパターン調べる必要があると思ってしまった.
色塗り後のピースは角が黒のパターンのピース2つと角が白のパターンのピース2つになるはずなので,
まず各ピースが角が黒のパターンのピースにどれくらい合致しているか
(角が黒のパターンのピースとして使うとしたら塗りなおさなくてよいのは何箇所か)を調べる.
次にピースを4!通りに並べ替え, 各並び順に対応する塗り直しの回数を求め, その最小値を出力する.

以下, Editorialのほぼコピペ.

#include <bits/stdc++.h>

using namespace std;

const int N = 109;

int n;
string a[4][N];

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

  // 角が黒のパターンに何枚合致しているか
  vector <int> v;
  for(int k = 0; k < 4; k++) {
    int sum = 0;
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
	if((i + j) % 2 != a[k][i][j]) {
	  sum++;
	}
      }
    }
    v.push_back(sum);
    // cout << "a[" << k << "]: " << sum << endl;
  }

  // 4!通り並び替えて一番修正が少ないものを選ぶ
  int res = int(1e9);
  vector <int> perm;
  for(int k = 0; k < 4; k++) {
    perm.push_back(k);
  }
  while(next_permutation(perm.begin(), perm.end())) {
    int sum = 0;
    for(int k = 0; k < 4; k++) {
      int id = perm[k];
      if(k & 1) {
	sum += v[id];
      }
      else {
	sum += n * n - v[id];
      }
    }
    res = min(res, sum);
  }
  cout << res << endl;
}