トヨタ自動車プログラミングコンテスト2023#4(AtCoder Beginner Contest 311)に参加しました。
結果
A,B,C,Dの4問正解でした。
E問題ももう少しで解けそうな気がする。サンプルケースはACだけと提出するといくつかWAになってた。
A - First ABC
A,B,Cからなる文字列で最初にA,B,C3種類が登場するのは何文字目かを答える問題。
それぞれの文字に対して出てきたかをフラグ管理して、3つのフラグが全部立ったかどうかを1文字ずつ確認。3つともフラグが立ったのが何文字目なのかを答えれば良い。
他には1文字ずつ順番にsetに入れて言ってsetのサイズが3になったのが何文字目かを答えてもACできそう。
B - Vacation Together
N人分D日間の暇か暇じゃないかが与えられるので、全員暇な日が何日続くかを答える問題。
N人分の情報を圧縮してから数えれば良い。
一人でも暇じゃなかったら暇じゃない日としてフラグ管理して、暇な日が何日連続で続くかを数えて答えればACできる。
C - Find it!
有向グラフが与えられるのでループを探して1つ答えれば良い。
普段はループの検出でUnionFind木を使っているので今回のUnionFind木を使って解くことにした。
ループを検出したらノードが何個でループになっているか数えて、その数だけ順番にノード番号を出力した。
D - Grid Ice Floor
ゲームでよく見かける壁にぶつかるまでその方向に滑る床があって、初期位置から何マス通過できるかを答える問題。
初期位置を始点に幅優先探索をしていった。 現在位置と方向を与えると通過したマスにフラグを立てつつどのマスで止まるかを返す関数を用意して、止まった時のマスをキューに入れつつチェック済みかどうかをフラグ管理していった。 探索が一通り終わったら、マスを通過したかどうかのフラグを一通り確認していき、通過したマスの数を数えて答えた。
E - Defect-free Squares
一部に穴が空いたグリッドが与えられるので穴を含まない正方形が何個あるかを答える問題。
サンプルケースは解けたけどACはできなかった。
解き方の方針・手順としては
- 穴の数を2次元の累積和で事前計算しておき、左上から任意の座標の範囲に含まれる穴の数を簡単に求められるようにする。
- 二重ループで正方形の左上の座標をずらしつつ、最大でどれくらいのサイズで穴を含まない正方形が作れるかを探索する。
- 正方形のサイズ(n)を引数として、何個の正方形が作れるかを計算して返す。
（結果として、1からnまでの2乗和を返す。） - この結果を積み上げていき答える。（同じものを複数カウントしないように注意する。）
これで解けそうな気がしたけど、バグっているか何かだめなパターンがあるらしい。
ローカルやコードテストで処理するとTLEしそうなコードになったけど、提出してみるとTLEにはならなかったから、純粋に答えを間違えてWAになっているっぽい。
