Codeforces Round 1103 (Div. 3) 参加レポート

Codeforces Round 1103 (Div. 3) に参加しました。 午前1時過ぎには寝たかったので、今回はコンテストの途中までの参加でしたが、結果としてA問題からC問題までの3問を解くことができました。

A問題 Games on the Train

どのタワーにも少なくとも1つのブロックを追加しなければならないため、最終的な高さは最低でも hmax+1h_{max} + 1 以上にする必要があります。

したがって、最小の高さ hminh_{min} を hmax+1h_{max} + 1 にするために必要なブロックの数が答えとなります。

B問題 Tatar TV Show

操作を行う際、以下の3つのパターンが考えられます。

  1. 00→1100 \to 11: 「1」の数が2つ増える。
  2. 11→0011 \to 00: 「1」の数が2つ減る。
  3. 01→1001 \to 10 または 10→0110 \to 01: 「1」の数は変わらない。

このことから、どの操作を行っても「1」の総数の偶奇（パリティ）は変化しないことがわかります。 つまり、最終的な「1」の総数は偶数でなければなりません。

ただし、この条件だけでは不十分です。 なぜなら、操作は特定の「位置」と「そこからちょうど kk 離れた位置」に対してのみ行えるからです。

言い換えると、i mod ki \bmod k のグループごとに「1」の総数が偶数であることが、必要十分条件となります。

C問題 Omsk Programmers

操作1よりも、操作2の方が強そうに感じました。

a,b≤109a, b \le 10^9 であり、109<23010^9 < 2^{30} です。そのため、各値は最大でも30回程度の割り算操作で0まで減らすことができます。

そこで、aa と bb が0になるまで繰り返し割って得られるすべての値を記録しておき、それらの組み合わせを全探索することで、両方の値を等しくするために必要な最小の操作回数を求めることができます。

D問題以降は解けませんでした。

普段は AtCoder で問題を解いているのですが、Codeforcesでは itertools クレートがデフォルトで使えないため、コンパイルエラーにかなり苦戦してしまいました。

楽しかったので、これからも時々参加しようと思います。

最後まで読んでいただきありがとうございました。