日鉄ソリューションズプログラミングコンテスト2023（AtCoder Beginner Contest 303）に参加しました。
結果
A,B,Cの3問正解でした。
D問題がだいぶ沼った。解く方針を二転三転させてそれでも解けなかった。
A - Similar String
同じ長さの文字列2つが与えられるので、それぞれの文字列の同じ位置にある文字同士が条件を満たすかどうか判断し、 N文字すべてが条件を満たすかどうかを答える。
愚直に1文字ずつチェックして結果を答えれば良い。
いくつかある条件を1つずつif分でチェックするだけ。
B - Discord
N人が1列にM回並んだ時、1回も隣り合ったことのないペア数を答える問題。
各ペアに対して隣り合ったことがあるかどうかをフラグを用意して、
M回それぞれで隣り合っているペアのフラグを更新していく。
最後にフラグを一通り確認して隣り合っていないペアの数を数えて答える。
C - Dash
体力を消費しつつ指定された順番に移動した時、体力を使い切るまでに最後まで行動できるかどうかを答える問題。
一部の地点では体力が回復できるので愚直にシミュレートするしか解く方法はなさそう。 順番にシミュレートしつつ、体力が回復できる時は必ず回復すように行動していく。 最後まで行動できるかどうかを確認して答えれば良い。
D - Shift vs. CapsLock
aとAでできた指定された文字列を作るときにキー入力の順番を考えて最速で入力する場合の時間を答える問題。
時間内には解けなかった問題。
キーの入力方法は実際のキーボートと同じで、aだけ押す、shiftと一緒に押す、CapsLockを押すの3通り。
同じ文字を続けて入力する場合はShiftを押しながら連続して入力するのとCapsLockを押してから入力するのとどっちが早いかを計算して足していってみた。
この場合だとテストケースで答えが一致しなかったので別の解き方を考えることにした。
たぶん、その文字だけを連続で入力する場合はこれで良いと思うけど、どっかのタイミングで一時的に損するかもしれないけど別の入力方法にしたほうが全体を見ると早くなる方法があるんだと思う。
次に何文字目を入力したのかとその時のCapsLockのON/OFFで状態を分けて、各状態を1つの頂点とみなしてグラフでの最短経路問題に変換して解いてみようとした。
最終的には実装が間に合わなくて解けなかった。解説を見てみると想定回はDP法なので、頂点の作成と辺の作成を正しく出来ていれば一応解けていたと思う。
最初に考えた方針が間違ったときのリカバリーに失敗した気がする。 コードを書き始める前の考察がちょっと足りなかったのかな。
