ABC 321 （2023/09/23）
見ずらいので，問題番号の上は1行空白を開けてください
〇A問題
Yuto.icon やるだけ
Kaplam.icon上の桁から問題ないか見ていくだけ
yuichang.icon10で余り取って割ってく
CarpDay.iconKaplam.iconさんと同じかな？文字列のまま読み込み，左からチェック．
おたふく.icon 何故か難しく考えている。
TK.icon文字列でループして、intにキャストして下がってるがチェック
〇B問題
Yuto.icon 足す数を小さいのから順に全探索
Kaplam.iconmaxとminを一旦加えないで場合分けでって感じで組んだら入力例2が合わず、無理やり修正してもWA3出たので全探索で
yuichang.icon解に対する二分探索でオーバーキル
CarpDay.iconソートして，追加する前での最低と最高を除いた点数（$ SSとする）を求めておく．最低＋$ SS ≧Xなら，追加する前で既に条件満たしているので0．$ SS＋最高 < Xなら，不可能なので-1．それ以外は追加数＋$ SSが最終スコアになるので，Xー$ SSが答え．
おたふく.icon ソートして、取ったスコアが最小になる場合に条件を満たすか、最小にも最大にもならない場合に条件を満たすか、最大になる場合に条件を満たすか、それでも無理なら-1と愚直に実装する。
TK.icon問題文読んでない。X以上じゃなくてイコールになるところを全探索で探していた。方針変えたりとかいろいろしたけど、そこじゃないっていうミスをしていた。
〇C問題
Yuto.icon 難しい．一旦飛ばしてDに行った．Dが一瞬で解けたので戻ってきたけど分からん．しばらくExcelで遊んでたけど無理そうだったのでEに行った
https://scrapbox.io/files/650eeb7e07213a001e48a8cd.png
yuichang.iconsetでコネコネする。時間がない
Kaplam.icon上の桁から小さくなっていく数字全部入れたリストを再帰で作ってsortして指定された場所を見る
CarpDay.icon321-like numberを1桁，2桁，．．．と順に作成する．i 桁目を作成して総数が K を超えたら，i桁目の321-like numberをソートして，トータルでK番目の数を選択．i桁目を作成して総数がKを超えないときは，i桁目の321-like numberを使って，i+1桁の321-like numberを作成する．最近のC問題は「愚直に作成」が頻出で，解けないことが続いたので，やっとリベンジ．解説読んだ．大きな方針としては同じだけど，考察は解説の方がスマート（当たり前か）
おたふく.icon 11桁以上の321-likeな数は存在しないことはすぐに気付けたが、最初はYuto.icon同様に規則性を考えて、上手く計算する方法を探すも、良い方法を見つけられず。小さい順に321-likeな数を作っていっても計算量が大丈夫そうな感じがしたので、この方針で実装を試みる。当初の方針では非再帰のdfsで実装しようと考えるも沼り時間が溶ける。それからkaplam.icon同様に再帰でおとなしく実装するもWAが1件...。最初に勘違いして10桁以上の321-likeな数が存在しないとしていたことに気付き無事AC...。
TK.iconK番目のものをピンポイントで作成することを考えていたが、後から考えると全列挙できることに気づいた。しかも不等式にイコールがないから同じ数字も登場しないから組み合わせを使って後から実装。
〇D問題
Yuto.icon にぶたん+累積和． 見た瞬間解法が浮かんで，一発でAC出来た．最初 $ \sum a_i b_jを求めるのだと勘違いしていて（ただしくは $ \sum (a_i + b_j) ）少し時間を浪費してしまったのは反省．ここまでは順調．
yuichang.icon二分探索 累積和。
Kaplam.icon同上
CarpDay.icon二分探索には気付くが累積和に気付かず，2回TLE．やっと気付くが配列外参照で1回REののちAC．時間浪費．反省．
おたふく.icon コンテスト後に問題を解きました。bisectを利用することでPを超えるものが何個あるかを高速に判定できることには気付いたが、累積和を利用することで和を高速に求められることに気付くのに少し時間がかかりました。
〇E問題
Yuto.icon もう少しで解けそうなんですけどねぇ...
Kaplam.icon最初Kの条件よく確認せずBFS組んだら全然時間足りなくて、グラフの形使うのかと急いで組んだけど場合分けいっぱいでバグ取り間に合わなかった 追記：アルゴリズム間違ってた、難しい
CarpDay.icon完全二分木の特徴を使って，各クエリをO(1)で求めるのだろうけど，経験不足なのでスキップ．終了間近から挑むも時間切れ．最下層が完全に埋まっていないときの処理，Xが左側／右側による場合分けなど，実装しようとすると条件分岐が多数．もっと効率的な方法があるだろうから，諦めて解説見る．なるほど，勉強になります．
〇F問題
CarpDay.icon方針はすぐ定まるものの，途中のロジックに自信がないまま投稿し，懸命に祈って何とかAC．久々のF問題ACで，3桁ランクも久々です．
【追記】解説にあった「形式的冪級数」をメンバーの推薦もあったので少しWeb検索．ほとんど分からなかったが，数え上げ問題を解くのに役立つことは分かりました．面白い．（参考サイト）ただ，冪級数の係数をどうやってプログラム（特にPython）で求めるかが分からない．． おたふく.icon dpを考えるのはやっぱり楽しい。ナップサック問題 っぽいものを感じて、+の時の処理に気付けると-の時にどうしたら良いかを考えると上手くいく気がしました。F問題の中では取っ付きやすい問題に感じました。