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

はい。 xo-x- (0/0) 1270(+39)
http://codeforces.com/contest/754
Dはサンプルは出来ても入力値の制限を読み違えてた。読んでたら読んでたでTLEにしかならなかったけど。Aはまた誤読でWA。部屋内では誰もHackに動かなかったけどコンテスト全体ではAがHack祭りになってることに途中で気付いたのでもう少し考察するべきだった。

A. Lesha and array splitting

ざっくりと大意

・数列aをそれぞれの総和が0でないようなk個に分割して、それぞれの開始と終了の位置を出力する。

Pypy3

n=int(input())
l=[int(i) for i in input().split()]
ans=chk=0
if l.count(0)==n:
    print('NO')
elif sum(l):
    print('YES')
    print(1)
    print(1,n)

else:
    for i in range(1,n):
        if sum(l[:i]) and sum(l[i:]):
            print('YES')
            print(2)
            print(1,i)
            print(i+1,n)
            break

数列aに0しかなかったらNOになる。数列aの総和が0でなかったら分割せずにそのまま出力。それ以外なら左端から左右にそれぞれの総和が0にならないように分割できる箇所を探す。a=0,1の場合だと分割しなくてもよいのが読み違えでHack出来るケースになる。わかる。a=0,0,0,0,3,-3,0で落ちる。わからん。。

B. Ilya and tic-tac-toe game

ざっくりと大意

・まるばつゲームでxのターンの盤面が与えられる。xが今のターンで勝てるかどうか。

Pypy3

l=[]
ans=0
for i in range(4):
    x=input()
    if 'xx.' in x or '.xx' in x or 'x.x' in x:
        ans=1
    l.append(x)

for i in range(2):
    for j in range(4):
        tate=l[i][j]+l[i+1][j]+l[i+2][j]
        if 'xx.' in tate or '.xx' in tate or 'x.x' in tate:
            ans=1
        if j>=2:
            y=l[i][j]+l[i+1][j-1]+l[i+2][j-2]
            if 'xx.' in y or '.xx' in y or 'x.x' in y:
                ans=1
        if j<2:
            y=l[i][j]+l[i+1][j+1]+l[i+2][j+2]
            if 'xx.' in y or '.xx' in y or 'x.x' in y:
                ans=1
print('YES' if ans else 'NO')

縦横斜めにxが3つ並びを作れるxx.,x.x,.xxのいずれかがないかを探す。xのターンといいつつ既にoooがないかを一応疑ったけど必要なかったらしい。

C. Vladik and chat

ざっくりと大意

・手を付けなかった。チャットログがあり得るか、?を埋められるかを見るっぽい。

D. Fedor and coupons

ざっくりと大意

区間が少なくともk重に重なるトコで最長の区間を探して、区間長とクーポン番号を出力する。