AtCoder Beginner Contest 352に参加しました。
結果
A,B,C問題の3問正解でした。
コンテスト後にD問題の解説を見たら結構惜しいところまでは解けていたっぽい。採用するデータ構造を誤っていて処理に余計な時間をかけていたみたい。数列の最大値、最小値を取得するのにsetが使えるのは自分の中には無い発想だったのでためになる失敗だったと思う。
A - AtCoder Line
駅１から駅NまでのN個の駅があり、X駅からY駅へ移動する。このときにZ駅を通るかどうか答える問題。
XとYの間にZがいるかどうかを判断してYes/Noを出力するだけの問題。
X,Yの大小関係が不明なので大小比較してスワップして常にXがYより小さい/大きいを固定してから
X,Yの間にZがいるかどうかを確認すれば良い。
大小関係的にはになっているかどうかをif文で判断すれば早い。
もしくはループ処理で1つずつ確認していっても制約的には間に合う。
B - Typing
タイプミスしながらある文字列(T)を入力したので、もともと入力したかった文字列(S)の各文字が正しく入力できている文字列Tの位置を順番に答える問題。
文字列Sの文字を文字列Tの前から順番に探して答えていけば解ける問題。
文字列はそこそこ長い可能性があるので、文字を探すときは文字列Tの先頭からじゃなくて、
を探すときに途中まで探索していた文字列Tの続きから探索を始めていくと言う工夫は必要そう。
C - Standing On The Shoulders
巨人がN人いて、それぞれの肩の高さと頭の高さ
が与えられる。※地面を基準としたときの高さ。
巨人がそれぞれの肩に立って積み上がっていく時、巨人の頭の高さとして実現できる最大値を求める問題。
N人目の巨人の足元の高さはN-1人の巨人の肩の高さの和になる。 だからN人目の巨人の頭の高さは、N-1人の巨人の肩の高さにN人目の頭の高さを加えた位置になる。
N人の巨人それぞれが1番上にいる場合の頭の高さを計算して、最大値を出力すれば解ける。
N-1人の巨人の肩の高さを毎回計算しているとTLEしそうなので工夫が必要そう。
予めN人分の巨人の肩の高さの合計を計算しておき、巨人iが1番上だった場合は、肩の高さの和からを引いて
を加えることで巨人iの頭の高さを
で算出できる。
D - Permutation Subsequence
１～Nを並び替えて作った数列が与えられるので、i～i+Kの各位置の最大値と最小値の差の最小値を出力する問題。
色々考えてみた結果としては以下の通り。
- サイズKのウインドウをスライドさせているわけなので、１～N-Kまでが探索の範囲になる。N-K+1からK個数値を探していくと最後の数値はN+1になって数列の最大値を超過する。探すだけ無駄なのでどこからK個見るかの基準には1～N-Kで間に合う。
- 与えられる数列は１～Nを並び替えたものなので、それを元に値iは数列のどの位置にいるのかを管理している方が処理が楽そう。数列の端から端まで探索してKの値を探すより、1はどこ、2はどこというのを管理しておけばK個の値を参照するだけでその時の処理対象の位置が取得できる。
という事で各要素にランダムアクセスできて、先入れ後出しができるデータ構造が適していそうと思ったのでdequeを使って解くことにしてみた。 1つ要素を追加するときに最大値を更新して、1つ要素を削除するときに最小値を更新しながら、常に要素数がK個になるようにしながら最大値と最小値の差を計算して最後に差の最小値を出力してみた。
けどTLEでダメだった。
結局コンテスト中には解ききれなかったのでコンテスト後に解説を読んでみたら、 データ構造としてはsetを使うのが正解だったみたい。setだと最大値と最小値の取得が簡単にできるので要素を更新するたびに最大値・最小値をメンテする必要がなくなって、その分処理が早くできるっぽい。
確かにdequeを使って管理していると、すでにキューに入っているどれかが新しい最大値・最小値となる場合は毎回K個全てを探索しないといけなかったのでTLEの原因だろうなとは思っていた。
