https://arc102.contest.atcoder.jp/tasks/arc102_b

コンテスト本番では"トポロジカル"という単語が見えたため即E問題に移りました(トポロジカルソートに苦い思い出があるため)
ただ、終わった後よく見てみたら個人的に好きな構築ゲーだったので、一考もしないのは少しもったいなかったかな…
(わりと発想ゲー感はあるのでコンテスト中のコンディションで解けたかは怪しい)

問題概要

以下の条件を満たす有向グラフを一つ構成しなさい．

頂点数N、辺数M、各辺のコストc
全ての辺は頂点番号が小さいものから大きいものへ向かっている(つまり適当なグラフをトポロジカルソートしたもの)
頂点1→頂点NへのパスはちょうどL個あり、それぞれのパスの長さは0～L-1がちょうど1個ずつ存在する．
多重辺はあり

制約

N <= 20
M <= 60
0 <= c <=10⁶
2 <= L <= 10⁶

考えたこと

構築ゲーは制約がヒントになることが多い(気がする
例えば今回は頂点数20個で10⁶までの値を表現する必要があると考えると2進数を使うのではないかというのは自然な発想として出てくる． (2²⁰>10⁷、両端を使わないとしても2¹⁸>10⁶なのでぽい)
2進数を表現するということで、まず各頂点を通ったからbitが立つみたいなイメージで考える．例えばN=5の時、両端(1,5)を除いた(2,3,4)という組で考えると
1→2→3→5 なら、110=6
1→2→4→5 なら、101=5
といった要領で2進数が表現できそう…

しかしこの方法だと全点間に辺が必要そうなので辺の数がN²くらいになりとてもM<=60の制約がクリアできなさそう
そこで問題文を改めて眺めると重複辺が許されるらしいので，これをうまく活用すると下のようにうまい感じに2進数っぽく表現できるて辺数も2N個ですむ．
この形を思い付くのが一番難しかった(こなみ

【L=8の時】

さて、上の形を使えばL=2^Nの形で表されるLは表現できるが、その間をどうやって埋めるかという問題．具体的な値を与えて考えてみる.
【L=9の時】

これは簡単で上のように1→N間にコスト8の辺を作ってしまえばよい
【L=10の時】

これも同じように1→N間にコスト8と9の辺を作ってしまうと、どんどん辺の数が増えてしまうので制約的に厳しい.
そこで8,9が連続した数値であることを考えると上のように線を引くいて元の辺も活用することで上手く表現できる
少し飛んで 【L=15の時】

このように上手い具合に元々引いてある辺を使えば表現することができる
また上の図を見ると明らかなように15=8+4+2+1と分解しているが、これは2進数の扱いそのものでLを二進数表記してbitが立ってる桁のところに、上のように線を引くことで任意のLについて表現できる

実装

考察さえ終えれば実装は簡単
Submission #3130962 - AtCoder Beginner Contest 108

L = int(input())
N = L.bit_length()

Lines = []
for i in range(1,N):
    Lines.append([i,i+1,0])
    Lines.append([i,i+1,1<<(N-i-1)])

tmp = 1<<(N-1)
for k in reversed(range(N-1)):
    if L>>k & 1:
        Lines.append([1,N-k,tmp])
        tmp += 1<<k

print(N,len(Lines))
for a,zu,nyan in Lines:
    print(a,zu,nyan)

感想

2進数を使うというはわかっても、多重辺をうまく使ってそれを表現する形を閃くのが難しい(と思った
ここの発想さえできればその後の考察や実装は簡単なのでわりと発想ゲーって感じで個人的には好きです
(むやみに発想ゲーって言うといやお前の精進が足りないだけで典型だからって強い人に怒られそう(赤にもなってないのは典型も解けてない証、古事記にもそう書いてある

sima(mu)*雑記

print(f"{雑多なこと}")

ARC102_D - All Your Paths are Different Lengths (700)

問題概要

制約

考えたこと

実装

感想