hotpepsiの練習帳

Codeforces 161

03:01

Div2 A. Beautiful Matrix

問題

• 中央に1を移動させる

方針

• abs取るだけ

Div2 B. Squares

問題

• 異なる大きさの正方形を重ねる
• ちょうどk枚重なる点をどれでも良いので答える

方針

• 辺の上の座標がn～1になる
• kが1～nなら辺上の座標で答える

Div2 C. Circle of Numbers

問題

• 1～nのN個の数値を円状に並べる(5<=N<=10000)
• 隣と一つ飛びの隣をペアとする
• 2N個のペアが与えられる
• 元の数値の並びを答える

方針

• 紙に書いてみる
• XYZABCDEFGと並んでいたとき、Aの隣の候補について考える
• set<int>を10000個用意してペアを突っ込む
• AにはYZBCがペアとして入る
• BのペアはZACD
• AとBの共通のペアはZとCで、一つ飛びだと共通のペアは1つ
• つまり共通のペアが2つなら隣
• ただしN=5のときは、ペアが4つ、すなわち自分以外全部ペアなので、任意の並び順で良い
• N=6のとき、ABCDEFはACBDFEと答えてもよい。反対側の数値だけがペアではないので、それだけ場合わけするとうまくいく
• N>=7は場合わけ不要
• 1から順番に1つずつ決めていく

結果

ooo-- 492+464+1500=2456pt 83rd/1591 rating 1534 -> 1674 (+130)

Cが通ったので満足。