This file was generated by RubyGems. The application 'irb' is installed as part of a gem」 だけどこのファイルが更新されていたわけではない。たぶん
%USRPROFILE%\.irbrc に書き込むんだけど、どうやって色分けと補完を無効にするんだよ。……。IRB.conf[:USE_AUTOCOMPLETE] = false と IRB.conf[:USE_COLORIZE] = false を書き足して心の平穏を得た。俺は出しゃばりな機械を憎んでいる。■C 問題 2^a b^2。方針を定めるのが難しい。平方数を列挙したいと思ったけど、N の上限が 10 の 18 乗だからといって 10 の 9 乗までを列挙することはできない。それに b が 2 を含んでいるときに同じ良い整数を表す２通り以上の方法があって重複を除かなければいけない。そこで、b は 2 を含まない(奇数である)ということに決めてしまった。a を決め打ってから b の上限を二分探索で。■E 問題 Ringo's Favorite Numbers 3。扱う素数がいくつあるかをまず調べた。８万以下だった。定数倍が２分の１以下だとしても組み合わせを列挙すると２乗で厳しいなーとか考えていた。べつに厳しくはなかった。p^{2n}q^{2m} が 10^{12} を超えない範囲ですべての p^nq^m を列挙してソートしておいてから、２乗して A を超えない最大のものを二分探索で探した。サンプルの１ケース目が合わなくて困っていたのだけど、これは p^nq^n を列挙していたことが原因。p と q の指数は偶数であるという点が共通するだけで独立しているのに勝手に揃えてしまっていた。■D 問題 Takahashi the Wall Breaker。F と D を見比べて見込みがあるのは D だと思ったので一度飛ばした D に戻った。方針が立たなかったのだ。前蹴りしたはいいけど他の連結成分に合流できないケースの扱いに困っていた。それはどういう状態なのか。どの状態からやってきてどの状態へ移行するのか。どうやって現実的な時間で遷移を網羅できるのか。わからなかった。だけどグリッドの処理を書いているときに、前蹴り何回で現在のマスにいるのかを書き込んでいけばいいのだと気がついた。サンプルが有能で助かったんだけど、前蹴りで破壊される２マス目の扱いに罠がある。処理が重複する無駄があると TLE になるおそれがあるので、最短を更新したときだけ次の処理をキューに入れるのがお約束。ところが、前蹴り１マス目が最短を更新しなかったとしても、前蹴り２マス目は最短を更新することがある。前蹴りには向きがあるからこのようなことが起こる。だから前蹴り１マス目に関しては最短を更新しなかったとしても２マス目の処理を進めなければいけなかった。解けてみれば実装問題枠として置かれていたのだと思うけど、普通に考え込んでしまった。もともと大したことがなかった脳みその退行が著しい。悲しいね。自分がやっていたような精進というのは、問題に対するパターンマッチ、ヒューリスティクス、反射神経を鍛えているのであって、規模と速さにおいて決して敵わない AI に対して AI の土俵で戦いを挑む行為なのではないかと思ってしまう。自分は考えるという行為を未だ知らない。■■■Ruby の Integer.sqrt にバグが見つかっていた。「Bug #21217: Integer.sqrt produces wrong results even on input <= 1e18 - Ruby」 きっかけは ABC400 の C 問題らしい。提出 #64512377 (WA×2 / Ruby で C 問題最速の提出)。本番で絶対合ってるのに WA が出たら……かなりつらい。固執してペナルティを重ねるか、俺は間違ってないこれが違うならもう何もわからんと投げ出すというのが自分の典型的反応。最終更新: 2025-04-10T19:57+0900
時系列
という経過をたどって４つのパーツが選ばれた。
シフターは右用と書かれているけど、ハンドルの右側の上方に取り付けるつもりはなくて、左側の下方に取り付けた。そうするとラピッドファイヤーのときと同じ位置にレバーが来る。ただし左右は逆になる。左手は後ろブレーキのみ担当でシフトはなし、ブレーキとしても主力ではなくグリップも握らず遊びがちだったので、これからはリヤシフトを担当してもらう。レバーは６時の方向にあるときがトップで、ローはだいたい10時の位置。検索で上位に来るブログを読んで不安に思っていたのだけど、ワイヤーを巻き取りすぎてチェーンがスプロケから外れてしまうことはない。リアディレイラーに H/L と刻印された２つのネジがあり(以前はプラスねじだったと思ったけど、今回は星形の T8 だった)、移動限界を調整しておけばよい。３つ目のネジは B テンションアジャストボルトであり、ガイドプーリーをスプロケットに近づけてチェーンの横方向のガタが変速に及ぼす悪影響を小さくするものなので(という風に私は理解しています)、この機会に適度に近づけておく。シフトに話を戻すと、ローギア10時は親指で押すにはかなり遠いが届かなくはない(レバーの回転軸がハンドルバーより奥にあるので余計に遠い)。人差し指で手前に押すのにはちょうどいい。だが８時の位置で人差し指が届かなくなる。そこからのシフトアップが難しい。親指の背中で少し手前に押してやると親指の指先でトップまで操作できる。人差し指から親指へのリレーがスムーズではない。停止するときはだいたい３つか４つシフトダウンするので、発進するときはカチカチ、カチと３つシフトアップしていた。カチカチではなくなったのでちょっともたつく。でもまあ楽し。
シマノの日本語のページに情報がなかったから候補から漏れてしまったけど、リアディレイラーに11速の古い105(RD-R7000-SS)を使えばスプロケの値段が倍になる程度の差で一式を11速に揃えるチャンスだった。LINKGLIDE 互換の11速だから今のホイールに取り付けられるし今後のパーツ供給に不安もない。GRX と違いショートケージでコンパクトなものも選べる。Tiagra の状態を見ると LINKGLIDE でない10速は９速に続いて消える運命にあるように思えるのだよね。今現在一式新しく揃えるようなものではなかったのではないかと考えてしまう。
BB とクランクセットを交換した。
昨年末から左の足下からギリギリと音がしていた。一時解消していたんだけど10速化したときに再発していた。原因はいろいろ考えられて、
どれも違うようだったので消去法と前回交換したとき(2014年９月)に音が解消した経験からボトムブラケットが悪いと結論づけた。10 年使っている BB (シマノ BB-UN55 68mm/113mm) を交換するだけでもいいんだけど、それで音が解消しないと面倒だし、今後どのチェーンリングに交換するか悩みたくもなかったので(シマノの話だけど、PCD が同じミドルのリングでも穴の内側のでっぱりが干渉して付かないものとそうでないものがある)、クランクも含めて一番ありふれたセットに交換することにした。
クランクは 2007 年に自転車を購入したときのものそのままだからちょうど 18 年になる。チェーンリングはいつからかインナーを省いてアウターとミドルだけ付けていたけど、そのアウターもチェーンガードの固定台座としてのみ存在しておりミドル(36T)しか使っていなかった。シフターからもワイヤーは外してしまってただの脱落防止のチェーンガイドになっている。だから新しいクランクは最初からシングルにしたし、歯数は、今のスプロケットのトップ(12T)まで使い切ってしまっているので４多い 40T ということにした。スプロケのレンジがちょうどいいスピードから外れても困るので 42T にはしなかった。一番無難なのは２多い 38T だったけど、チェーンガードが欲しかったので 40T になったし、GRX ではなく CUES になった。クランク長は違和感が出ないように同じ 175mm のまま。長すぎる可能性はあるけどこれまでずっとこれなので。
ABC397 E 、K 頂点を K-1 辺で結んだ直鎖を長さ K のパスと呼んでるの違和感あるな」という意見を見かけた。真意はわからないけど、それはパスはパスでも単純パスと呼ぶのではないかという疑問なのではないかと想像した。なんでそう思うかというと、自分もちらっと単純でない(交差のある)パスが答えになることがあるか考えてみて、NK 頂点を長さ K の N 本のパスに分解するのだから、それは単純パスに違いないなとすぐに納得したからだった。単純パスだと限定しているのは文章のその部分ではなく、その他の条件の帰結としてだと思うんだよね。単純パスのことを書いているのかどうかはわからないけど(X の閉鎖性のため前後の文脈を読むことができない)、違和感は自身で解消できるのではないか。■■■精進。D 問題。５秒を２秒以下に抑えた２つのポイント。１つ目は、１から Math.cbrt(N) の範囲で線形探索する x と y の差分だけど、N の偶奇を見れば対象を半分にできる。これで 2.5 秒になる。２つ目は、コンテスト中にはついに突き止められなかった二分探索の上限。x と y の上限を低く見積もりすぎて答えが見つからないということを繰り返していた。式をよく見よう。
(y+d)**3-y**3 を展開して整理すれば dyy+ddy+ddd になる。d=1 のとき y が最小になり、これが N を超えないのだから、yy+y+1<=N の範囲で解を探すことになる。N のルートが上限だった。Ruby には上限を指定しない二分探索があるんだけど、これは遅い。上限を指定することで 2.5 秒が 1.7 秒になった。提出 #63960582 (AC / 1678 ms)。２桁ミリセックには遠く及ばないけどね、ちょっとした工夫で Ruby でも十分に間に合う制約でありました。Ruby での他の人の提出を見た。自分のが一番遅い。一番短い人の提出 #63901879 を見ると３乗根の範囲で線形探索をし、上限を指定しない二分探索をしているところは自分の５秒の解答と変わらない。それが 146 ms で済んでしまう理由は、５行目の早期の判定だと思う。線形探索範囲が半分になるどころではない。x と y の差分 d で N が割り切れないならそもそも二分探索を試す必要がない。それは xxx-yyy = (x-y)(xx+yx+yy) = d(xx+yx+yy) = N と因数分解すればわかる。この因数分解はコンテスト中にやっていたけど、xx+yx+yy を解の公式で解くというはおろか、x-y = d であり、N が d で割り切れるということもわかっていなかった。自分は、頭を使って問題を解こうとしていないな。手を動かしてとにかくやってみて運良く正しい答えが出るといいなあ、という態度で問題に当たっている。悲しいことにこれは怠惰故ではなく、頭の使い方を知らないということなのです。考えてるふりしかできない。だから下手の考え～って言われるのです。/(\d+)\s+\1\s+\1\s+/ というパターンを書いた。入力末尾の改行を保存しているので３番目が入力の末尾でもマッチするのでそこは罠ではない。罠というのは入力が "11 1 1" というケース。11 の末尾１桁だけを切り出してマッチしてはいけない。提出直前に気がついてテストしてパターンの先頭に \b を足した。\b は単語境界(\w と \s、\w と \W、\s と \S の間)にマッチするパターン。■B 問題 Card Pile。スタックが使えますかという問題。■C 問題 Buy Balls。かなり難しい。貪欲法でやろうとしたけど、どうやるべきか、本当に貪欲法でいいのか、すっきり答えが見通せなかった。黒より白の数が多くなってはいけない。だから基本的に黒を取ることにし、黒を取るときに同時に白を取るかどうかというオプションを考えることにした。それでいい？ 白が先になくなる場合、黒が先になくなる場合、黒が負でも白と併せて正なら取るべきか、そのとき併せるべき白は何か、処理順によって判断が変わってくることはないか、考えるだに貪欲法で大丈夫か不安が募る。よーく考えて提出して AC。10 分弱かけた。■D 問題 Minimum XOR Path。制約で難しさを出すのが定番の D 問題で愚直 DFS でもない順列総当たり O(N!) が通るのは甘々です。といって前にも１回「甘々です」と書いているので、前例がないわけではない。■F 問題 Rotated Inversions。E よりとっつきが良かったので F 問題から考えた。k=0...M につれて転倒数の変化を数えれば良い。変化はある要素が 0 に落ちるタイミングで起こる。自分は最初左にあって大きい要素の数と、右にあって小さい要素の数を使って変化量を数えようとした。答えが合わないから、左にあって小さい要素と右にあって小さい要素を使って数えてみたり、左にあって大きい要素と小さい要素と右にあって小さい要素を使って数えてみたりして、最終的に左右にあって大きい要素と小さい要素の数を使って数えて答えが合った。途中で何度か考え直していたんだけど、なかなか全体像が見えなくて答えを出すのに４つの変数が必要だとわからなかった。４変数のどれも答えを出すのに必要なんだけど、どこまで考慮すれば十分かはそれほど明らかでなく、目についた不十分な変数の組み合わせで答えを出そうとしていた。■E 問題 Min of Restricted Sum。数学問題に見えて実はグラフ問題であり、やれば答えが出る。つながっている要素間ではある要素のあるビットの 0/1 が決まれば他のすべての要素の 0/1 が決まる。0 の数と 1 の数を見て 0 にするか 1 にするかを決めればいい。どうやるか。UnionFind と BFS でやったけど、制限時間いっぱいの 2995 ms かかっていてこれは遅いらしい。時間内に Ruby で通している人たちはそれぞれ 660 ms、970 ms、1303 ms しかかけていない。提出が早いほど早いのには残酷な格差を見て取ってしまう。■コンテスト成績証。６問解けてないしあまり早くもなかったけど水パフォ上位で +12。前回から AtCoder がデレてきている。cs.sort_by!(&:size) cs というのは数値配列で、数値を size プロパティに基づいてソートするというのは、ほぼ何もソートしていないのに等しい。だって Bignum でなければ 32 ビット整数なら４、64 ビット整数なら８に決まっているのが数値の size だから。この間違いは過去にもやったことがある。単純に .sort と書くべきところで .sort_by と書いてしまったときに、つい選んでしまって疑問を持ちにくいのが .sort_by(&:size) なのだと思う。しょーもない間違いで貴重な得点を失ったものだ。■解法について書く。テキトーに根を選んで DFS をした。再帰関数の戻り値はアルカンの構成要素になり得る C または H の数。たとえば子がないなら自分自身を H と数えて１を返す。アルカンを構成しうる子が４つ(以上)あるなら、自分自身を C として中心に据えてアルカンを完成させて答えを更新する。アルカンを構成しうる子が１つでもあってそれが単純な H でないなら、自分自身を H として加えてアルカンを完成させて答えを更新する。アルカンを構成しうる子が３つ(以上)あるなら、自分自身を C として中心に据えてアルカンを構成しうる子であるとして親に返す。子が７つも８つもあっても選べるのは最大で４つまでなのだから、できるだけ数が大きい子を選ばないといけない。そのためのソートだったのだけど、ソートできていなかったので WA が出ていた。「アルカンを構成しうる子」というワードについて。実はすべての子がアルカンを構成する(その子を H とみなす)。最初に実装を始めたときには明らかでなかったので思わず条件があるみたいに書いてしまっただけ。