ABC391 参加結果・感想
お疲れ様です、茶色コーダーの「さわーくりーむおにおん」です。
もう2月ということが信じられない今日この頃です
2025/2/1に行われたABC391に参加しましたので、問題を解く際に考えていたことや感想をまとめてみようと思います。筆者が提出したPythonコードも載せておきます(A~D問題)。
何か参考になることがあれば幸いですし、「こんな解法もあるよ」って方はコメントやX(@SCO0720)で共有してもらえると嬉しいです！
私自身はABCDの4完でした。特にD問題の実装でハマってしまい、結局終了ギリギリにAC出来ました。
A問題
【考えてたこと】
・恐らく置換とかで上手く書く方法があるんだろうけど…8パターンなら全部列挙する方が早そう・これはATT(AtCoder Typing Training)とでも呼ぶべきか…
【提出コード】
https://atcoder.jp/contests/abc391/submissions/62307874
【別解】
愚直に全パターン書かなくともtranslate関数を使うと下記1行で書けました。
(ちなみにreplace関数は変更後の文字も置換する対象になるので使いにくいです。）
参考にさせていただいた記事
print(input().translate(str.maketrans('NEWS', 'SWEN')))B問題
【考えていたこと】
・M,Nが最大50なら4重ループでも十分間に合うはず
→全探索しちゃえばよくない？左上が一致していたら他のマスもTと一致するか判定する。
【提出コード】
https://atcoder.jp/contests/abc391/submissions/62269026
【反省点】
Sの探索する範囲を解説のようにrange(N-M+1)にしていれば、IndexErrorの心配がなくスッキリ書けていたかな。
C問題
【考えていたこと】
・C問題で良く出てくるクエリの問題。毎回複数の鳩がいる巣の数を数えるとTLEになるので、出力する用に変数を用意すればいい。
・N匹の鳩とN個の巣…鳩の巣理論か？？(関係ない)
【提出コード】
https://atcoder.jp/contests/abc391/submissions/62276476
【反省点】
indexの番号の付け方がド下手くそ。0-indexにするか1-indexにするかは統一しよう…
D問題(今回の山場‼‼)
【考えていたこと】
個人的にこの問題、実装に苦戦してしまったので解いている時の思考を整理してみようと思います。
＜問題文から考えたこと＞
・行を作るブロックの組み合わせは固定
→各ブロックが消える時間は先に計算できそうなので、消える時間を格納した配列があればいい。あとはクエリごとにO(1)で取り出してYes Noを判定すればOK。
・ブロックが消えるタイミングは次の2種類
①消える行の候補が一番下にあり、最後のブロックが埋まった時
②既に1行分埋まっていて前の行が消えた後
→時間を入れる変数を用意。1行目から順番に消していって➀➁のどちらの タイミングで消えるか判断する。
・消えない行が出たらそれ以降はブロックは消えない。
＜じゃあ実装どうしよう＞
何行目まで消えるか把握したかったので、ブロックを消さずに全て下に落とした状態を考えてみた。
→行ごとにy座標を格納したリストを用意しておけばいいのでは？
→消える時間の候補(上記➀)はy座標から求められる。
という訳で
処理の順番としてはこんな感じ
❶行ごとにブロックのy座標を入れたリストを作る
❷1行ごとに取り出して消えるか(ブロックが埋まっているか)確認、埋まってなければ❺へ。
❸その行が消える時間を(前の行を消した時間+1)か(行を埋める最後のブロックが落ちた時間)か判定して記録
❹❷に戻る。
❺Q個の質問を受け取って記録した時間から判定
＜MLEに悩まされる茶色コーダー＞
いざ実装して提出してみると…MLE？！(こんなの初めて～～～～)
それ以外にもTLEやらWAやらREやら大集合してしまいました。
ちなみにXで画像を投稿したらそこそこ反響があり、chokudaiさんまで届いてしまいちょっと恥ずかしかったです。初めての絡みがネタ投稿でいいのか俺…
という訳で、最初に用意した列ごとのリストがデカすぎました…
必要に応じてリストを追加するようにし、最小限にしたら余裕でACしました。
【提出コード】
ボロボロになりながら時間と闘いながら書き殴ったコードです。
https://atcoder.jp/contests/abc391/submissions/62310528
【反省点】
茶色になってまでMLEに翻弄されているのはちょっとダメでは…考察まではスムーズだったけど実装に時間がかかったのは精進不足。
まとめ
ABC391はABCDの4完(ほとんど滑り込み)でした！パフォは875、レートは+18上がり733になりました。
先週の大敗北を少し取り返せたといったところでしょうか。
また精進しますかぁ、ではでは