Codeforces Round #580 (Div. 1)
初のdiv1が0完でしたが…
A. Almost Equal
問題：2n個の整数の順列が環状に並んでいる。n個の連続する要素の和2n個の、任意の2つの要素の差が最大でも1になるような順列を求めよ
3個だと思ってました（なぜ）
解説：
コンテスト終わった後に考え直しました
i個目とi+n個目の要素の差が1になります。
したがって、2*i+1、2*i+2を対角におきます。
和はそれぞれ偶数だけ足したものと奇数だけ足したものができてしまいます。
基本2*i+1として、ｎ個の対角ペアのどちらかに１足すことにします。
どこをとっても平均的になる必要があるので交互にしてみます。
そうするとnが偶数のとき2*n個目と1個目どちらも+1され、n個目とn+1個目がそのままになります。
差が2になってしまうので構築不可能です
奇数のときのみ上のように構築して出力しましょう
感想：
いやむずすぎ
1300点ってマジ？普通にわからなかったです。
B. Shortest Cycle
問題：ｎ個の整数が与えられる。各整数を頂点として、任意の2つについて論理和が1以上なら辺を与えるとする。最短の閉路を求めよ
ついてあで答えを見て実装したので書きます
各bitで見ます。そのbitが1である任意の2つの整数で辺があります。
つまり、同じbitで3つの整数が1であるなら、長さの3の閉路があります。
これに当てはまらないことを考えます。
制約から高々60bit程度で、各bit1整数は2つ以下なので、頂点120、辺60以下に抑えられます。これは全探索で十分間に合います。
ここからバグ祭り
１：TLE
このままだとなぜか間に合いません。
6*10^6って1secで間に合わないんですね。
nが120以上なら必ずどこかのbitで3つ以上になります。
判定する必要がないです
２：
上の頂点数に0を含めない。
0はこの問題で全く意味ない存在です。入力時点で数えて取り除くべきでした。
３：
二重辺を許さないので辺をsetで記録してまとめないといけないです。
これは提出前に気づくべきでした。
Bは1900らしいです。ま？
C以降は気が向いたらやります。
インタラクティブなのでC避けてDは普通にわからなかったです。
2500と2800なのでまあ無理かなって感じです。
感想
かなしい。Div1Ratedについて実力不足だとは思ってましたが、もうちょっと戦いたかったなって感じです。
まあ実力不足なので仕方ないやって気持ちのほうが強いですね
明後日のDiv2で挽回したいところ
