AtCoder Beginner Contest 335(Sponsored by Mynavi)に参加しました。
結果
A,B,C,Dの4問正解でした。
E問題は制約的にTLEしそうだなと思いつつ他には良さそうな方法を思いつかなかったのでとりあえずDFSで実装した。
案の定TLEして一部はREだった。
E問題まで安定して解けるようになりたいなあ。
A - 202<s>3</s>
2023で終わる文字列が与えられるので最後の3を4に変更して文字列全体を出力する問題。
色々解き方がありそうだけど、私は最後の文字以外を出力して、 最後に4を出力するように実装した。
文字列の扱い方がわかっていれば解ける問題だと思う。
B - Tetrahedral Number
Nが与えられるのでとなるx,y,zの組み合わせを辞書順に出力する問題。
Nは最大でも21なので3重ループで全探索しても十分間に合う。 なので全探索して条件を満たす場合のx,y,zを順番に出力するように実装して解いた。
多重ループが問題なく実装できれば解ける問題だと思う。
C - Loong Tracking
長さがNある龍が1マスずつ移動するので指定された部位がどの座標にあるのかを答える問題。
各部位は前の部位に追従するので、どのデータ構造を使ってどの部位の座標は今どこにあるのかをうまく管理するのかを考えるのがポイントな問題だと思う。
解説を見るとdequeを使えば良いってあったけどdequeの存在を知らなかったので、 長さNの配列を用意しつつ、先頭の座標を保存した位置を指す変数を用意して、 1つずつ後ろにずらしながら新しい先頭の座標を管理していった。
長さNが5だったら、
頭 最後尾
頭、胴体、胴体、胴体、尻尾
胴体、胴体、胴体、尻尾、頭
胴体、胴体、尻尾 、頭、胴体
みたいな感じで、 どこを頭にするのかをずらして管理していくことで、頭は移動しつつほかは頭に追従するという関係を表現して 座標を管理していった。
この部位の座標が欲しいとなったら、その時先頭となっている位置から数えて指定された部位に相当する場所を計算して該当部位の座標を出力した。
D - Loong and Takahashi
1辺のサイズが奇数の正方形のグリッドがある。中央にはTと書かれているので、 残りのマス全部に一筆書きで1からまでの数を順番に記入していき、グリッド全体の内容を出力する問題。
一筆書きなら何でも良さそうだけど、左上から渦巻き状に順番に数字を埋めていく方針で実装していった。
今どの方向に記入して行っていて、次に記入しようとしているマスはグリッドからはみ出ていないかとかまだ記入されていないかをもとに記入するか方向転換するかを判断して順番にグリッドを埋めていった。
渦巻き状に埋めていけば良さそうなのはサンプルケースを見ていれば気づけると思うので、 あとはそのアイデアを正確に実装できるかどうかな問題だと思う。
E - Non-Decreasing Colorful Path
無向グラフがあって各頂点に数字が書かれているので、
頂点1から頂点Nまで、各数字が広義単調増加になるようにパスを作って、パス上の数字の種類数が得点になる。
この時、得点の最大値を求める問題。
時間内には解けなかった。コンテスト中に考えたこととしては 以下の通り。
- 頂点数の制約が結構大きいのでDFSとかBFSでパスを計算してもTLEになりそう
- 数字の種類数が得点になるのでパスは長いほうが嬉しい。だからダイクストラ法みたいな最短経路を求めるアルゴリズムだと答えは求められなさそう。
他に特に方法も思いつかなかったので、一旦DFSで実装してみた。 探索を少しでも減らすために、広義単調増加とならない場合は辺が無いものとしてグラフを作って解いてみたけど、 やっぱりTLEした。
その後いろいろ考えてみて、 頂点に書かれている数字が同じものは同じ頂点としてマージしたり、 DPで解ければ解けそうな気がするなあと思った。 思ったけど残り時間が5分くらいしかなくて実装が間に合わなかった。