ABCリアタイチャレンジ・ABC321

やった回: ABC321
成績: AB2完😇 / 0ペナ / 20:26(ペナ込み)
パフォーマンス: 561(当日夜時点)*1

いやーこれはつらい。結果から見ればCDEで目移りしすぎて撃沈した回。レートで言うと前回持ち直した分が(今のところ)±0で吹っ飛びました。いやむしろ±0で済んでよかった、もっと酷いと思ってた。

C問題は想定解法ではないにせよ他の情報を入れる前に追加20分弱でACしてるし、D問題も方針気付けば*2十分出来たし、頭が固いことをこれでもかと突き付けられた心境。やってる問題のclarが出たらよく読みましょう。

A問題: ABC321-A 321-like Checker

atcoder.jp

とりあえず文字列を先頭から走査して単調減少してなければ処理打ち切り。もうちょっとオシャレになるんでないかこれ。

B問題: ABC321-B Cutoff

atcoder.jp

とりあえず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 というか解説コードもこんな感じの方針ぽいし、こっちの方がやってることが分かりやすい。

(upsolveコード) atcoder.jp