脳log[20250323]

2025年03月23日 (日) [AtCoder] 今日は AtCoder Regular Contest 195 (Div.2) があった。配点は 4-5-6-7-9。３問解ければいいなあという配点。■A 問題 Twice Subsequence。他の人の解答を見ると、前から作った列と後ろから作った列を比較しているものが多かった。自分はというと、前から部分列を作りながら、もうひとつ、異なる選択をした場合の列(のうち最善のもの)を同時に作っていた。提出 #64134048 (AC)。二分探索があるからたぶん効率が悪い。■B 問題 Uniform Sum。まず A 数列と B 数列から -1 を取り除く。-1 の数の合計が、好きな和を作れる要素の数になる。だから -1 が A/B 合わせて N 以上あるなら答えは必ず Yes になる。M=N-(-1 の数)>0 として、M というのは A 数列と B 数列を組み合わせて同じ数を M 個以上作れたら答えが Yes になるという数字。和を固定したら A 数列と B 数列を組み合わせていくつその和を作れるかは線形時間で数えられる。でもその和の候補が N^2 通りあるなら全体は N^3 であり、N≦2000 だから３乗は通らない。TLE×38、TLE×12。通らないのはわかっていたけど終了時刻が迫っていたのです。終了後に A 数列と B 数列の組み合わせを全列挙する解答を考えた。全列挙は２乗なので許されている。列挙した和を集計して最も多く作れる和を選ぶだけ！ 提出 #64144851 (AC)。22 行目の集計部分がちょーっと複雑で長いけどちょっとだけ！ なんでわざわざ下手な数え方をして TLE を出していたのか不思議だね。あとサンプル３が親切に教えてくれるけど、和は A 数列の最大値と B 数列の最大値と同じかそれより大きくないといけないという条件があるので、フィルタリングを忘れない。■C 問題 Hamiltonian Pieces。赤い駒も青い駒も４を単位として輪っかが作れる。だから４で割った余りをどう組み合わせるか、16 通りの場合分けをがんばった。WA×23、WA×13、AC。■■■B 問題で和の集計について何をごまかしたかを書く。A 数列に２が２つ、B 数列に３が３つあるとき、直積で列挙した和には５が６個現れる。実際に作れるのは２と３の少ない方である２個だけ。これに対処するためにまずは２つの２を (2,2)、３つの３を (3,3) と集計したあとで直積を列挙した。得られる要素は ((2,2),(3,3)) であり、５が２個作れることがわかる。和として５になるものは他に ((1,x),(4,y)) などが考えられるけど、和を１つ選ぶとき、(2,2) と (1,x) が実はペアを変えただけの A 数列の同じ要素の再利用だったり、(3,3) と (4,y) が B 数列の同じ要素の再利用だったりすることはないので、問題は解決している。そういうことを 20 から 22 行目でやっていた(tally, product, group_by とか sum{ min } とかで)。