ゴミだったよ。ゴミとも思えなかった前回よりはずっといい状態なのでよかったけど、腕とかがかすかにしびれる感じがあって精神が苦しい。
C - Triangular Relationship
整数が3つもあって、しかもa+bとか和で、怖い。a+b+cを基準に考えてみる。a,b,cを固定すればa+b+cは定まる。もっと言えば、a+b+cをKで割ったあまりが固定される。「すべてKの倍数（Kで割ったあまりがすべて0で等しい）」ってことは、mod Kでa,b,cは相等しいということだ。そういう縛りをしたときに何通りあるのかはまだよくわからないが、どういうときにa+bがKの倍数になるかをまず考えよう。Kが2の倍数のときはK/2でいける。他に、0でもいい。他にはなさそうなのでそれで書く（決まったタイミングでK毎に1増えるのでオフセットを実験しつつ普通に除算）。WA。えー！？llが必要なんだ。20万という制約から、3乗してもllには収まるなと思った記憶があるのにこれは酷い。
そういえば、それしかないという証明が思い浮かばない。コンテスト中はちらっとmod Kでの逆数を考えた。でも素数とは限らんしな。素数だとして0に2の逆数を掛けたら0だから、まあそういうことか。2*x=n*K（0<=x<K、x,nは整数）とか方程式をたてると、nは0か1ということになり、x=0,K/2が出てくるね。こういう問題は、頭の中でパッと「証明」ができると強いのだが、コンテスト後にやっと長い証明を出しているようでは弱い。ここでいう「長い」というのは、文字数のことではなく、頭の中での長さのこと。
D - All Your Paths are Different Lengths
頂点数が少ない。そして、辺数が全頂点間に辺が引けないほど少ない。パスの長さのことはおいといて、とりあえず100万が作れるかを考えてみる。iとi+1を2本の辺でつなげば2^19になる。これでは足りないので3本にすると、3^13（14頂点）で100万を超える。なんかN進法とかで表す形になりそうだし、その形ならパスの長さも何とかなるだろう。ここからは、経路をL通りにすることに注力する。
さて、3進法で表すことを考える。まず3^3通りとかの図を描き、そこから3増やしたり9増やしたりする方法を考える。始点からいくつか飛ばして辺をつなげばできそうだ。この場合、辺は1頂点から最大で5本出る。3^13だと5*13でオーバーしてしまう。ていうか5*12ならちょうど60だな。3^12の時点で50万は超えてるわけだし、3^13を目指す必要はないわけか。2*3^12とかでいい。小さい図を描いて計算してみても、これはいけそうだ。この時点で、開始40分だった。
問題はパスの長さの作り方だが、とりあえず経路数だけで実装してみる。自分が考えてた図の始点と終点を反対にし、3進法での下位から作っていくことにした。3^12とかでよければ、パスの長さを作るのは簡単だ。まさに3進法で作ればいい。問題は、3^12+3^2とかの半端だが、これも下位から3^12,3^12+1,3^12+2と割り当てていけばいい。できそうな感覚は最初からあったが、具体的に作っていくのは難しい。実装が汚くなったら危険信号で、一応正しいかもしれないが何かを理解していないということになる（逆に、理解できてないなら実装をきれいな見た目に寄せることで答えを知るというムーブもある）。辺がたくさん集まってくる終点の扱いが難しく、制約もギリギリなため思考に余裕がない。また、上で3^12と書いた、終点へいきなりジャンプする組の長さの基準となる値の取得で最後まで混乱してWAが取れなかった（「ACが取れなかった」と同じ意味になるんだね）。22:39:35とかを示す時計を見たときは目を疑ったよ。あれで間に合わないんだね。
