記念となる300回目のCFに参加。ABCD提出でADを落としてしまい1114位。1885 → 1818 (-67)。

A: Cutting Banner

100文字以下の文字列を与えらえれる。この文字列からある範囲を消して"CODEFORCES"を作ることができるかどうかを答えよ。

解法

単純に消し去る範囲を全探索すればいい。本番はjの範囲を(i+1, N+1)ではなく(i+1, N)としていたため落としてしまった。

S = raw_input()
N = len(S)
for i in xrange(N):
    for j in xrange(i + 1, N + 1):
        if S[:i] + S[j:] == "CODEFORCES":
            print "YES"
            exit()
print "NO"

B: Quasi Binary

正の整数が与えられる。その数字を1と0からなるいくつかの数字の和によって表現したい。使用する数字の数が最も少なくなる場合の、その個数と用いる数字を答えよ。

解法

繰り上がりをすると損である。各桁ごとに、まだ1が必要なら1と、そうでないなら0として、和が与えられた数字に合うまで数字を追加していけばいい。

digit = map(int, list(raw_input()))
N = len(digit)
ans = []
while sum(digit) > 0:
    tmp = ""
    for i in xrange(N):
        if digit[i] > 0:
            tmp += "1"
            digit[i] -= 1
        else:
            if len(tmp) > 0:
                tmp += "0"
    ans.append(tmp)

print len(ans)
print " ".join(ans)

C: Tourist's note

N(≦ 10⁸)日間登山を行い、そのうちM(≦ 10⁵)日については日付とその日の標高の記録が残っている。1日に1単位しか標高を変えられないとして、登山中に到達しうる標高の高さがいくらかを答えよ。また1日1単位の移動では記録を満たせない場合は"IMPOSSIBLE"と答えよ。なお初日と最終日に標高0にいなくてもよい。

解法

初日と最終日は、その日からもっとも記録に近い日の標高と日数の差の和の標高まで到達可能。それ以外の記録間については、それぞれ標高差が日数の差以下を満たすかどうかを確認する。満たさなければ記録に不備があり、答えは"IMPOSSIBLE"となる。

そうでなければ、まず標高差を埋めるのに必要な日数を上り（下り）で消費したと考え、余った日数をさらに高いところに上って下ってきたのに使ったと考える。上り下りに2日必要なので余った日数÷2だけさらに高いところに到達できる。

N, M = map(int, raw_input().split())
d, h = [], []
for loop in xrange(M):
    di, hi = map(int, raw_input().split())
    d.append(di); h.append(hi)

ans = max(h[0] + (d[0] - 1), h[-1] + (N - d[-1]))
for i in xrange(M - 1):
    if abs(h[i] - h[i + 1]) > d[i + 1] - d[i]:
        print "IMPOSSIBLE"
        break
    tmp = ((d[i + 1] - d[i]) - abs(h[i] - h[i + 1])) / 2 + max(h[i], h[i + 1])
    ans = max(ans, tmp)
else:
    print ans