脳log[20211106]

2021年11月06日 (土) [AtCoder] 精進。ARC070-D「No Need」(ギリギリ黄 diff)。N と K の上限が 5000 なんだけど、O(NK) を通すために C++ で殴ってしまった。提出 #27059260 (AC / 106 ms)。なんという甘え。なんという芸のなさ。しかし 11 個目の黄 diff AC であることに変わりはない。ないったらない。■Ruby でのすべての提出を見ると、しっかり Ruby で通している人がいますね。1241 ms、1010 ms、14 ms。これで全部。98 Byte/14 ms の提出は頭おかしいと言わざるを得ない。なんだよそれー。■自分の方針。ある要素に注目したとき、それ以外の要素を組み合わせて作れる和にある要素を足して初めて K に届くようなケースが１つでもあるなら、その要素は不必要ではない。それを左右からの DP で。■入力をソートしてみたりもしていたんだけど、大小関係を要不要の判断に活用する方法が思い浮かばなくて消してしまっていた。Ruby での AC 提出はどれもソートしている。大きい要素から順番に K 未満の和の集合を作っていくことを考える。和のどれかに現在の要素を加えて K 以上になったなら、その要素は不必要ではない。同時に、処理済みの要素(現在の要素と同じかより大きい)も現在の要素と交換することで不必要ではないと判断できる。最初の判断に利用した和の構成要素であったかどうかには影響されない。和の集合だけど、K 未満で K に一番近いものを１つだけ覚えておくのでいい。K に１足りないだけなら値が１の要素も必要にできる。７割８割くらいまではわかってたんだけどなー(負け惜しみ)。■K 未満で K に一番近い和だけど、要素を大きい順に処理していることで自然に求まるかと思ったけどそんなことはないよね。DP が必要。提出 #1172583 を理解するには考察が足りない。■N=4; K=100; A=70,50,49,1 という入力に対して、左右から DP をする自分の提出と、ソートして二分探索して両端をメモして DP の回数を抑えている(っぽい)提出 #4480840 が 0 を返しているところ、提出 #1172583 は 1 を返す。14 ms で Ruby 最速の提出は嘘解法ということでよろしいか。■Ruby で通った！ 提出 #27128108 (AC / 1997 ms)。AtCoder では TLE を確定するまでに３回くらい実行を繰り返すというような話を聞いたけど、2026 ms みたいに TLE だけど実行打ち切り(22xx ms など)ではなさそうなタイムの時は、再提出することで試行回数が増やせます。だけど提出直後の２回目の提出は、うっかりミスを訂正するよくある提出パターンとして許されているけど、それ以上の連続提出は規制されているそう。DoS 攻撃になっちゃうからね。■公式解説を読むと O(NK) と O(NKlogN) が想定解であって、O(NK) は速い方だった。ちょっと雲行きが怪しいぞ。自分がやってたのは O(NKK) の三重ループじゃあないですか(それでも通ってしまう C++ の犯罪性の高さよ)。でも Ruby のは二重ループだからっ。