- やった回: ABC328
- 成績: ABCD4完 / 1ペナ(+未AC1ペナ) / 37:36(ペナ込み)
- 推定パフォーマンス: 980
松江のホテルで力尽きていて参加できなかったABC328を、Rails Girlsの競プロ同好会でセルフ実況しながらバチャりました。自分が解きながらだったのでかなり駆け足の解説になりましたが、お付き合いいただきありがとうございました！
推定パフォーマンスを見た感じまずまずの結果*1というところですかね、早解き回ではあったのかも。E問題は終了間際にガラッと方針転換して結局間に合わなかったけど解説読まずには解けたので、うーん、でも時間内に解きたかったなぁといった気持ちです。
A問題: ABC328-A Not Too Hard
素直にループ回して条件満たすスコアを加算していきました。ゴルフにならない範囲でももう少しならコード短くできる気がする。
B問題: ABC328-B 11/11
なんか無駄に悩んでしまった。
方針としては解説でいう1の方。提出するまでの手元確認でボロボロと細かいミスが多くてうーんって言う感じ。こういうのシュッと書けるとカッコいいよね。
C問題: ABC328-C Consecutive
累積和の判断に苦手意識があったので、問題文を読んでわりとすぐに累積和の問題であることに気付けてちょっと嬉しかった。
最初に文字列を全走査して隣り合う数をカウントしていって累積和の配列を作っておき、質問の入力はそれを使って答えていく、という、方針さえ出せればとてもシンプルな累積和でした。
D問題: ABC328-D Take ABC
正直過去に類題やったな…？という記憶が頭の片隅にありつつ、何故か素朴に正面から体当たりをして砕けました。単純に負荷かける系のテストケースが少なかったんだと思うんだけど意外とTLE起こしてなくてへぇーって気持ちになりました。
まぁそれで通るならD問題になってないでしょということで先頭から順にスタックを積んでいき、直近3文字がABCであれば除去して次の文字を見る、というのをやっていって無事ACしました。過去の類題よりもスッキリ書けて「次は20分くらいでいけるだろう」という過去の私の見積もりもペナルティ込みでだいたい正解。次はさすがに10分で行けるのではなかろうか。
あと「配列の末尾3つの要素」が欲しいんだったらans[-3..-1]よりans.last(3)の方がお洒落だったなと思う。
E問題: ABC328-E Modulo MST
(upsolveコード) atcoder.jp
正直、「全域木って何ですか」という話から始まったので最初から割と絶望的かと思いきや、意外に健闘しました。……いや、最初から正しい解法にたどり着いていれば正直この問題取れたんだけど。 雑な問題の趣旨としては「受け取ったグラフから辺を削って木にしたとき、所定の計算で得られるコストの最小値を求めよ」という感じ。
で、D問題を解き終わった時点で1時間くらい時間があったので、まぁぼんやり過ごすよりは今からでもお勉強したろってことでまずはこの記事を読みました。 www.momoyama-usagi.com
一通り問題の趣旨を雑に理解したところで「よっしゃーこの記事にあるクラスカル法とやらで解くんですね？初めて実装するけどがんばる！」みたいな感じで解いたんですよ。実際「最小全域木」を求めるのであればクラスカル法を使うのが正しいのですが、結果から言うとこれが罠(？)でして*2。
入力例1と2はすんなり通るものの入力例3が全く合わず、とりあえず投げてWAを確認した後デバッグ出力を仕込んだりしても意図した木にはなってるっぽいぞと言うことになり、何か問題文を誤読しているのでは？と読み返してみることに。
そしたら案の定誤読してました。問題文の要求は「最小全域木のコストをKで割った余り」ではなく、「(ありうる任意の)全域木のコストをKで割った余りの最小値」であることに気付いたのが終了10分前とか確かそんなあたり*3。Nの制約が最大8だし、そうなると全域木かもしれない辺の組み合わせは最大でもなので、まぁ全探索でやれってことなのかしらという感じでバチャ時間をオーバーランしつつ解いたら無事AC。
いやまぁでもクラスカル法のコードが書けるようになったし、いつまで経っても誤読は減らないけどこういうことがあるんだって分かったし、素直によい勉強になったと思っています。
