読者です 読者をやめる 読者になる 読者になる

君はまるで砂漠に咲く、一輪の花。

僕はその花に引き寄せられる蝶。

Codeforces Round #337 (Div.2)

はい。
http://codeforces.com/contest/610

A. Pasha and Stick

ざっくりと大意

・長さnの棒で長さnを使いきって辺の長さが整数の四角形を作って、四角形が正方形でない作り方の個数がいくつか?

python

n=int(raw_input())
print 0 if n%2==1 else n/4-1 if n%4==0 else n/4

全く成長していないから当時と同じく奇数で作成できないパターンを見逃したりした。あと、print 0 if n%2 else (n-1)/4でいいらしい。。これも忘れてた。

B. Vika and Squares

ざっくりと大意

・n個のペンキ缶にそれぞれ\(a_i\)リットル入っている。1マスを塗るのに1リットル必要。
・幅1の紙に1x1のサイズのマスが無限に長く並んでいる。
・好きな番目のペンキから並んでる順に1マス1リットルで塗り、n番目からは1番目に戻ってペンキを使う。
・残量が0で缶の順番通りに塗れなくなったらそこで終了。最大の塗れる長さはいくつか。

python

n=int(raw_input())
a=map(int,raw_input().split())
tmp=min(a)
p=a.index(tmp)
chk=p+a[::-1].index(tmp)
for i,j in enumerate(a):
    if j==tmp:
        chk=max(chk,i-p-1)
        p=i
print tmp*n+chk

おそらく一番長く塗れるのが最小値の間隔が最も広い箇所の左端?から。サンプル1では最小値が2、間隔は1,2,3番で1と、3,4,5,1番で2。なので4番のから使いはじめるのが最長になる。証明はよくわからんし、最小値のペンキは同じ回数、周回でなくなるので最も間隔が広い箇所を使えるようにした方が長く塗れるんですが、細かい証明/説明は根拠なし。