AtCoder Beginner Contest 109
AtCoder Beginner Contest 109 (ABC109) の解説です。
AtCoder Beginner Contest 109 旧版
AtCoder Beginner Contest 109 beta版
解けた問題だけ解説をしていきますー
要項
AtCoder Beginner Contest 109
rated 1200
9/8(土) 21:00 ～ 22:40 (100分)
100-200-300-400 (4問)
ペナルティ: 5分
方針
全完
A - ABC333
まず、次の規則を思い出しましょう。
- 奇数×奇数=奇数
- 奇数×偶数=偶数
- 偶数×奇数=偶数
- 偶数×偶数=偶数
従って、が奇数であれば
を奇数にすることで奇数になり、それ以外の場合は必ず偶数になります。
B - Shiritori
条件が2つあるので、それぞれ別に考えてみましょう。
まず、先頭の文字が直前に発言した単語の末尾と一致するか判定します。
これは直前に発言した文字の末尾を記憶しておくことで、比較すれば判定できます。
次に、同じ単語を2度発言していないかチェックします。
これはsetのようなデータ構造を用いて、要素数と発言数が一致しているか比較すれば判定できます。
C - Skip
順番が関係ない時は、まずソートでもしておきましょう。
さて、この問題の移動法はよく見ると一つにまとめることができます。
- 整数
を用いて、
の地点に移動する
この移動によって目的地に着けるとき、これはと
との距離の差が
の倍数であったことに他なりません。
即ち、全てのに対して最大公約数を求め、その値を
にすればそれが最大となります。
D - Make Them Even
まず、偶数のコインが置かれているマスは基本的に無視できます。
問題となるのは、奇数枚のコインが置かれているマスからコインをどう移動させるかです。
ここで、まず隣同士に奇数枚のコインが置かれている場合は簡単ですが、隣同士で無い時はどうしましょう？
よく考えてみると、途中に偶数枚のコインが挟まれていても気にせずに動かすことができると分かります。
例えば1 2 2 1だと最初の3か所のコインを全部後ろ側3か所に移動させれば、0 2 2 2となるので解決します。
つまり、あとは同じマスを2度選択しないような移動方法を考案すれば良いです。
これは、例えばマスを次のようにナンバリングします。
1 2 3 4 8 7 6 5 9 ...
この規則上で、自分より若い番号にまだ動かしていない奇数のコインの場所を発見したら、1個ずつ数字を戻るように辿れば必ず同じマスを2度通らずにコインを動かせます。
計算量はなので十分間に合うでしょう。
結果
oooo 4完(1000点) 2:30-8:53-16:32(1WA)-68:52(1WA) / 78:52
517位
感想
規則性に気付けば楽な問題が多めでしたね。
こういう問題は発想力であると同時に典型力でもある(今回のCとD、どちらも似たような問題が過去に出題されている)ので量をこなした方が発想しやすいと思います。
