脳log[20230413]

2023年04月13日 (木) [AtCoder] 精進。20230409 に書いたように ABC123-D「Cake 123」(水 diff)。難しかった。ABC197-E「Kth Takoyaki Set」と似ているということで解法の見当がついた状態で挑んだけど、ひとひねりあって考えてしまった。制約を比較すると N の上限が 10 から 1000 へと増えている一方 K が 20 万から 3000 に減っている。列が３本あるのも違いだけど、それは最初に２本を組み合わせてソートして 100 万のソート列と 1000 の「値を増加させるプロセス」に転換できる。O(NK) が通る制約なのは同じだから、ここから同じ解法で答えが出る。じゃあどこに考え込む要素があるのか。プログラミングをする者の思考として共通部分を見つけて括りだしてまとめる傾向があると思う。100 万のソート列と 1000 のプロセスを組み合わせて K 個の値を大きい方から作り出す本処理を書いたとき、前処理で行った 1000 の列を２本組み合わせて 100 万のソート列を作り出す処理にも応用できないかと考えてしまった。一見できそうに思える。なんなら本処理よりも簡単にできそうに思える。というのも本処理では 100 万と 1000 を組み合わせるので迂闊に全体を一括して扱うと 10 億になって手に負えなくなる一方、前処理では 1000×1000 = 100 万なので雑に組み合わせて全体を一括処理して構わない。それなのに本処理と同じやりかたを前処理に適用しようとして N の３乗 TLE になりそうなことに気がついて、なんでそうなってしまうのか考え込んでしまった。■提出 #40551459 (AC / 267 Byte / 748 ms)。前処理と本処理を共通 M (マージ)関数にまとめることはできなかった。■Ruby によるすべての提出を見ると２桁 ms の AC がいっぱいある。自分の解法は ABC297-E の制約を見て考え出されたものであって、ABC123-D 向けには別の解法を採用すべきだったということ。ちなみに ABC297-E には他にプライオリティキュー解法と二分探索解法が存在している。自分が過去に ABC123-D で WA を出した解法は二分探索解法だった。もうすこし考えねばならぬ。■前処理で作成するソート列の長さを制限することができる。そうするとさっき書いたことに反して共通のマージ処理を使うことができる。２桁 ms の提出は長いものと短いものに二分できるみたい。長いものはプライオリティキュー解法で、短いものはソート済みであることを踏まえて賢く打ち切りながらの全列挙だった。