いやーこれはつらい。結果から見ればCDEで目移りしすぎて撃沈した回。レートで言うと前回持ち直した分が(今のところ)±0で吹っ飛びました。いやむしろ±0で済んでよかった、もっと酷いと思ってた。
C問題は想定解法ではないにせよ他の情報を入れる前に追加20分弱でACしてるし、D問題も方針気付けば*2十分出来たし、頭が固いことをこれでもかと突き付けられた心境。やってる問題のclarが出たらよく読みましょう。
A問題: ABC321-A 321-like Checker
とりあえず文字列を先頭から走査して単調減少してなければ処理打ち切り。もうちょっとオシャレになるんでないかこれ。
B問題: ABC321-B Cutoff
とりあえずN-1ラウンド終了時点での以下の値を出す。Nはそんなに大きくないのでsortしちゃうとインデックス引いて操作できるので楽。
- 現時点での採用スコアの合計
- 現時点での最小スコア
current_worst - 現時点での最大スコア
current_best - Xから1. を引いた値(現状のスコア状況から単純にあと何点足りないか)
required_point
で、判定としては2つ閾値があって、
required_pointがcurrent_worst以下ならcurrent_worstが可算対象として採用されればよいのでそれより低い値の最小値と言うことで0でよい。required_pointがcurrent_best以下ならrequired_pointが可算対象として採用されればよいのでその値をそのまま出力required_pointがcurrent_bestを超える場合は入れたところでベストスコアが更新されて弾かれるため、どう頑張っても可算対象として組み込めないので諦める
C問題: ABC321-C 321-like Searcher
(upsolveコード) atcoder.jp
制約でKの上限がないことにビビりつつ取りあえず該当の値を列挙しまくって、「この値が何番目の321-like Numberなのかを答えてください」ならまだどうにかなりそうなんだけどなぁと思いながら悩み、方針が出せそうになかったので一度飛ばしてDとEを見る。
DもEもアカンということで戻ってきてもう一度悩み、終了20分前くらいにclarをちゃんと読んだら「321-like Numberは有限個であり、Kはその範囲内であることが保証されている」という旨が明記されていることから「これ適切に値を絞ったら全列挙でどうにかなるのでは」ということでやってみたけど時間切れ、そのまま解説やタイムラインを見ずにやってみたら普通にAC。時間的にはDとEにうつつを抜かす時間がなければ何とか解けてた計算ではあるだけにこれは悔しい。 ちょーっとスマートな列挙が出来ず、BFS的というか前の列挙内容を保存しておいて、それを参照して値を組み立てて…みたいな回りくどいことをしている。
その後rinrionさんのツイートを見てbit全探索で解けることを知りやってみたのがこちらのコード。 atcoder.jp というか解説コードもこんな感じの方針ぽいし、こっちの方がやってることが分かりやすい。
D問題: ABC321-D Set Menu
(upsolveコード) atcoder.jp
- セット価格に天井がなければ
main_prices.sum * m + sub_prices.sum * nで出せる N*Mの二重ループは無理だけど合わせて定数回程度のループなら回せそう- 累積和みを感じる
とりあえずこの辺は頭に浮かびつつ、天井対応をどうするかで悩みコンテスト中は諦めた。
その後解説を見てソートが可能なことに気付き(B問題ではノータイムでソートしたのに？)、そうしたら二分探索で天井ポイント探索が可能になるし、手前の値も累積和作っておけば簡単に出せるじゃんとなりAC。これも方針さえ見えれば、という気持ちがありかなりくやしい。
ということで今週も対ありでしたー
*1:不正が多かった関係で再計算予定らしい https://twitter.com/atcoder/status/1705583219754856451
*2:まぁ気付けないのが実力なんですよというのは甘んじて受けます
