ユニークビジョンプログラミングコンテスト2023 夏 (AtCoder Beginner Contest 312)
まとめ
ABCDFの5完。
問題が結構面白かった。バリエーション豊か。
よくなかった
戦略的にはちょっと失敗した。 Fに先に手をつけていれば順位が結構上がったかもしれない。
よかった
前回に続いてノーペナだった。
解けた問題については無駄な実装をしてなくて、そこそこ速解きができていた。
特にD, F問題はそれぞれ8分, 15分間ほどで解けていて素晴らしい。
E問題はかなり惜しいところまで実装できていた。コンテスト後に少しだけ手直ししたら解けた。
問題ごとの感想
✅ A - Chord
問題文に記載された文字列の列をしっかりコピペする。
文字列の列は ドレミファソラシ に該当するコードらしい。
✅ B - TaK Code
左上の座標を全探索です。
画素の判定については「シェビチェフ距離」を実装に取り込むと見通しが良くなるかな? 「実装慣れしてないと時間が奪われる」タイプの問題が序盤に来ると Difficulty がいい感じになる気がしている。
✅ C - Invisible Hand
とは言ったものの、本当にこれで解けてるのかな・・?と不安になりながらの提出でAC。
✅ D - Count Bracket Sequences
制約を見る限り、文字列の長さ分の2重ループが可能です。
閉じのない ( の数を状態として DP ができることにすぐに気づけて無事にAC。
❌ E - Tangency of Cuboids
100x100x100 空間なので、全ての座標を考えても 10^6 個で全探索ができます。ある面で3つ以上の立体が接することもないので、答えの合計も大きな数字にはならず、全てをカウントアップする方式で上手くいくはず。
この方式でいい感じに実装できており、サンプルは合って TLE にもなっていない提出までできた。
全ての面が他の立体と接している時の答えが合っていないことがわかり、どこが悪いのかわからずコンテスト中の解決は達成できず。惜しい。
✅ F - Cans and Openers
缶については満足度が大きい順、缶切りについては使用可能回数が大きい順に取れば良い・・ というのはかなり直感的です。こういう場合は基本は貪欲で、缶切りについて何かしら一工夫すれば良さそう。
まずは缶切りを全く使わない場合の答えを出して、使う缶切りの数を1個ずつ増やす感じでやると見通しが良くなった。
缶切りを増やす = 「食べられる缶を1個減らす代わりに、選べる種類が増える」という行為。
板書
https://scrapbox.io/files/64c5e2023fa5ba001cc4a96b.png
立体のお絵描きを頑張りました。