2020/1/24

TDPC B

メモ化再帰をしたら大変なことに...

パリティを分ければ漸化式で書ける

 

TDPC D

愚直に書くとメモリが大変なことになる(ML264MBの場合、64bitだと10^7*定数ぐらいが限界)→使いまわす

場合の数が大きすぎる→直接確率を持たせる

 

Codeforces 1294 C

ありえないほど苦戦

冷静になると約数を小さい方から二つ持ってきて判定すればよい

大小関係を設定すると見通しが立ちやすいかも?

 

Codeforces 1294 E

列ごとに分割して考えてよい

要素ごとに、何回shiftした時に正しい位置に来るかを求め、shift回数ごとにcountする

→各shift回数ごとに必要な最小操作回数がわかる

整理して見通しを立てやすくする(条件式もごちゃごちゃしてきたら書き出すべき)

 

Codeforces 1294 F

パス構築

直径+直径となるパスから最も離れた頂点をとればよい

まず直径を求める

次に直径の端点からの距離を各頂点について求める

各頂点を全探索して最も直径パスから離れた点を取ってくる