- やった回: ABC303
- 成績: ABCD4完 / 2ペナ(未AC3ペナ) / 66:46(ペナ込み)
- 推定パフォーマンス: 1002
成績だけ見ると最近に比べたらだいぶ上々の結果なんだけど、E問題がもうちょっとのところで時間切れ。解説をさっと読んだあと15分後くらいに解けました。実装ミスに気付けずずっとデータ量削減してたのがくやしい。
A問題: ABC303-A Similar String
素直に「s[i]とt[i]が同じ文字か」「s[i]とt[i]がどちらも1かlのどちらかか」「s[i]とt[i]がどちらも0かoのどちらかか」を先頭から確認していって1個でもダメならその場でNoを出力して終わり、最後まで検証成功したらYesを出力する。
文字列はcharsしなくてもs[i]で参照できるの忘れがち。
B問題: ABC303-B Discord
N*Nの配列に隣になったかどうかをひたすらフラグ管理しておき、あとから全探索して隣り合ってないペアをカウントしていく。
C問題: ABC303-C Dash
冒頭から素直にシミュレーションしていく。アイテムの座標管理をHashのたぐいでやるのがポイントっぽい。
Nのサイズを考えても問題ないだろうとは思いつつ、やっぱりC問題以上で素朴なシミュレーションを投げるのはドキドキする。
D問題: ABC303-D Shift vs. CapsLock
DはDPのD～♪(ドレミの歌のメロディでどうぞ)
文字数*状態4つの二次元DP。「入力前のCapsLockの状態」と「今回のCapsLockの状態」でそれぞれON/OFFがあって状態4つ。こういうのは手を動かして表を書くのが一番。
何でDPするかを決めるのがむずいよねーと常々思っている中でちゃんと答えられたのはけっこううれしい。
…んですが、方針も実装もほぼ合ってたのにCapsLockの初期値にサンプル1の値を固定で与えて1WA、その後デバッグコードの消し忘れでもう1WAという大変しょうもないペナルティを重ねたのちのAC。
E問題: ABC303-E A Gift From the Stars
(upsolveコード) atcoder.jp
最初方針を出せずに図をゴリゴリと書いていて、「そういえば木と言えばノードを二色に塗り分けるパターン多いよね？」と色を塗ってみたら連結先が1個しかないノードって必ずその連結相手が星の中心だよね？ということに気付き、それをひたすら探索してく方針を立てました。
最初の方針だと単純に連結ノードが少ない順に走査してしまい途中でランタイムエラーを起こすケースがいくつか発生。これをデータサイズが大きすぎて起きるエラーと勘違いしてしまい*1、修正方針をミスったのが(時間を食ったという意味での)敗因。
終わったあと解説を読んで連結を削って1個だけになったノードを集めてまた探索するようなBFSっぽい実装にしたらすんなりACしてちょっと悔しい。
ただE問題で初めてのパターンでも基本方針を出せて概ね合っていると言えるところまでは組めたのでちょっと自信になったかも。
*1:実際無計画にArrayを宣言すると起こることがある
