Codeforces Round #191 (Div.2) - 君はまるで砂漠に咲く、一輪の花。

A. Flipping Game

ざっくりと大意

・数列で1を最も多く出来る方法で特定の区間の0,1を反転させた時に1がいくつあるか？？
・少なくとも1つの1 ≤ i ≤ j ≤ nの、i,j間は反転させる必要がある。

Python2

n=int(raw_input())
l=[int(x) for x in raw_input().split()]
ans=chk=0
for i in l:
    if i==0:
        chk+=1
    else:
        chk-=1
    if chk<0:
        chk=0
    ans=max(ans,chk)
print n-1 if 0 not in l else l.count(1)+ans

必ず1回は実行しないといけないので数列に1しかない場合はn-1が解になる。それ以外は端からチェックを初めて0が有ったら+1、1が有ったら-1して最大値を保存しつつ、負の値になったら0にリセットした。負の値になる = 反転させても1を最も多くは出来ないパターンと言う感じ。だと思う。。

B. Hungry Sequence

ざっくりと大意

・1より大きく10⁷以下の数を使ってn個の数列を作る。
・左側の数より右側の数が大きく、右側の数が左側の数で割り切れないような長さnの数列を作る。

Python2

n=input()
m=10000001
ans=xrange(m-n,m)
print ' '.join(map(str,ans))

右側の数が左側の数で割り切れないようなというのは必ずしも隣り合うものではなく、末尾の数が先頭の数で割り切れないようなということも含む。単純な解はサンプルを無視して使用可能な最大数の10⁷を末尾から1減らしながら並んだようにすると解になる。