AtCoder Beginner Contest 258に参加しました。

結果

A,B,C,D問題の4問ACでした。 E問題はやっぱり難しい。解けそうな方法を考えたけど実装量が多くて、コードを書きながら解き方間違えてる気がしてきた。結局時間内には実装が終わらなかった。

A - When?

指定分数後の時間を表示すれば良い問題。

言語によっては時間計算のライブラリがあるのでそれを使えば楽に解けそう。

地力でとくなら、時の方は（指定分数/60）時間後になるし、今回は最大でも100分なので21か22のどちらかになる。

分の方は指定分数を60で割った余りになる。こっちは1桁になる可能性があるのでそこだけ気をつけて先頭0埋めの2桁表記で表示させる。

出力時に先頭0埋めで表示桁数の設定ができるのでその設定を使って分は表示させるとか、9分以下なら0を表示後に計算した分数を表示させるとか、分数を文字列にして"00"と結合して下2文字を表示させるとかやり方は色々ある。

A問題にしてはちょっと面倒くさい気がする。

B - Number Box

マス目のあるマスを始点としてNマス移動して、マス目に書かれている数字を並べた時にできる数字の最大値を答える問題。

制約を見るとマス目がかなり小さいので全探索で十分間に合う事がわかる。
なので全探索するコードを書いて答えを探せば良い。

実装方法を考えていた時に、似たような内容の過去問の解説で始点の座標と縦方向・横方向の変化量を引数にして探索を行い結果を返す関数で簡単に実装していたことを連想して、そういった関数を作って答えてみた。 8方向分の探索が8回関数を呼び出すだけで住むのでだいぶコードがスッキリできた。（8方向分の探索を1つ1つ書くのはすごく大変そう。）

後は、数字1桁を表す文字は'0'で引くと文字が表す数字を整数値として取得できるとか、 N進数を10進数に変換するみたいに10倍して数字を足してを繰り返すとマスに書かれている数字を順番に並べた数字が作れるとか細々としてテクニックを使って実装した。

C - Rotation

複数のクエリを処理しながら答えていく問題。

よくある解き方としては、最後から処理していくとか、複数の処理をまとめて行うとかして計算量を削減するのが多いと思う。

愚直に解くと「S の末尾の文字を削除し、先頭に挿入する」をx回ループで処理する解き方になると思う。 Q個のクエリで毎回x回のループを処理していては時間がかかりすぎてTLEになるのは予想できる。

なので、x回分の処理を部分文字列を使って1回で処理できるようにしてみたけどそれでもTLEだった。つまり、もっと早く処理できないといけないってことになる。多分各クエリでO(1)くらいで処理できないと間に合わないんだと思う。

少し観察すると、「S の末尾の文字を削除し、先頭に挿入する」を実行するたびに
abcd → dabc → cdab → bcda　と言った具体に文字の開始位置が1つずつずれていっているように見える。そこで今の文字列の開始位置はもとの文字列の何文字目になるのかを管理しつつ、クエリによって開始位置は何文字目なのかを更新したり、管理している開始位置からx文字目はどの文字なのかを答えてみた。
こっちの方法ならACできた。

D - Trophy

どうやって解こうかなと少し考えた問題。

ちょっと考えてみると、以下に気づいた。

X回のステージクリアの内何回かはステージの初回クリアに使われ、残りがクリア済みステージの周回に使われる。
ステージの周回は、クリア済みステージの内 $B _ {i}$ が最小のステージを集会するのが1番効率がいい。
制約的にO(N)くらいで解きたい。

そこで予め、ステージiまでクリアするのに要する時間を累積和を使って計算しつつ、 $0 \leq x \leq i$ のうち $B _ {x}$ の最小値を管理しておき、
1～i番目のステージまでをクリアした場合にX 回ステージをクリアするために必要な時間の最小値を $1 \leq i \leq N$ の範囲でループを使って計算した。
i番目までのステージをクリアするのに必要な時間は累積和の値を参照することで求められて、残りX-i回分の周回は $B _ {1}$ ～ $B _ {i}$ までの最小値をもとに計算できる。