最終更新: 2025-04-04T01:03+0900
時系列
という経過をたどって４つのパーツが選ばれた。
シフターは右用と書かれているけど、ハンドルの右側の上方に取り付けるつもりはなくて、左側の下方に取り付けた。そうするとラピッドファイヤーのときと同じ位置にレバーが来る。ただし左右は逆になる。左手は後ろブレーキのみ担当でシフトはなし、ブレーキとしても主力ではなくグリップも握らず遊びがちだったので、これからはリヤシフトを担当してもらう。レバーは６時の方向にあるときがトップで、ローはだいたい10時の位置。検索で上位に来るブログを読んで不安に思っていたのだけど、ワイヤーを巻き取りすぎてチェーンがスプロケから外れてしまうことはない。リアディレイラーに H/L と刻印された２つのネジがあり(以前はプラスねじだったと思ったけど、今回は星形の T8 だった)、移動限界を調整しておけばよい。３つ目のネジは B テンションアジャストボルトであり、ガイドプーリーをスプロケットに近づけてチェーンの横方向のガタが変速に及ぼす悪影響を小さくするものなので、この機会に適度に近づけておく。シフトに話を戻すと、ローギア10時は親指で押すにはかなり遠いが届かなくはない(回転軸がハンドルバーより奥にあるので余計に遠い)。人差し指で手前に押すのにはちょうどいい。だが８時の位置で人差し指が届かなくなる。そこからのシフトアップが難しい。親指の背中で少し手前に押してやると親指の指先でトップまで操作できる。人差し指から親指へのリレーがスムーズではない。停止するときはだいたい３つか４つシフトダウンするので、発進するときはカチカチ、カチと３つシフトアップしていた。カチカチではなくなったのでちょっともたつく。でもまあ楽し。
シマノの日本語のページに情報がなかったから候補から漏れてしまったけど、リアディレイラーに11速の古い105(RD-R7000-SS)を使えばスプロケの値段が倍になる程度の差で一式を11速に揃えるチャンスだった。LINKGLIDE 互換の11速だから今のホイールに取り付けられるし今後のパーツ供給に不安もない。GRX と違いショートケージでコンパクトなものも選べる。Tiagra の状態を見ると LINKGLIDE でない10速は９速に続いて消える運命にあるように思えるのだよね。今現在一式新しく揃えるようなものではなかったのではないかと考えてしまう。
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 とみなす)。最初に実装を始めたときには明らかでなかったので思わず条件があるみたいに書いてしまっただけ。