【競プロ精進日記】Educational Codeforces Round 84 (Rated for Div. 2)

2020.03.24
競プロ

1. はじめに
2. A
3. B
4. C
5. D
6. E
7. F
8. G

はじめに

当ブログは問題の解説がメインではなく、筆者の解法やアイデアの保存がメインです。
したがって、読者の期待に沿えないことがあると思いますがご了承ください。

A

Sum of Odd Integers
一生英語が読めない。
同じ数を何度でも使えると勘違いして終わり。
nが偶、kが奇のときNO（奇数を奇数回足すと奇数になるから）。
nが奇、kが偶のときNO（奇数を偶数回足すと偶数になるから）。
よってnとkの偶奇が同じ時だけ調べます。
まず、最小の奇数の和でもnを越えてしまうことがあるのでそれを調べます。
最小の奇数の和は1,3,5,…の項がk個のときでこの和は\(k^2\)になります。
したがって、\(n \lt k^2\)のときもNOになります。
私はこの時点で提出してACしちゃったんですが、以上のことが満たせばk個の奇数の和がnになる奇数が存在することがいえるのかあまりぱっとしません。
終了後の自分なりの解釈ですが、和を差に考えて\(n\)から奇数を引いていくと残りの数の偶奇は入れ替わります（偶-奇=奇、奇-奇=偶）。
すると、\((n,k)\rightarrow(n-a_1=n_1,k-1)\rightarrow(n_1-a_2=n_2,k-2)\rightarrow\ldots\rightarrow(n_x,1)\)となります。
\(n\)と\(k\)の偶奇が同じならば、奇数を引くたびに両方偶奇が入れ替わるので最終的な\((n_x,1)\)で\(n_x\)が奇数となり、奇数列\(a_i\)が存在するということだと思います。
これがA問題なのか…
https://codeforces.com/contest/1327/submission/74080309

B

Princesses and Princes
一生英語が読めない。
ちょっと何言ってるかわからないですが、やるだけですね。指示に従いシミュレーションするだけです。
https://codeforces.com/contest/1327/submission/74092693

C

Game with Chips
一生英語が読めない。
完全に勘違いしていました。
最適な操作を出力するのかと思いきや、2nm以下の操作ならなんでもよかったんですね。
完全にやらかしました。激冷えです。
2nm以下でいいならチップを1か所に集めてボードを巡回するだけです。
左上にチップを集めるとすると上方向にn-1回、左方向にm-1回、左上以外の全マスnm-1マスを巡回するので合計n-1+m-1+nm-1<2nmとなり条件を満たす操作が存在します。したがって、この問題を解くうえで必要なのはnとmのみで他は一切必要ありません。それにしても問題が悪いのか、私の勘違いが悪いのか悔しいですね。最適な操作だと思ってターンと座標を持ってDPとかA*とか考えましたが無意味でした。はたしてEducationalなんですかねー。
https://codeforces.com/contest/1327/submission/74129963