AtCoder Grand Contest 002 参加記
はい。 oox---
http://agc002.contest.atcoder.jp
2完。C問題は慣れてる人でもうっかりミスったりしたらしいのでアレ。
A - Range Product
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
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
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
両端から短いほうを選ぶとダメ。反例情報。
C問題でやった恥ずかしい嘘解法:
— ⭐️10, Div1底辺 (@startcpp) 2016年7月31日
・両端からほどく
・左端と右端の数字を比べて、左端が小さければ左側、そうでなければ右側をほどく
反例:
4 15
10 10 1 11
(上記の方法だと)10 10 1 11 -> 10 1 11 -> 1 11 -> Impossible
4 15 10 10 1 11
両端から短いのではなく、長さL以上の箇所を最後まで残すように切らないとダメ。