最終更新: 2021-03-12T19:59+0900
まだ AC してない。(←その後 AC)
前回の日記(20200905p01)で解いた問題と構造は同じ。一番大きな違いはグリッドの大きさで、こちらは制約上の上限が 200000×200000 だから１マスずつの処理では間に合わない。
そこは何とかなって今は上限20万回のループの中で、上限20万要素からの二分探索が２回と、上限20万要素からの最小値検索を１回行っている。配列からの最小値検索が線形時間なのが明らかにまずいんだよなあ。実はループの中で配列のスプライシングをやってるのもまずくて、まずいのが２つ組み合わさって手がつけられないんだなあ。
問題のイメージが掴めてきた(今です)。H 枚の板が上から順にやや右下がりで設置されていて、最上段では横一列に並んだ W 個の蛇口から水が流れている。k 段目で注目すべきは水が落下している位置(複数)と、そこに流れ込む水流のうち落下点に最も近い蛇口がどれか。蛇口と落下点を結ぶ線はどれも交わらない。
蛇口と落下点の距離が最小となるものを効率的に見つけるデータ構造がわからんのだよなあ。
あ、TLE が２つ減ったのは nmin, rmin の導入効果。「蛇口と落下点の距離」ごとに数を数えておいて、数がゼロではない距離を小さい順に検索する。距離は増加する一方だから検索範囲は狭まっていく。
今回のポイントは r を可変長から固定長にしたこと。可変長のときの r のサイズは W から減っていく一方だったのだけど、固定長だと最初から最後まで W(+1)。それでどうして速くなるのか。
r の中身について。これまでは落下点と落下点までの横移動コストを記録していた。今回は落下点は(固定長)配列の添字となり、配列の中身に蛇口の位置を記録した。落下点までの移動コストは計算で求まる。
ここでトリック。落下点と蛇口の位置関係は「蛇口<=落下点」で決まってるので、「添字<中身」の場合を、落下点を見落とさずに配列のスキャンを安全にスキップするための情報とした。
Ruby で提出してると AtCoder Problems で確認できる Shortest Code の数がいつの間にか増えている現象がある。この提出が(いまのところ)そうだし、巨大企業(20200607p01)もそう。
AC 一番乗りである。C++ は甘え。まあ、Python は普通に AC がいくつもあるんだけど>「Python によるすべての提出」
見事なまでに変わらず。スキップ情報を UnionFind と同じように深さ優先探索で貪欲に求めて書き込むようにしても、やっぱり変わらないだろうなと思ってる。
最終更新: 2020-12-01T21:25+0900
今週は ABC がないようなので精進である。D 問題が「コンテスト時間中には解けなかった」ので E 問題は問題文を読みさえしなかった。
一行ずつ左から処理するにあたり保持するデータを vs = [0]*4 と定めたあとは、特に詰まるところはなかった。つまりそこで詰まったということであり、一番のお楽しみポイントだったということ。あるマスにおける状態と、状態から状態への遷移が、４要素の配列でまかなえることの発見が。
今のところ２番目の提出より倍くらい速いみたい。だけど書き方による違いかもしれないね。
この人の名前は AtCoder を初めて日記に書いた 20190907 のこの部分(20190907p01.05)で初めて目にした。このときも Python で一、二を争うくらい速くて、同じくらい速い他の複数の提出から参考にしたと参照されていた。
参考にできるところがあるだろうか。
自分のスクリプトで気になっているのが r0[c] = vs.max と書いた部分で、長さ 4 の vs 配列のうち 1,2,3 番目は基本的に昇順ソート済みなのだけど、0 番目にイレギュラーが飛び込んでくるせいで vs[3] や vs[-1] とは書けずに vs.max と(４要素とはいえ)配列を走査するほかなくなっている。
up = dp[i - 1][j][3] for w in range(4): dp[i][j][w] = max(dp[i][j - 1][w], up)
上のように、隣の行から値を引っぱってくるときに最大４要素を更新すればすべてソート済みであるとして末尾の要素を最大値として取り出すことができるんだけど……
もうわからぬ。
違いは入力 RCV を配列に記録するかハッシュテーブルに記録するかだけ。速くてメモリ食いが配列。遅い方がハッシュテーブル。要素数が少ないときはメモリ食いなのもハッシュテーブルの方なのであって、(メモリと GC が気にならない限り)いつでも配列を使っていきたいんだけど、この問題について言えば、R×C に比べて K がかなり少ないみたい。制約が「1 ≤ K ≤ min(2×10^5, R×C)」だから、最悪の場合が 900 万になるか 20 万になるかという違い。
ところで、いくつか見た感想なんだけど、作業配列は C+4 要素で十分だと思うんですよ。C×4 でも C×4×2 でもなく。入力を記録する R×C サイズの配列の前では霞んでしまう違いだけども、numpy の場合のパフォーマンス特性はわからないけども、要素の更新量は確実に減る。
Python で一番速い提出 #16084621 を読んだ。コンパイル済みのバイナリを書き出して実行するなら Python である理由がないじゃん、と思ったんだけど、元になった Python のソースをちゃんと読めるようにしてくれている。コンパイル前のソースが Python なのだった。
長さ C の作業配列が昇順ソート済みだという特性が活用できていなかったことがわかったので、それを踏まえたコードに。あまり速くはならず。結局 R×C 回配列を更新するところは変わりがないから。
配列を昇順ソート済みにするための書き込みを省いて、配列の重複のない範囲から最大値を抽出するだけにすれば良くなると思った。倍遅くなってメモリ消費も激増した。むしろ逆で、予想外のメモリ消費がスローダウンを招いた？ Array#[] か Array#max に何かある？
vs[0] = [vs[0],r0[c0..c].max].max # r0 に関わらない処理 r0[c] = vs.max
だったものを
vs[0] = [vs[0],r0[(c0..c).max_by{|i|r0[i]}]].max
# r0 に関わらない処理
r0[c] = vs.max
に書き換えたところ、１つ前の異常なメモリ消費、異常な実行時間だったものが、２つ前よりメモリも時間もやや悪いという、予想の範囲内の結果に収まった。
いや、悪くなってるのはがっかりなんだけど、１つ前の悪くなり方はやはり尋常じゃなかった。配列に最大値を聞くのではなく、添字の範囲を使って配列の最大値を求めるという回りくどいやり方より遙かに遅かったのだから。
素直なやり方で予測可能な結果が出るなら速かったりしないかなあ。
困ったときのセグメントツリー。もう３回目の実装なので空で書いてバグも無し(でも一応内部データを目視するテストはした)(１回目と２回目は空で書いてバグだらけ)。メモリ参照の局所性なんて関係ないハードウェアから遠い言語でできる悪あがき。今のところのベスト。こんな作業ってアルゴリズムひとつで桁違いの差をつけて置いて行かれる類のものだ。楽しくはあるけどこれで終わり。
@l の利用場所すべてで @l+1 って書いてるから @l の定義から -1 を削っておけば良かった。
* コンパイル済みのバイナリ展開とか。
i <=> 0 で代用できる。メソッドであってほしいものと演算子で十分なものと、なんかちぐはぐだね。■<=> (Spaceship Operator) についてビャーネさんが何か言いたそうにしていたのをどこかで読んだ。Ruby での存在意義はこの１メソッドを定義するだけでクラスを Comparable にできることだと認めてはいる。でも C++ では何を追加しても、互換性を保って追加をする限り、煩雑さを増すことにしかならないだろう。■Uniform Function Call が一番楽しみだな、C++ に導入されるとしたら。シンタックスの統一はテンプレートの適用を拡大するし、メンバ変数を使用しないアクセサリメソッドをグルーピングのためだけにメンバ関数にするような暴挙を阻止できる。最終更新: 2021-10-24T17:45+0900
読んだ眺めた>「競プロerのための群論 (swapと順列と対称群) - little star's memory」
数学の用語で何か抽象的なことを言ってるなーということと、Swaps と Moving Piece の２問(だけじゃないけど)が取り上げられているということはわかった。
Moving Piece は先日解いたので(20200820p01)、以前解けなかった(20191111p01) Swaps も解ける気がした。
もちろん今日も AC に至るまでに WA を出した。それも前回と全く同じ入力に対して同じように誤った答えを出した。前回書いたスクリプトはひとつも参考にしなかったにも関わらず、構成も結果も瓜二つなのは、書いた人間が同じだからですね。同じところに留まっている……。
前回と違ったのはテストケースが利用できたこと>「atcoder_testcases > nikkeiqual_2019 > C」
今回のような Yes/No 問題の場合、間違った方法ででたらめな答えが出ても２分の１の確率で AC になってしまいデバッグが捗らない。そのような場合に(テストケースなしでも)使える手法をひとつ思い付いた。
スクリプトの真ん中に sleep (※引数なしなら永眠)を仕込んで、前半部分の Yes/No 判断に誤りがないかを確かめた。結果は TLE と AC のみだったので、前半部の判断は間違っていない。
予想外の WA (TLE なし)だった。これは後半部の No を sleep に置き換えたものなのだけど、１つも TLE がなかった。１つもないというのは(入力とバグり方がコラボした)偶然の結果なのだけど、偶然でもなんでも無条件 Yes は明らかなバグだ。
こんな感じで TLE(sleep) や RE(ヌルポ、０除算、変数名タイポ)が Yes/No ではない第３、第４の答えとしてデバッグに利用できると思った。こういう(アナーキーな)考え方ってゴルファーが得意としてそうだよね。常識だと思ってそう(違うんですよ)。
わかってみれば些細なことで、思えば去年もインデックスの扱いに確信が持てずに試行錯誤をしていた。どうして B 数列が予めソート済みではないという、そのひと手間で穴にはまるのか、何度でも。
つまり、A 数列の初期配列と B 数列の初期配列。A 数列のソート済み配列と B 数列のソート済み配列。A, B 両者の扱いが対等なこれら４つは脳みその中に居場所が確保されていた。しかし、B 数列の初期配列をソート済みとする、と条件を整えたときに A 数列の初期配列がどうなるか(ソート済みではないし、元の初期配列とも異なる)、という概念が脳みそからすっぽり抜け落ちていた。A, B の対称部分に気持ちを良くして、差異に向ける目がなかった。去年も、今回も(初めは)。
「去年の WA」を完成させたもの。必要以上に慎重だった(見極めが甘く無駄だった)二分探索がないぶん、冒頭の AC 提出より速い。
前回の日記に全部書いてある(あれで全部だった)。ひとつだけ付け加えるなら、「逆の例は、B 数列に重複する値が存在する場合や、B 数列の最小要素以下の要素が A 数列に複数ある場合など」の「など」でごまかした具体例の３つ目。
ソート済みの B 数列に異なる値を持つ隣接要素 B[i] と B[i+1] があって、B[i] < A[k] <= B[i+1] となる A[k] が存在しないときも、A 数列のすべての要素にあるべき位置が存在するとは言えなくなる。(A 数列がソート済みなら B[i] < A[i+1] を確かめるだけでいい)
最終更新: 2021-08-15T23:54+0900
余勢を駆って前回２つの WA であっさり引き下がっていた D 問題に再挑戦した。これも C 問題と同じ 600 点問題。
実は区間の片端に着目した貪欲法で解けるんですよ、というのが目から鱗だったスケジューリング問題そのままだった。どこにそう書いてあったかは忘れた*。
前回の WA 提出 #8424473 を見ると、今と同じことは考えていたことがわかる。C 問題の場合にも言えるけど、そこで結果を分けたものが何か。考えたことを過不足なく言い換えることと、バグなくコードに置き換えること。それができるかどうか。
それはどうやったらできるようになるんですか？ という問いは、どうしてそこで間違えたんですか？ という問いと対になる。わかりませんよ。ワーキングメモリが足りないんじゃね？(テキトー) こういうとき脳筋は手を動かして慣れるしかない。そうすればより少ない脳のリソースで解けるようになったり、型通りの手法で解けるようになったりして、うっかりや見落としで間違えることがなくなる(という期待)。
区間のどちら端に着目するか。冒頭の AC 提出では L のソート順に処理していたが、「前回の WA」では R でソートしていた。それを完成させてみたら、冒頭の AC 提出で使用していた Array#slice! と Array#insert という、配列に対して呼び出すにはやや気が引けるメソッドが、Array#pop と Array#push という配列に相応しいメソッドに置き換わっていた。二分探索も３回から２回に減っている。Swaps の場合もそうだったけど、AC に至りさえするなら部分的には過去の方が優れてるのなんでだろう。
グラフとか最短経路とかコスト０の辺を張るとかわからへんねん。
R でソートするバージョン(#p02.02)。
RC を二分探索し、最初に L かそれより後ろに到達する要素を見つける。より遠くに到達する要素はより高コストなので「最初」を見つける。
見つからない場合は断絶があるということでありパスする。R の昇順に RC に要素を追加しているのであり、今後 [L,R) の区間に到達する辺は現れない。R に到達する辺があとから追加されることはあるが、C が負ではないのでパスで良い。
ひょっとしたらこれも DP (動的計画法) の一種かもしれないけど、わからんけど、自分が頑なに DP の用語を使わないのは、それを言ってもメリットがないから。
一行ずつ左から処理するにあたり保持するデータを vs = [0]*4 と定めたあとは、特に詰まるところはなかった。つまりそこで詰まったということであり、一番のお楽しみポイントだったということ。あるマスにおける状態と、状態から状態への遷移が、４要素の配列でまかなえることの発見が。
これもそう。DP の核心は何を記録して遷移するかであり、それがわからないのに、「あ、これ DP だ」ということを言っても問題が解けない。むしろそれを言うことで何かわかったつもりになることが目眩ましになって問題に集中できない。過去に何度かそういう失敗をして、DP だということは言わないことにした。dp という変数名も自分にとって何も説明していないので使わない。
DP の一語でなく、配る DP、集める DP まで区別できるとまた違うのかもしれないけど、自分はそれらを識別しない。
どちらがどちらと同じと言うかはまあいいや。
速いでそ>「Ruby によるすべての提出」 それ以前に提出が少なすぎる……。
* 蟻本(初版第１刷)の43ページ「区間スケジューリング問題」だった。
最終更新: 2020-08-26T10:30+0900
ある時点でのファイルへの書き込みアクセスの可否を保存し、エディタの「上書き禁止モード」を体現するクラス。CDocLocker::IsDocWritable が第一義。
排他制御を行うのに書き込みアクセスは必須ではない。しかし書き込みアクセスができることをエディタは条件にしている。自身が書き込みできないファイルに対して「お前らこのファイルは俺のものだぞ。勝手に読んだり書いたりするなよ」と主張することのナンセンスを考えれば納得できる。
書き込みアクセスがないなら排他制御はやめとこか、くらいの温度感なので、CDocLocker.IsDocWritable() に基づいて判断を下している。今現在の瞬間の書き込みアクセスを条件にしているわけではない。
「上書き禁止検出時は編集禁止にする」というオプションによって、上書き禁止モードがより制限の強い編集禁止状態へと格上げされる。
(別のファイルとして保存するために)上書きできなくても編集はしたいという考えも、上書きできないのなら編集できても意味がないという考えもどちらもあるだろう。そこはどちらでもいい。
これは CDocLocker.IsDocWritable() の値が変化しうるタイミングと同義。次のようになっている。
※ 最後だけは「書込禁止の監視を廃止（復活させるなら「更新の監視」付随ではなく別オプションにしてほしい）
」というコメントとともに無効化されている。
上書き禁止モードの変化が排他制御を試みるかどうかと編集禁止モードのオンオフに影響するのはすでに書いた。
すでに編集できない状態ならファイルロックのメッセージを表示しない」という再メッセージ抑制策がとられている。
２組の比較を挙げたけども、どうにも扱いがちぐはぐで行き当たりばったり感がある。上書き禁止がいつ検知・再検知されるのか、すっきり説明できるようにしたい。
オプションにより編集禁止モードと連動する。ファイルを開いたときに上書き可否を検知し編集が禁止されるのは、ユーザーの選択でもありなんの問題もない。
しかし一度編集を開始したファイルに対して、アンドゥバッファが溜まり更新フラグが立ったファイルに対して、先ほど挙げた再検知タイミングを挟んで、上書き不可が検知され編集が禁止される事態が起こりうる。これはユーザーの望む動作であろうか。いたずらにユーザーの操作を制限しているだけではないのか。
ビューモードをオンオフするタイミング次第でエディタが編集可能になったり不可能になったりするようなことを誰が望んでいるのか。結局のところ編集禁止の根拠となっている上書き禁止モード、つまりは書き込みアクセスができたかどうかは、過去のある時点ではそうだったというだけなのに。
ファイルの保存をしようとしてその直前のテストで書き込みアクセスが拒否されたところに、こういうコメントがあるのがおもしろい。「たとえ上書き保存の場合でもここでの失敗では書込み禁止へは遷移しない
」
上書き禁止モードを体現する CDocLocker.IsDocWritable() の値が変化しうるタイミングをいくつかすでに挙げたけども、実際に上書き保存をする直前というタイミングがそのリストから明示的に除外されていることになる。
実際上の理由はわかる。最初の上書き失敗を理由にして２回目以降のトライを勝手に諦めてもらっては困るからだ(上書き禁止モードで上書き保存は選べない)。
上書き禁止モードが何ではないのかがよくわかるコメントではないか。
なお、自動で発動する上書き禁止モードをビューモード相当の制限に格上げすることができる(「上書き禁止は編集禁止」オプション)。
上書き禁止モードを仮にユーザーがオフにしたところで、上書きできないときには上書き保存に失敗するだけのことだ。ついさっき挙げた、この失敗から上書き禁止に遷移はしない、というコメントの状況が発生するだけのことだ。
ビューモードほど強い制限でなく、ファイルシステムからの要請でもなく、ユーザーが自分の意思でこのファイルには上書きしないと宣言するモード(上書き禁止モード)があってもいいのでは？
派生して、ビューモードをオフにするタイミングで書き込みアクセスの可否を再判定して、上書きモードのオンオフを更新する現在の挙動についても再考する。
上書き禁止モードは結局のところエディタやユーザーの選択の結果でしかない。書き込みアクセスが拒絶されたとて、そうあらねばならないモードではない。
ビューモードのオンオフ、上書き禁止モードのオンオフという操作によりユーザーが３つのモードを自在に行き来する状況を想定すれば、ビューモードのオフは編集モードへの移行であるべきでは？
ファイルを開いた際にユーザーの便宜のために自動で上書き禁止モードやビューモードを適用する機能があっていい。今は何が違うかというと……
せっかくなので理解した内容を長々書いてきたけどもそちらは本題ではなく、そもそもは標記の現象のための作業をしていた>コード。それで何か嬉しいことができたかというとそういうことはない。現在のステータス……
最終更新: 2020-08-24T19:08+0900
コンテスト時間中には解けなかった。昨晩から苦しんで夕方に初の AC をもらった>「自分の提出」
バグが２種類あったけど方針は間違ってなかった。
K%A[i].size)の扱い。巡回グループの部分列(スコア数列)の和が最大となるときを考える。部分列の最大長が K%A[i].size 以下となる範囲で和の最大を求めるより、一周少なく回って(A[i].sum １個分のハンディを背負って) K%A[i].size 以上 A[i].size 以下の長さで和の最大を求めた方が得する場合がある。
RE の直接の原因は、最初はゼロ除算を疑ったのだけど、Array#take の引数 k-1 が負になることだった。その値の出所が K%A[i].size。
バグというよりパフォーマンス問題。Array#product で総当たりをしたので、間違いはないが時間がかかりすぎた。バグらせずに時間内に求める方法が最後までわからなかった。
やっとバグ２がとれた。総当たりの方の、間違いではないが時間のかかる方法と答えをつき合わせてデバッグをした。
こうやって振り返ってもさっぱり参考になることが書いてないね。実装が難しかった、しかない。
現在の２番目のタイムが 95 ms。区間の最大値ということでセグメントツリーの使用は一応考えたんだよ。だけどこのときのこれが頭を離れなかった>「追加する要素との大小関係によって、待ち行列の末尾から、永遠に最大要素(最小要素)としての順番が来ない要素を追い出す」。おかげで 77 ms。
理想的にはこんなふうにすっきり鮮やかに解きたいね>提出 #16033967 (581 Byte / 175 ms)
普通に累積和の配列から k 要素を切り出して最大値を取り出してる(ss[_1 + 1, k].max)。回路長の３倍の長さの累積和配列を用意してるのがよくわかっていない工夫か(ss = (1 .. 3*l).each_with_object([0]){|j, o| o << o.last + Cs[lp[j%l]]})。
ss[l] が回路全体のスコアの和。0...l の範囲の１点を始点にして長さ 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 を含んでいようとも１つの統一された式を書きたい。実に自分好みのスクリプト。「if 文が嫌いである。(20181029)」
そうだそうだ、自分は長さ k の部分列の始点を負のインデックスにすることで仮想的に配列の長さを倍にしたのだった。小賢しい。まあ、それでは長さ 2l にしかならないから、3l が必要な「場合」は配列の加算(a+a)をしている。このやり方をとる限り場合分けを解消できないね。