A. Sum of Odd Integers

k 個の互いに異なる正の奇数を足し合わせて n にできるかを判定する問題です。YES である条件は、n と k のパリティが等しいことと、奇数を小さい方から k 個足し合わせた数、つまり k(k+1) - k が n 以下であること、です。

B. Princesses and Princes

がっつり問題文に絵が入っててびっくりしました。言われた通りに貪欲にマッチングしていって、完全にマッチングされれば"OPTIMAL"、王子と姫が余っていたら"IMPROVE"です。"IMPROVE" の場合は、余っている王子と姫を一人づつ選んでマッチングさせればいいです。

C. Game with Chips

ギャグでした。全てのチップが全てのマスを通るような操作ができたら何も考えることないな〜って思ってたら、できたので何も考えることがなかったです。とりあえず全てのチップを左上に集めて、全てのマスを通るように動かせばいいです。うなぎのように。範囲外に動くことはないからといって雑に操作すると、2nm 以上になってしまうことがあって落ちました。no more than 2nm action は 2nm action もアウトなんですね。

D. Infinite Path

こういうのはサイクルに注目するのが良いんですよね、Swapsを思い出しました。順列 {p} を i -> p[i] の有向辺を持つ n 頂点のグラフと見なし、サイクルに分割します。あるサイクルに注目してみます。サイクルのサイズを m とすると、そのサイクルに含まれる任意の頂点について、\( p ^ m [i] = i \) となります。このとき、明らかに頂点 i から始まる path は infinite path を形成します。そのため、サイクル分解した後のサイクルのサイズの最小値が答えの上限になります。これより小さくなる場合を考えます。サイクル分解した後のサイクルのサイズを再び m とおき、d を m の約数として、\( p ^ d \) を考えてみると、サイクル内の頂点 i から始まる path は \( i, p ^ d [i], p ^ d [ p ^ d [i]] ... p ^ m [i] = i \) となることがわかります。この path に出てきた全ての頂点 j で c[j] が等しければ d も答えの候補となります。あとはこの d を全探索すればできます。整数 N の約数の個数が \( \sqrt{N} \) 程度なので、計算量は\( O(N\sqrt{N}) \) 程度のはずです、多分。通ったので大丈夫だったのだと思います。

E. Count The Blocks

D を通して残り 15 分でしたが、1000 人以上に通されていたので、いけると思ったのですが、間に合いませんでした。焦りすぎました。問題を言い換えると、要素が 0~9、長さが N の整数列を全パターン考えた時に、同じ数字がちょうど k 連続するような場所がいくつあるか？を\( 1 \le k \le N \) 全てについて数えよ、という問題になります。同じ数字がちょうど k 連続するような部分では、k 個同じ要素が並び、その両端には別の要素が並んでいるはずです。例えば、長さ N の整数列のうち、前から i 番目から i + k - 1 番目までが、同じ要素で i - 1 番目とi + k 番目がそれとは別の要素であるような整数列の総数は、\( 10 \times 9 \times 9 \times 10 ^ {N - (k + 2)} \) 通りになります。全ての i \( ( 1 \le i \le n - k + 1 ) \) についてこれを足し合わせればいいですが、i = 1, i = n - k + 1 のときは、端が片方しかないことに気をつけて丁寧にやりましょう。反省。

感想

C のギャグに気づくのが早くてよかったのと、難しいっぽい D が解けてうれしかったです。E もしっかり通したかったですが。

現代の量子力学

主に精進の様子を記録する日記帳です

Educational Codeforces Round 84 (Rated for Div. 2) A~E

A. Sum of Odd Integers

B. Princesses and Princes

C. Game with Chips

D. Infinite Path

E. Count The Blocks

感想