AtCoder Regular Contest 102

AtCoder Regular Contest 102に参加しました！
AtCoder Beginner Contest 108 beta版
 AtCoder Regular Contest 102 旧版
 AtCoder Regular Contest 108 beta版

解けた問題だけ解説をしていきますー

要項

AtCoder Beginner Contest 108 / Regular Contest 102
rated 1200 / 2800
9/4(土) 21:00 ～ 22:40 (100分)
100-200-300-700-700-1200 (6問)
ペナルティ: 5分

方針

ただいま合宿中なので、あまり時間は掛けられない。
従って、CD2完を速くして残った時間でE挑みを軽くしてみる程度に抑えたいところ。

A - Pair

1から $K$ の中に偶数は $\lfloor \frac{K}{2} \rfloor$ 個、奇数は $\lfloor \frac{K+1}{2} \rfloor$ 個あるので、ペアの数は $\lfloor \frac{K}{2} \rfloor \lfloor \frac{K+1}{2} \rfloor$ 個となります。

まず、正方形であるから $x2 - x1 = y3 - y2, x2 - x3 = y2 - y1$ となります。
また、対角の座標の和は等しいはずなので、 $x1+x3=x2+x4, y1+y3=y2+y4$ となります。
ここから、 $y4-y1=y3-y2$ より $y4=y1+(y3-y2)=y1+x2-x1$ と分かります。
あとは $y3=y2+y4-y1=y2+x2-x1$ 、 $x3=x2+y1-y2$ 、 $x4=x1+y1-y2$ と導出できるので、それを出力すれば良いです。

C - Triangular Relationship

考え方は2つありますが、まずは決め打ちで解いていくことを考えてみましょう。
ここでは $a$ を決め打ちます。ただし $0 \leq a < K$ とします。
この時、 $a+b \equiv 0 \pmod{K}$ より $b \equiv nK - a \pmod{K}$ ( $n$ は任意の正の整数)と分かります。
同様に $c$ も分かり、 $b + c \equiv 0 \pmod{K}$ より $b + c \equiv nK + mK - 2a \equiv 0 \pmod{K}$ であるから $2a \equiv 0 \pmod{K}$ ということが分かります。
従って、 $2a$ が $K$ の倍数であるときは $b$ と $c$ はそれぞれ $x = 2a \bmod K$ を用いて ${\lfloor \frac{N + x}{K} \rfloor}^2$ 通りとなります。
後は足していけば解けます。

なお、上の式を更に工夫すると、 $K$ が奇数ならば $a$ は $K$ の倍数であり $x=0$ となるから、答えは ${\lfloor \frac{N}{K} \rfloor}^3$ です。
逆に $K$ が偶数ならば $a$ は $\frac{K}{2}$ の倍数だから、答えは ${\lfloor \frac{N}{K} \rfloor}^3 + {\lfloor \frac{N + \frac{K}{2}}{K} \rfloor}^3$ です。

D - All Your Paths are Different Lengths

構築問題は、簡単な規則性があるはずです。
まずは、問題に着目すると $N \leq 20, M \leq 60$ という非常に小さい値に気付きます。
また、 $L \leq 10^6 = 1000000 \fallingdotseq 1048576 = 2^{20}$ より、おそらく何らかの方法で ${\rm O}(\log L)$ が出てくると想像できます。
そこで、まずは丁度 $L$ 通りの経路ができるような辺を考えていきましょう。

実験をすると、経路数は各頂点について移動前の経路の合計になることが分かるので、多重辺の経路数は積の形になることが分かります。
例えば、 $1 \rightarrow 2$ の経路を2つ、 $2 \rightarrow 3$ の経路を3つ置くと $1 \rightarrow 3$ の経路は全部で $2 \times 3 = 6$ 通りになります。
ということは、例えば $n \rightarrow n + 1 (1 \leq n < 20)$ の経路を2つずつ用意すると、38個の辺で $2^{19}=524288$ 通りまで対応できます。
さて、もちろんですが $L$ は2の乗数とは限りません。
その点を調整していきます。
まず、 $L = 6$ としてみましょう。
まずは $1 \rightarrow 2$ に2個、 $2 \rightarrow 3$ に2個の辺を置きます。これで4通り。
この時、 $1 \rightarrow 1$ は1通り、 $1 \rightarrow 2$ は2通りあることに着目すると、 $2 \rightarrow 3$ にもう1個辺を増やすとちょうど経路が2個増えます。
同様に、例えば $L = 7$ とすると $1 \rightarrow 3$ と $2 \rightarrow 3$ に1個ずつ辺を増やせば経路が3個増えます。
このような辺の置き方は、 $L$ を2進数で表した時の値を見れば分かります。
例えば、 $L = 13 = 1101_{(2)}$ のときは頂点数 $N = 4$ であり、 $1 \rightarrow 4$ と $3 \rightarrow 4$ に追加の辺が置かれます。
この時、各頂点に対して高々3個しか辺を伸ばさないことから、 $M \leq 19 \times 3 = 57$ より条件を満たします。

さて、これで辺の繋ぐ場所は分かったので、後は長さをどうするか考えましょう。
まず、 $i$ 番目の頂点に対して長さが $0, 1, \cdots, 2^i - 1$ の $2^i$ 通り網羅したいので、 $i \rightarrow i + 1$ の辺の長さは $0$ と $2^{i - 1}$ の2つにします。
後は、残りの辺の長さは今まで繋いだ経路数+1にすれば良いので、毎回加算しながら辺の経路を決めていけば解けます。