UNICORNプログラミングコンテスト2022(AtCoder Beginner Contest 269)に参加しました。
結果
A,B,C,Dの4問正解でした。
久々に4問解けた気がする。E問題も解説を見ると解き方の方針は合ってたっぽい。もう少し時間があってデバッグが間に合っていればACできた気がする。
A - Anyway Takahashi
問題文の通り計算結果と指定文字列を出力すれば良い。
計算結果出力後に改行するのを忘れなければ正解できると思う。
B - Rectangle Detection
解き方が色々とありそうな問題だと思う。
＃で表現された長方形の領域が行と列の2軸でどこからどこまでかを求めて答える問題。 ループで長方形の開始の行と終了の行、開始の列と終了の列を探して答えれば良い。
文字列の中で特定の文字を含むかどうかを探す関数が有るかとか使い方を調べるのが面倒だったのと、2重ループで全文字を確認しても時間に余裕が合ったので、A,B,C,Dを適当な値で初期化してから
S[i][j]が#の時,
,
,
を計算して最終的なA,B,C,Dを出力することにして解いた。
C - Submask
まず問題文を読むと10進数表記の数値を2進数に変換してどのビットが1になるのか求める必要があるのがわかる。 そこからは色々解き方がある気がする。
最初はbit全探索で全通り確認することを考えたけど最大で回処理することになるのでTLEしそうだなと思った。（コンテスト後に気づいたけど、1となるビットは最大でも15個なので1となるビットの内どれを含めるかのbit全探索なら
回の処理になるからこれならTLEせずに済みそう。）
次にならDP[x][何か]でも処理できることが多いのでDPで解けないかなあと考えてみた。
DP[iビット目][選ぶ/選ばない]として手計算してみるとビットが1のときだけ値が変化するので最終的に
DP[i番目の1となるビット][選ぶ/選ばない]でDPできそうだなあと思いた。
よくよく考えるとDP[i]の結果に対して
を足す・足さないで分岐していくので幅優先探索の要領で探索していくほうが良さそうと思って幅優先探索で解いていった。
D - Do use hexagon grid
最終的には連結成分の数を答えるので、Union-Find木で処理していくのが良さそうだなと思ってUnion-Find木で解いていった。
黒いマスの数は最大で1000個なのでどの点とどの点がつながっているかを2重ループで調べてもTLEはしないので、全組み合わせで点同士が連結しているかを確認し処理していった。
Union-Find木を知っていればそれほど難しい問題ではないように思う。
E - Last Rook
インタラクティブな問題は珍しいかった。
問題としては、各行・列には1個だけコマが置ける時、どのマスにコマを置けるかを答えれば良い。
問題文を読んですぐに2分探索を使って行と列を個別に探索すれば良いと思った。
最終的にデバッグが間に合わなくてACできなかったけど、解説を見てみたら解き方の方針は合っていたっぽい。
コンテストが終わって見直してみたらちょっと修正しただけでACできた… 質問回数の上限である20回でループを回していたけど、20回目で特定できたときに答えを出力するの忘れてたみたい。 ループの中で1ループ1質問でコードを書いていたので20回目の質問でマスを特定できたときはループを出てから何もしていなかった。 このミスがなければ時間ギリギリだったけどACできたのでちょっと悔しいなあ。
