今日はタイトルのコンテストに参加しました。
結果は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]をすれば求まります。
強い人たちのツイートもはっておきます。
Dは冷静になるとどれかがsum/2 以上のものを引くだけでいいです(どれかがsum/2以上になるものをひくと自動的にどれかが0になるのは落ちるので)
ただしsumが偶数のときだけ(sum/2,sum/2,0)のケースを2回引いてるのでそれだけ気をつける— てんぷら (@tempura_cpp) April 20, 2019
D、とりあえず最大値が総和の半分以下が必要は知識であって、最大値を固定しちゃうと他がそれを超えない必要があってもつ情報が増える -> よく考えたら全部半分以下にすればいい -> 半分以上になるのはたかだか 1 色だからほうじょできるじゃん、みたいな考察をした
— capra🍊 (@gzlcp) April 20, 2019
感想
ようやく1000になりましたがABC早解きでレートあげてる感が否めないのではやくD問題を安定させられるようになりたいところです。
今回は余事象を考えてすっきりさせるという発想に至らなかったのが敗因。反省します。
現状400点は3割、500点は1割、600点は0割解けるという感じなのでD問題埋めをこれからも継続してやっていきたいです。
と言いながらこのペースでいくとあと数回でABCがunratedになってしまいそうなのが不安……
