競技プログラミング

AtCoder Tenka1 Programmer Beginner Contest 2019

今日はタイトルのコンテストに参加しました。

結果はA,B,Cは解けたもののD問題は解けませんでした。600点の壁は高かった……

しかし強い人が同時開催のレギュラーコンテストに流れていたため7位でした。パフォ1600が出て994->1089となりました。

では感想戦。

問題

コード

A – On the Way

考えたこと

A < C < B か B < C < A なら途中でCを通ることになります。

解答

そのままです。

B – *e**** ********e* *e****e* ****e**

考えたこと

k–して素直にやれば良さそうです。

解答

そのままです。

C – Stones

考えたこと

一瞬戸惑いましたが左側がずっと白で右側がずっと黒なら良いことがわかります。境界をずらしていってO(N)で解きたいので境界を決めたときの操作回数の計算はO(1)でしないといけません。つまり前処理としてある地点までの黒の数(あるいは白の数)を保持しておけばいいことになります。

解答

解説のまんまでした。

D – Three Colors

考えたこと

600点だからしっかり腰据えてやらないとなと思いました。

たぶん三角形の辺の長さがわかっていることを活用するんだろうなあと思い、最長辺を決めたら残り二辺の長さの合計が決まるのでその個数を数えていく感じかな、でも残り二辺が最長辺の長さを超えたらだめやなと思いぐちゃぐちゃとコードを書きましたがバグらせてしまい撃沈。

解答

辺の長さの合計Sがわかっているのでどれかの辺がS/2を超えた時点で三角形は成り立たないことに着目します(ここを最長辺はS/2未満と考えたのがよくなかった)。

全体からどれかの辺がS/2以上である三角形の個数を引けばそれが答えになります。S/2を超えるのはたかだか1色なのでこれを赤色とすると、これはDPで前からt個を塗り分けた時の赤色の和(r)の場合の数をDP[t][r]をすれば求まります。

強い人たちのツイートもはっておきます。

感想

ようやく1000になりましたがABC早解きでレートあげてる感が否めないのではやくD問題を安定させられるようになりたいところです。

今回は余事象を考えてすっきりさせるという発想に至らなかったのが敗因。反省します。

現状400点は3割、500点は1割、600点は0割解けるという感じなのでD問題埋めをこれからも継続してやっていきたいです。

と言いながらこのペースでいくとあと数回でABCがunratedになってしまいそうなのが不安……