AtCoder Grand Contest 002 参加記

はい。 oox---
http://agc002.contest.atcoder.jp
2完。C問題は慣れてる人でもうっかりミスったりしたらしいのでアレ。

A - Range Product

python

a,b=map(int,raw_input().split())
print 'Zero' if (a<0 and b>0) or (a==0 or b==0) else 'Negative' if b<0 and (a-b)%2==0  else 'Positive'

問題文を殆ど読んでなかったり、綴りを間違えて'Negetive'にしてたりと酷かった。。a,bどちらかが0、a,bで正負を跨いだら積は0。a,bが負の数のみで奇数個なら積は負。それ以外は正と考えた。

B - Box and Ball

python

n,m=map(int,raw_input().split())
s=[0]*n
s[0]=1
w=[1]*n
for i in range(m):
    x,y=map(int,raw_input().split())
    if s[x-1]==1:
        s[y-1]=1
        w[x-1]-=1
        w[y-1]+=1
    else:
        w[x-1]-=1
        w[y-1]+=1

    if w[x-1]==0:
        s[x-1]=0
print s.count(1)

初めには1番目の箱にだけ赤が入っている。1からiへ移したら1は空で赤がありえなくなり、iに赤と白がある。iからjへ移したら、iに残ってるかjに移ったかがわからない。iとjのどちらにも赤がありえる。更にiからjへ移したらiは空になりjには赤白白が入っていることになる、という感じのをシミュレートした。

C - Knot Puzzle

python

n,l=map(int,raw_input().split())
a=map(int,raw_input().split())
ans=[]
f=-1
for i in range(n-1):
    if a[i]+a[i+1]>=l:
        f=i
        break
if f==-1:
    print 'Impossible'
else:
    print 'Possible'
    for i in range(f):
        print i+1
    for i in range(n-1,f,-1):
        print i

両端から短いほうを選ぶとダメ。反例情報。

4 15
10 10 1 11

両端から短いのではなく、長さL以上の箇所を最後まで残すように切らないとダメ。