最近、会社のSlackにある競プロチャンネルにジョインしたのもあって、久しぶりに競プロ熱が戻ってきたので参加している。 昨日行われたABC294に参加したのでその感想とか。 なお、問題の意図や解き方を解説するものではなく個人の感想です。またABC294のネタバレになるのでこれから挑戦される方は注意。
A - Filter / B - ASCII Art
簡単なので特になし。
- ACした回答
C - Merge Sequences
最初は雑にA+BをしてsortしたCを用意して、A,Bの要素がCのどこにあるかを検索するようにしていた。 しかし、これだとAとBの回数ループするのと、その中でc.indexするので最悪Cの長さ(=A+B)検索するのでループ回数が増えてTLEする。 計算量はO(n2)であっているかな・・・？(自信なし)
TLEしたので別案を考える。 A,Bは狭義単調増加列で必ず小さい順にソートされていることに気がついた*1。 小さい順にソートされているので、N+M回ループしてAの先頭とBの先頭を比較して小さい方に今のループ回数を格納するという方法に変えたらACした。
D - Bank
まず問題を理解するのに時間がかかってしまった…。
イベント1でキューにプッシュして、イベント2でキューから除外、イベント3はキューの先頭を表示ということに気がついたらあまり難しくなかった。
最初はキューをArrayにしていたのだが、イベント2でArray#deleteの実行が遅かったので断念。
次はキューをHashにしてその部分は高速化したのだけど、イベント3のときにhash.keys.firstとしていたのでここがボトルネックになってTLE。。
どうしたものか？っと悩んでいたのだけど、ふとRubyのHashはデータを追加した順番を保持するのを思い出したので、 hash.first.first に変更したらACした。
別解
コンテストが終わったあとに気がついて直したらACしたパターン。
キューをArrayで表現し直したパターン 提出 #39883032 - AtCoder Beginner Contest 294
Array#delete が遅いので、N人分のArrayを事前に用意しておいてイベント1が来たらArrayの該当の要素をtrueにして、イベント2が来たらfalseにする。
イベント3は何番まで出力したかを保持しておいて、自分の今の番号含めて次のtrueになっている要素(受付待ちしている最小の番号)を検索して出力するという方法にしたらACした。
コンテスト中にもこの方法を思いついたのだけど、次の受付待ち番号の検索をイベント2のときに実行していたがためにループ回数が増えてTLEした。
そして、この記事を書くためにACしたコードを見直していたが、事前に用意しているArrayがすべてtrue(受付待ち中)になっていて、イベント1の処理が不要になっていた。
よくこれでACしたなぁっと思ったが、イベント2も3もすでに受付に呼ばれいてる人がいる前提なので問題ないのだろうなっと思った(1がなく2と3が呼ばれることはないという暗黙？の前提)。
E - 2xN Grid
この問題はコンテスト中には時間が解けなかったが、コンテスト後に一発で通った問題だった。コンテスト中に解けていればなぁ～悔しい。 * ACした回答: 提出 #39885934 - AtCoder Beginner Contest 294
そもそも連長圧縮ってなんぞや…ってところだったが、ググった結果ランレングス圧縮ということに気がついて問題が理解できた。 素直に1行目と2行目の配列を作って、頭から比較していくとTLEしそうだだなっと思ったので、文字種と長さが格納されていることに着目して、連続した文字の切れ目ごとに1行目と2行目の配列を読み出していく方法を取った。 TLEするかなぁ～？っと思ったが案外一発で解けてよかった。
F - Sugar Water 2
こちらもコンテスト中には解けなかったので、おまけとしてチャンレンジした。 しかしというかやはりというかTLEした。
うまく枝切りする方法を考えていたが眠くなってきたので断念…。 後で解説とかを見ながら解くかも。
総括
D問題まで解けてよかったが、もう少し早く解けていればE問題もいけていたので悔しい感じ。がんばろう。 あと、改めて自分のコードを文字に起こしてみたが、とても難しいね！
*1:これが真なのか正しく理解していないが…ACしたのでそうなのだろう
