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

codeforces

はい。 oo--- (0/0) 1276(+68)

http://codeforces.com/contest/610

A,B問題ともに1回ずつ無駄にWA。。。手元でちょっとテストすればいいものを。。。

A. Pasha and Stick

ざっくりと大意

・長さnの棒を正の整数で切り分けて使って四角形を作るのに正方形になるパターンを除いた切り方の総数。

方針のようなもの

・なんとなく計算する。

python

if n%2:
    print 0
    exit()
ans=n/2
print ans/2 if ans%2 else (ans/2)-1

なんとなく計算したけどもっとシンプルに print 0 if n%2 else (n-1)/4 で良かったらしい。無駄なWAは長さ奇数で四角形を作れない場合を考慮しなかったせい。。

B. Vika and Squares

ざっくりと大意

・量が\(a_i\)あるペンキを使って1x1サイズの紙にペンキ1を使ってどんどん塗っていく。
・ペンキを使う順は必ず\(a_i\) \(a_{i+1}\)の順で\(a_n\)になったら\(a_1\)に戻る。
・最大で何枚の紙が塗れるか？？

方針のようなもの

・最小値ではない数が最長で並んでいるとこを探す。

python

n=int(raw_input())
l=map(int,raw_input().split())
r=l[::-1]
tmp=min(l)
cnt=chk=0
for i in l:
    if i>tmp:
        cnt+=1
    else:
        chk=max(chk,cnt)
        cnt=0
chk=max(chk,cnt)
chk=max(chk,l.index(tmp)+r.index(tmp))
print n*tmp+chk

これも書き方に無駄があるような。。
最小値xペンキの種類nまでは絶対に塗ることが出来る。すべて同じ量ならそれで終わり。
それ以外の場合は最小値以外が最長の箇所を探す。数列内のどこかに昇順で並んでいるか両端でループした場合の大きい方を足すと解決すると思う。