トヨタ自動車プログラミングコンテスト2023#5(AtCoder Beginner Contest 320)に参加しました。
結果
A,B,C,Eの4問正解でした。
D問題は問題文を斜め読みすると難しそうな気がしたので後に回して、Dより簡単そうに見えたE問題から解くことにした。
D問題自体も問題分をちゃんと読むと思ってたより難しくなさそうだった。
A - Leyland Number
指定されたとおりに数値計算する。
指数計算が必要なのでpowを使って楽に解いた。
powを知らなかったならループで頑張ってBをA回掛けたり、AをB回掛けたりすれば解ける。
ループと数値計算がわかっていれば解ける問題。
B - Longest Palindrome
文字列が与えられるので回文となっている部分の最長の文字数を答える問題。
文字列は100文字以下なので部分文字列全通りに対して回文かどうか確認しても処理時間的には余裕で間に合うので、全通り確認した。
具体的には、元の文字列に対して部分文字列の最初と最後はそれぞれ何文字目かで二重ループを回した。
部分文字列の最初と最後は元の文字列の何文字目かをもとに部分文字列を作って、別途用意しておいた、渡された文字列が回分かどうかを判定する関数で判定させた。
C - Slot Strategy 2 (Easy)
3つのリールのスロットがあるのですべてのリースを同じ目にするには最速何秒かかるかを答える問題。
どう解こうか悩んだ結果、全通り探索することにした。
複数のリールを同時に止めることはできないけど、運が悪くても最大3周するまでには全部のリールを止められる。
リールは最大でも長さが100なので、300秒以内のどこかに答えがある。
0秒から3*リールの長さの範囲での3重ループで探索した。 各ループはそれぞれのリールに対応していて、 それぞれのタイミングでそれぞれのリールを止めた時、3つが揃っているかどうかを確認して、揃っているなら1番最後にリールを止めた秒数が答えの候補になる。
D - Relative Position
時間が足りなくて解ききれなかった問題。
座標平面上に人がいて、この人からみてあの人はx軸正方向でX、y軸正方向でY離れているという情報が複数あるときに、それぞれの人の座標を答える問題。
最初に問題文を斜め読みした時は正方向というのを見逃していたので、人がいる候補が4つもあって特定するのは難しそうだなと思ってた。
実際は正方向なので一意に絞り込めるので、そこまで難しくなかった。
人1は原点にいるので、情報がある2人は繋がっている無向グラフとしみなして、 人1から深さ優先探索や幅優先探索をしていけば解けそうと考えた。
E - Somen Nagashi
先頭の人が必ず全取りするけど、1度食べたらしばらく食べないと言う設定の流しそうめんで誰がどれくらい食べたかを答える問題。
設定は以下の通り。
- 人は番号順に並んでいる。
- 時刻にそうめんが流れてきて、食べると秒後に戻ってくる。
- 列の先頭の人が全取りするけど、食べるとしばらく列から離れる。
戻ってくる時は列の元の位置に戻ってくる。
時間が秒後までありえるので1秒ずつのシミュレートでは時間がかかりすぎる。なので、イベントドリブンでシミュレートして解くことにした。
実装方針としては
- 人の列は優先度付きキューで管理する。常に列の先頭の人がそうめんを全部食べるので。
- イベントは発生する時間とイベントの種類(そうめんが流れるか人が列に戻ってくるか)、イベントの種類に応じた必要な情報(列に戻ってくる時間や流れてくるそうめんの量、列に戻ってくる人の番号)をタプルにして優先度付きキューに入れて時間別イベントの種類別にソートして管理する。
イベントドリブンのシミュレートを知っていれば多分簡単に解ける問題。