- やった回: ABC329
- 成績: ABCD4完 / 1ペナ(＋未AC2ペナ) / 44:19(ペナ込み)
- パフォーマンス: 735
うーん、悔しいけど全体的に(初見である場合)頭の柔らかさを求める系の問題で、わりと現時点のベストは尽くしたのではというか、どうしようもなかったのではという気持ちになっている。強いて言うならC問題での1ペナは防ぎたかったよねってくらい。
E-F間でのdiff逆転、確かに今回くらいのdiffならワンチャンくらいはあるけども、分かって解くわけじゃないしなぁ。順位表見てたら気付けたんだろうか。ただしEからFに切り替える発想があったところでこのFが解けてたかと言われると微妙、ダメもとで投げる可能性が0ではないがかなり怪しい。
今回は終わった後にいしりば～さんと一緒に感想戦をしました。色々教えてもらって楽しかったです！🥰
A問題: ABC329-A Spread
素朴にcharsしてjoinで間に空白を足しました。
B問題: ABC329-B Next
sortして(最大値であろう)末尾の値を除去したあとの最大値を答えとして出力しました。
感想戦で色々話した結果、記述としてはこれ↓が一番シンプルなのでは、という話になりました。
gets.chomp.to_i puts gets.chomp.split.map(&:to_i).uniq.sort[-2]
C問題: ABC329-C Count xxx
要するにランレングス圧縮。ということに気付かず素朴に部分文字列の集合を作ろうとして一度TLE。メモリ消費もヤバくてテストケースが1個MLE。そういえばランレングス圧縮も典型90にあったなぁ…
感想戦でいしりば～さんに Array#chunk というこの問題におあつらえ向きのメソッドを教えていただきました🙌
D問題: ABC329-D Election Quick Report
なんというか、データの持ち方に悩んでSortedSetまで持ち出したんだけど実はそこまでしなくてよかった問題。 暫定一位といま票を得た人の比較だけでよいので、データ構造としてはシンプルな配列で得票数を持って、かつ暫定一位の人の番号を持っているだけでよい。
E問題: ABC329-E Stamp
(解説の写経のつもりだったけどTLEするコード) atcoder.jp
問題文のとおりの操作をするよりは文字列SをN個の#に戻せるかを判断した方が早くない？っていうのはわりと早い段階に気付いた。それは大変よかった。
ただそこからが全然ダメで、変換が出来なくなるまで闇雲に操作すれば当然TLEを起こすし、一度変換した後はある程度範囲を絞り込めるのでは、というところまでは気付いたもののそのまま物理時間がTLE。感想戦で解説を読んで悩みながら写経したんだけどまだTLEが取れず、他のRubyの人どうしてるんだろーって提出見たけど何が違うのか読み取るための頭が回らず今日のところはupsolveを断念。
以下追記
ふと思い立ってちょっと手を入れてみたら通ってしまった。 ちゃんと検証してないけど、差分を見てみた感じ多分写経したロジック自体がどうっていうより配列操作のなんだかんだで遅くなっているみたいで、写経の時点でeachとかしてなくてインデックス参照メインのコードになったのでcharsせず文字列のまま操作してみたらすんなり通った。
(upsolveコード) atcoder.jp
大まかな方針としては、kyopro_friendsさんの解説が直感的に分かりやすかった。
アライグマ「E問題は先週のABC328Dとだいたい同じなのだ！ 例えばT="ABC"のときは、操作を逆に考えると「Sのうち"ABC", "AB#", "A##", "##C", ……みたいな部分文字列を"###"に置き換えて良いとき、全部'#'にできるか？」って問題になるから、」
— 競技プログラミングをするフレンズ (@kyopro_friends) 2023年11月18日
アライグマ「前から貪欲に置き換えて、置き換えるごとに2文字戻ってやり直すのだ！」https://t.co/dDp4e6d6IQ
— 競技プログラミングをするフレンズ (@kyopro_friends) 2023年11月18日
F問題: ABC329-F Colored Ball
(upsolveコード) atcoder.jp
コンテスト中は全然手を付けなかったんですが、いしりば～さんがコンテスト中に挑戦されていたということでupsolveしてみようということになりました。
素直にシミュレーションしてダメならどうしたらいいのかいまいち分からなかったので感想戦で解説を読みながら解きました。何か特別なアルゴリズムがあるというよりはわりと素朴な速度改善をするような感じで「えっこんなのあり…？」みたいな気持ちになりました。ACを確認した後興味本位で箱のサイズ比較処理を削ってみたらちゃんとTLEするんですよねぇこれ。
こういうパターンもあるのか、とよい学びになりました。
ということで、今週も対ありでした！
