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)をしている。このやり方をとる限り場合分けを解消できないね。
q,r = 7777.divmod(101) みたいに多重代入で受けると、多重代入が遅いせいで(20200428p01.08.01)密かに期待するパフォーマンスメリットが相殺されてしまう罠がある。最終更新: 2020-09-03T17:14+0900
時間内に B 問題までしか解けなかったので今日の日記は C 問題。AGC の C なら解けないのは残念ながら当然だけど、昨日あったのは ABC で、C 問題は 300 点問題だ。嘆かわしい。
解るような気がしながら解らなくて、でもやっぱり解りそうな気がするという堂々巡りを繰り返すだけで考えがさっぱり焦点を結ばなかった。具体的には 7,77,777,7777,... という数列を規定するルールを、どのように捉えれば解きやすいか考えあぐねていた。
布団の中でも考えていて眠る前に AC が出た。だけどまだ解らない。このプログラムが停止するかどうかさえ自分には不確かだ。
たどり着けるならK回目までにたどり着くので「K回目までにたどり着かなかったら到達不能と判断」でもよかったか
うん、これが解らない。
K の余りをとるなら余りの種類が K 種類しかないのはわかる。同じ余りが出たら以降が循環ルートに入るのもわかる。K+1 回目以降の余りが必ず既出なのもわかる。わからないのは、自分が提出したスクリプトでははっきりとわかる形で K の余りを求めていないところ。たぶん変数 k に配列７の要素( 0 以上 9K 以下の値)を足して 10 で割ったあとの k の値がそれっぽいから、この k の値が既出かどうかをチェックする方法があると思う。
でも問題に用意された入力について言えば、答えが出そうな K からは必ず答えが求まっているようではある。それは必然なのか偶然(出題者の作為)なのか。
他の人の提出を見ると明らかに自分だけ*おかしなことをしている(嬉しい)。え？ 停止条件さえ判れば(※自分には判らない)、数列を順番に K で割るだけでいいの？ (※桁が大きくなりすぎるので余りにだけ注目する必要はある)
たぶんやっていることは実質的に同じで、一方が難読化されているというだけなのだろう。問題の理解がこんがらかっているからスクリプトもそうなる。過去に２回くらい日記に書いてるけど、アホの子は自分で問題を難しくする。(問題の本質、抽象化された実質が理解できないから、無駄や回り道がなくせないという意味)。
「レプユニット数」という概念があるらしい>「[AtCoder] ABC 174 C – Repsept | ヤマカサの競技プログラミング」 そういえば問題名が Repeat でも Respect でもなく Repsept だ(今初めて読んだ)。
この問題の２つの解法というのは、逆元とか割り算を含む式の余りについて理解を深めるチャンスだという気がするんだよね。何か関係がありそう。以前解けなかった問題>「階乗が法外な大きさになるので余りを答える問題。割り算を含む式の余りが求められなかった。」
(別の問題の解説だけど)これも理解の手がかりにできそうな雰囲気。雰囲気しかわからぬ……
公式解説は累積和だね、横一列を1回の掛け算で済ます方法
僕の解法は「単純に2で割れないから逆元を使った難しい解法になる」と言われてた
抽象的に考えすぎて難しいだけでは。11ぐらいの小さい数で試したことがあれば難しくなく思いつけると思う
* この提出はお仲間かな。 https://atcoder.jp/contests/abc174/submissions/15654939
♭ nishio「循環ルートに入る」＝「kの1の位が偶数か5」ということみたいです、追記しました。
♭ ds14050お知らせありがとうございます。しかも代わりに考えていただいて^^。 循環する場合に「B-AはKの倍数」からの「..