A bolt out of the blue

競プロ、その他勉強したことなど

AtCoder Beginner Contest 108 参加ログ

AtCoder

ABC108に参加しました

AtCoder Beginner Contest 108 | AtCoder

実力：緑色 / 現R: 916

ここ数回は、参加していたもののいずれも爆死。メンタルをやられてログを書いていませんでした。

今回もほぼ爆死ですが頑張って翌日に書いています。

A - Pair

いつも通り普通に解けばおk

B - Ruined Square

珍しくほぼ完全に図形の問題だったので、これで手こずった人も意外といそう（はい私です。

f:id:hazuhi:20180902145012j:plain

この問題は、図をあれこれ弄ることなく、回転行列を使って解く方が簡単だ。

$\displaystyle \begin{bmatrix} cos\theta & -sin\theta \\ sin\theta & cos\theta \end{bmatrix}$

で原点を中心に反時計回りに $\theta$ だけ回転するから、 1と2を入れ替えて、

$\displaystyle X_3 = \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix} (X_1 - X_2) - X_2$

$\displaystyle X_4 = \begin{bmatrix} 0 & 1 \\ -1 & 0 \end{bmatrix} (X_2 - X_1) - X_1$

C - Triangular Relationship

問題文の解釈

三角関係という甘美な響きの問題だが、3人の関係は（Kを法として）いつでも対等である。

問題文を解釈していこう。

Kで割った余りが等しい関係を $\equiv$ で表そう。

$0 \leq a', b', c' K$ かつ $a \equiv a', b \equiv b', c \equiv c'$

の $a', b', c'$ の関係は、

$a' + b' = 0 \ or \ K \\ b' + c' = 0 \ or \ K \\ c' + a' = 0 \ or \ K$

$a' + b' = 0$ の時、 $c' = 0$ が言えるので、 $a' = b' = c' = 0$
$a' + b' = K$ の時、

2.1. $a' = 0$ の時は、 $b' = K$ となるが、残りの式から矛盾が言える。

2.2. $a' \neq 0$ なら、 $c' + a' > 0$ 。よって $c' + a' = K$ なので、 $b' = c'$ 。同様にして $a' = b' = c'$ になる。

元の式と比べると、Kが2の倍数の時に限り、 $a' = b' = c' = K/2$ となる。

計算

あとはどうやって数え上げるかが問題になる。

$a' = b' = c' = 0$ の場合 a, b, cが全てKで割り切れる組み合わせを全て数えれば良いので、

(n//k)**3

となる。

$a' = b' = c' = K/2$ の場合

1.を除くために、全部 K/2の倍数で、かつKの倍数でないものを数え上げる。

((n - k//2)//k+1)**3)

で計算できた。

最終的にワンライナーで書けて、

print((n//k)**3 + (1-k%2)*((n - k//2)//k+1)**3)

となる。

D - All Your Paths are Different Lengths

所感

2進数をグラフで表現すれば良いことにはすぐ気がつくだろう。でも、実装力がないと解けない問題のようだった。

自分は時間が足らず解けなかった。

今回も本家解説を読んで、概要だけでも書いておきたい

作るべきグラフの形

結局、何を作ればいいのかは、次図を見ていただければわかりやすいかと思う。 f:id:hazuhi:20180902171508j:plain

これは、 $L = 150$ の時の一つの解なのだが、大きく分けて２種類のエッジがある。

一つは鎖状に繋がっているエッジで、これは1番ノードから終端ノードまで繋がっている（ここでは主鎖と呼ぼう）。
もう一つは、各ノードから最後のノードに直接橋渡しをしているものだ。

主鎖によって、2の累乗までの数字を全て表現できるようになる。主鎖のような構造が、最も単純に2進数を表すことのできるグラフだ。

問題で問われているのは、任意の数字 $L$ までの数字を漏れ・ダブりなく表すことであるから、この主鎖を応用して、数字の大きい方から順に埋めていけば良い。

主鎖のノード $i$ から取得できる数字は、[tex: 0 ~ 2ⁱ - 1]※ なので、ノード $i$ から取得できる最大の数字が、今足りていない最も大きな数字に合致するように、定数を足せば良い。

具体的に説明しよう。

図では、 $i = 2, 3, 5$ のノードから、終端ノードにエッジが伸びている。

これらはそれぞれ、0~1, 0~3, 0~15を表す数字を出力している。これらに定数を足して、

128~129, 130~133, 134~149を表すようにしている。

127までは、主鎖で表すことができるから、これで条件は満たされている。

二進数

ところで、主鎖は2進数を表すといった。

150を2進数で表すと、"10010110"になる。

ひっくり返すと、"01101001"になるが、これがちょうど上の鎖の構造と同じことが分かるだろうか。

つまり、2進数表記で右から $i$ 桁目のビットが1ならば、ノード $i$ から終端ノードにエッジを伸ばせば良い。その時の定数の大きさは、 [tex: n - 2ⁱ]※ となる。

※はてな Markdownの数式は()なので()です。

結果

R916 => R945 (Up)

頑張って早く青色コーダーになりたい