脳log[20230409]

2023年04月09日 (日) [AtCoder] 今日は ABC297 があった。自分のすべての提出。コンテスト成績証。DEF 問題について書く。■D 問題「Count Subtractions」(灰！ diff)。数学問題苦手。でもまあ、エラトステネスのふるい……じゃねーや、ユークリッドの互除法の名前は忘れてたけどどういう処理かは精進(20191118p01, #8508807)のおかげで知ってますよ。Ruby 2.3 の頃は余り付きの pow メソッドがないから逆元の計算に苦労したのだ。■E 問題「Kth Takoyaki Set」(緑 diff)。N≦10 が特徴的な制約。10 個以下の数を重複ありで組み合わせて K 個の数を作りたい。効率的にソート列を伸ばしていく方法は。たとえば値を増加させるプロセスが１つだけなら、与えられたソート列と、処理済みのソート列の２本の配列を持って、２つの配列の先頭の要素を見比べて小さい方の値を取り出して処理して処理済みのソート列の末尾に追加することでソート列をどんどん伸ばしていける。それは 20190916p01.01 と 20220129p01.06 に書いた。今日の問題への応用は。(1)１本のソート列に 10 のプロセスが張り付いて次の値を提案する。(2)ふさわしい値をソート列の末尾に追加する。(3)次の値を提案するために各プロセスがソート列上を少し後ろに移動する。という感じ。提出したスクリプト８行目の while 修飾子は if 修飾子で十分だった気がする。提案した値が採用されたプロセスだけが添字を +1 するだけのはずだから。Ruby でプライオリティキューは定数倍の重さが致命的になりがちでできるなら避けたいところ。■F 問題「Minimum Bounding Box 2」(青 diff)。類題を何問か解いている。「Black and White Rooks」(20220306) と「AtCoder社の冬」(20211222)。だから処理の流れはわかったうえで、TLE にならないように同じ数え上げを省く効率化を間違えずにやることに専念して、１時間以上苦しんだ。全部を一度にやるのは難しいから、全然答えが合わなくてそれを痛感したから、愚直解を書いて答えを合わせてから、その式をにらみながらリファクタリングをするようにした。最初に行方向の数え上げだけを効率化して提出してみたけどきっちり TLE になったので、残ったわずかな時間で列方向の数え上げも効率化してぎりぎり(２つの意味で)時間内に間に合った。「けっこう制約が優しくて、ループ内で愚直にスキャンして掛けて足し合わせても間に合いそう」だった先の２問よりも厳しい。厳しいのになんで黄 diff より下の青 diff 止まりなのか。水色の自分が通しているからか。■E 問題が Cake 123 に似てるというツイートを読んだけど、自分はその問題は WA で投げ出している。これが次の精進候補かな。■■■@2023-04-12 F 問題。解説の方法でやってみた。提出 #40569324 (AC / 508 Byte / 812 ms)。なにこれ簡単。h×w の枠を H×W の内部で動かすとか、累積和で DP を高速化するとか、まるで関係ない。足して引いて足して割るだけ。なにそれずるい。■もうひとつの解説のやり方もやってみた。提出 #40569949 (AC / 644 Byte / 1081 ms)。この形は見覚えがあるなあ。AtCoder社の冬への自分の提出 #28054417 だなあ。こちらは枠を動かすステップがあるけどそれでもまだ簡単だなあ。ずるい。ループを通して相殺される足し引きを予めまとめておかないと間に合わないくらいの努力が要求されたんだよ、最初の提出(#40491985)では。