Codeforces Round #360 (Div.2) 参加記

はい。 oo--- (0/0) 1198(+15)
http://codeforces.com/contest/688
A,Bともにpre通して

A. Opponents

ざっくりと大意

・n列d行で0,1が隣接して並んでいる。1行目から見ていって、敵'0'を含む行が連続して現れる最大数はいくつか?

方針のようなもの

・'0'の含む行を見る。

python

ans=chk=0
n,d=map(int,raw_input().split())
for i in range(d):
    s=raw_input()
    if '0' in s:
        chk+=1
    else:
        ans=max(ans,chk)
        chk=0
print max(ans,chk)

strで受け取って'0'を含んでいるかを確認して最大で何回連続しているかを見れば大丈夫そう。

B. Lovely Palindromes

ざっくりと大意

・長さが偶数で回文状態であるn番目の数はいくつか??

方針のようなもの

・Noteを見たりして考える。
  python  

n=raw_input()
print n+n[::-1]

入力の上限が10100000とかで以上に大きいので1番目から探すとかはあり得なさそうで、何かの法則とかで求めるのだろうと思った。紙に書いている内にnとnを反転させたものを繋げば大丈夫そうなことに気づく。慎重に手元で確認した上で大丈夫そうだったので提出して通った。

C. NP-Hard Problem

ざっくりと大意

・グラフGについて頂点がn個であることと、辺がmある情報が与えられる。
・辺は自己ループと、同じ頂点を結ぶ2本以上の同じ辺がないことが保証されている??
・二部グラフを塗り分けて、1,2行目に一方の頂点の個数とその頂点を列挙、3,4行目にもう一方の頂点の個数とその頂点を列挙する。
・サンプル1番目は2と1,3の組で塗り分けられるのでそれで解になる。サンプル2番目はどうしても接続されている頂点で色違いにならないので-1。
・多分、2つ以上の頂点があるグループが出来ることはない。辺のない頂点も無視する。
f:id:clarinet758:20160701022613p:plain

方針のようなもの

・後で