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

脳log[20200820] AtCoder Beginner Contest 175/D 問題 Moving Piece



2020年08月20日 (木)

最終更新: 2020-08-24T19:08+0900

[AtCoder] AtCoder Beginner Contest 175D 問題 Moving Piece

コンテスト時間中には解けなかった。昨晩から苦しんで夕方に初の AC をもらった>「自分の提出

 最初の提出 #15953114 (RE / TLE)

バグが2種類あったけど方針は間違ってなかった。

 バグ1:K が各巡回グループ(配列 A の要素)の要素数より大きいときの端数(K%A[i].size)の扱い。

巡回グループの部分列(スコア数列)の和が最大となるときを考える。部分列の最大長が K%A[i].size 以下となる範囲で和の最大を求めるより、一周少なく回って(A[i].sum 1個分のハンディを背負って) K%A[i].size 以上 A[i].size 以下の長さで和の最大を求めた方が得する場合がある。

RE の直接の原因は、最初はゼロ除算を疑ったのだけど、Array#take の引数 k-1 が負になることだった。その値の出所が K%A[i].size。

 バグ2:1以上 K 個以下の連続する部分数列のうち和が最大となるものの求め方。

バグというよりパフォーマンス問題。Array#product で総当たりをしたので、間違いはないが時間がかかりすぎた。バグらせずに時間内に求める方法が最後までわからなかった。

 最初の AC #16057773 (729 Byte / 77 ms)

やっとバグ2がとれた。総当たりの方の、間違いではないが時間のかかる方法と答えをつき合わせてデバッグをした。

こうやって振り返ってもさっぱり参考になることが書いてないね。実装が難しかった、しかない。

 Ruby によるすべての提出(実行時間昇順)

現在の2番目のタイムが 95 ms。区間の最大値ということでセグメントツリーの使用は一応考えたんだよ。だけどこのときのこれが頭を離れなかった>「追加する要素との大小関係によって、待ち行列の末尾から、永遠に最大要素(最小要素)としての順番が来ない要素を追い出す」。おかげで 77 ms。

理想的にはこんなふうにすっきり鮮やかに解きたいね>提出 #16033967 (581 Byte / 175 ms)

普通に累積和の配列から k 要素を切り出して最大値を取り出してる(ss[_1 + 1, k].max)。回路長の3倍の長さの累積和配列を用意してるのがよくわかっていない工夫か(ss = (1 .. 3*l).each_with_object([0]){|j, o| o << o.last + Cs[lp[j%l]]})。

ss[l] が回路全体のスコアの和。0...l の範囲の1点を始点にして長さ k(+1) の部分列を切り出す。k = mi[K, l + K%l] だから、最大で [l-1+(l+l-1)+1] の要素にアクセスする。長さは 3l 必要。 ma[0, ss[l]] によって回路全体のスコアの和が正か負かの場合分けを省略している。

Array#max を分岐と見ることもできるかもしれないけど、場合分けをしてそれぞれに固有のスペシャルな式を書くより、Array#max, Array#min を含んでいようとも1つの統一された式を書きたい。実に自分好みのスクリプト。「if 文が嫌いである。(20181029)

そうだそうだ、自分は長さ k の部分列の始点を負のインデックスにすることで仮想的に配列の長さを倍にしたのだった。小賢しい。まあ、それでは長さ 2l にしかならないから、3l が必要な「場合」は配列の加算(a+a)をしている。このやり方をとる限り場合分けを解消できないね。