/ 最近 .rdf 追記 編集 設定 本棚

脳log[20210224] SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)/F 問題 Potion



2021年02月24日 (水)

最終更新: 2021-03-23T20:00+0900

[AtCoder] SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)F 問題 Potion

解説を読んで ABC をコンプリートしようシリーズの1回目。ABC192 で残っているのは F 問題。いわゆるポーションって portion とはスペルが違ったのね。

2回目があるかはわからない。1回目にして解説を読んでから2日間苦しんだ。DP だったんだけど、人類が扱うには次元が高すぎるのではないかな? 自分には無理。

 提出 #20468517 (AC / 614 Byte / 1451 ms / 18204 KB)

ソースコードの冒頭にも引用したけど、解説の要諦が次の一文。

dp[i][j][k] = i 番目までから j 個選んだときの和であって、mod C で k に等しいようなものの最大値

自分は最初これを次のように解釈した。

dp[i][j][k] = i 番目までから j 個選んだときの和であって、mod j で k に等しいようなものの最大値

微妙な違いがわかりますか? mod C と mod j の違い。うっかりミスではなく、理解できる範疇を超えていたから、これってこういう意味だよね、と一段次元が低い誤った理解しか生まれなかった。

引き回すデータ配列の構成を教えてもらってさえ遷移が書けるまで一日かかったんだけど、いざ完成したらこの微妙な勘違いのせいで時々答えが合わなかった。時々。答え合わせに使ったのは次のナイーブな解答スクリプト。N が 30 を超えると実行時間が現実的でないので生成する入力の N は小さめに。テストケースはまだ利用できない。

N,X,*A = $<.read.split.map(&:to_i)

p (1..N).filter_map{|c|
	k = X%c
	m = A.combination(c).map(&:sum).sort.reverse_each.find{|m| m%c == k }
	(X-m)/c if m
}.min

要するに、これを時間制限に収まるように書き直しましょう、という問題だった。それが難しい。

結局一度完成したと思ったスクリプトを囲うようにもうひとつループを重ねた。法が変わると余りは再利用できない。最初から目的地(C)を定めて j を変化させなければいけない。dp 配列の添字 k の上限は j でなく C である。無理だよ、明日にはもう自分でこの文が理解できないよ。


DP であることでナイーブな解答より有利になる点は次の2つ?

  1. j+1 個の組み合わせを生成するのに j 個の組み合わせ結果が利用できる。

    その際にキーとなるのが添字 i (「i 番目までから j 個選んだときの和であって」)。j 個の組み合わせ結果を i (1~N-j)によって分類しておくことで、j+1 個の組み合わせを作るのに利用できる。

    たぶんこれって DP のひとつの典型なんだと思うけど、配列の型を示されてさえこの種の遷移(何を残して何を再利用するか)を見つけるのに1日かかった。

    見つけた遷移は具体的には、「j を C まで増やしながら、ある j について i 番目の要素(A[i])を i の大きい順に考える。A[i] を採用しないときに dp[j][i] に対応する C 要素の配列は dp[j][i+1] のものと同じ。A[i] を採用するときは dp[j-1][i+1] に記録された C 個の値と組み合わせる」 i と j が解説とは入れ替わってら。

    dp[j][i] の値を作るのに dp[j][i+1] (最内ループの直前の値)と dp[j-1][i+1] (中間ループの直前の値の1要素)を再利用している。

    勘違いして見えていなかったのは、j=C であり j を 1..N の範囲で変化させる過程で各 j(C) に対応した答えが見つかる……のではなく、C=1..N について j を 1..C の範囲で変化させなければいけないということ。

  2. 組み合わせた結果の和を mod C で分類して最大の値だけを採用することで、無駄な組み合わせが省ける。
  3. あとはまあ、組み合わせる数は多い方が初期値の点でも経時増加量の点でも有利なので、ループを降順にして、途中で打ち切り条件を設定したりした。だけど special_xx.txt に類するケースがスペシャルな理由は、こうした打ち切りが無効なところにありそう。

  • 提出 #20486969 (TLE×11)

    主にイテレータを使って書き直したので遅くなるのはわかる。

    Array#min の代わりに Array#[] でダイレクトに最小値を取得するようにしたので、special_xx.txt 以外のケースでは改善している。

  • 提出 #20486969 (TLE×11)

    同じように Array#min を使うのをやめたのと、イテレータを使わず全て while で書いた。special_xx.txt 以外のケースで上よりさらに少し改善しているが、TLE は TLE。

    Ruby って整数演算が足す引く剰余大小比較まで、どれも同じくらい遅い雰囲気。演算コストに差がないなら演算子の数を減らす方がいい?

    でもどこに 800 ms も遅くなる要因があった? もう予測できない。

 提出 #20581154 (AC / 615 Byte / 1437 ms / 15868 KB)

平均すると最初の提出より1割弱タイムが改善しているけど、意味のある差ではない。

ベースはイテレータメインの提出 #20486969 (TLE×11)。

AC と TLE の分かれ目は4重ループの最深部にあった。

  1. 初期値を正の無限大ではなく nil にした。

    正の無限大は正常値として扱えるので記述が統一できるのだけど、むしろ異常値として nil や -1 や無限大を設定・検知して、ループをスキップするのが良かった。

    ところで、想定上限を整数で表現しようとすると 67 か 68 ビットが必要になる気がして採用できなかった。Float::INFINITY と Bignum の、どちらがいいともいえない。打ち切り条件が ×C ではなく ÷C である理由でもある。

  2. 余り(k)の計算は、k = m%ck-=c if c<=k よりも、「実行されないコードが最速」なのだった。負の添字を使った配列参照は組み込まれた機能でありコストは支払い済みなので、使い倒さなければ損になる。

いくつかの C について最小公倍数で余りをとれば、より外側のループで DP 配列が再利用できるのではないか。数列 A の偏りと C の組み合わせを調べれば、k が取り得る値が C 種類より少なくなるのを見抜けるのではないか。結局のところ、TLE の原因はおそらく X%C と A%C(の和) がまったくマッチしないせいで4重ループを最初から最後までフル回転させられるせいだと思うから。

 提出 #20639856 (AC / 870 Byte / 1167 ms / 24016 KB)

「いくつかの C について最小公倍数で余りをとれば、より外側のループで DP 配列が再利用できるのではないか」を実装してみた。話を単純にするために C が偶数の時に j=C/2; i=0 の DP 配列を C=C/2 の DP 配列として再利用した。

たとえば N が上限の 100 のとき、51..100 は普通に DP をする。1..50 は再利用配列を使用して DP をしない。限界は次の2点。

  • C が大きいときの方が DP の処理量が多いので、全長の下半分の節約は、処理時間にすると4分の1以下の短縮効果にしかつながっていない。
  • special_xx.txt 以外のテストケースでは打ち切り条件が有効に働くので、DP の節約効果が日の目を見ないどころかただオーバーヘッドを増やしただけになる。

 @2021-03-05 テストケース

ケースXX (素因数)A に含まれる 9999999 の数答えが見つかる C
special_01.txt52142908377193267103×4703×10764231956301
special_02.txt48620189947792921131×2719×18713×729445312
special_03.txt70227681074731923770227681074731923723
special_04.txt651020109319638361162011×231599×1735054934
special_05.txt61168850281850484182936769××737535968945
special_06.txt857415171960730822×11257×32587×11686759956
special_07.txt794433313787770441101×74910361×10500118167
special_08.txt515779426304609041101×510672699311494178
special_09.txt8962979337589569513×22769×1312161174929389
special_10.txt908429522499966622×24335153×1866496427910

N はすべて 100。数列 A の要素はほとんどが 10000000 で、0から9個が 9999999 という構成。

special_xx.txt が入力する数列 A の中に値の種類は1から2個しかなかった。C 個選んだ和の余りがとる値は、限られた 9999999 がいくつ含まれるかでしか違いが出なかった。つまり1から10種類。それでも C が 1..N の範囲で変化するうちに余りの数字(k)自体は変化していくし、X%C も変化するんだけど、どうやったらぎりぎり最後までマッチングしないような X が選べるんですか?