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

A. Two Substrings

ざっくりと大意

・ABとBAが文字列sの中で一部重複せずにあるか？？
・ABAだと一部重複しているのでダメ、ABBAなら重複せずにあるから大丈夫。

方針のようなもの

・ABを探したらBAを探すか、BAを探したらABを探す。

s=raw_input()
if 'AB' not in s or 'BA' not in s:
    print 'NO'
    exit()
ab=s.index('AB')
ba=s.index('BA')

if 'BA' in s[:ab]+s[ab:ab+2].replace('AB','XX')+s[ab+2:] or 'AB' in s[:ba]+s[ba:ba+2].replace('BA','XX')+s[ba+2:]:
    print 'YES'
else:
    print 'NO'

当初は先頭からforで見ていこうかと思ったけど範囲外とかABABAとか連続されると嫌でもう少し楽する方法を考えた。最も先頭よりで見つけたAB,BAを適当にXXに置換してから、もう一方があるかを if ~ inで探してみた。

B. Preparing Olympiad

ざっくりと大意

・n個の問題を用意して、想定の難易度は\(c_i\)である。
・少なくとも2つの問題を選んで難易度の合計をlからrに抑えて、最も簡単なのと最も難しいので難易度差は少なくともxが必要である。

方針のようなもの

・そうだ、ビット総当りの練習をしよう。

python

n,l,r,x=map(int,raw_input().split())
c=map(int,raw_input().split())
ans=chk=0
for lst in range(1<<n):
    total=0
    cnt=0
    big=0
    small=10**6+1
    for i in range(n):
        if (lst>>i&1):
            total+=c[i]
            cnt+=1
            big=max(big,c[i])
            small=min(small,c[i])
    if x<=big-small and l<=total<=r and cnt>1:
        ans+=1
print ans

ビット総当りよりitertoolsで組み合わせ列挙で見るほうが速かったらしい。。

C. Divisibility by Eight

ざっくりと大意

・0始まりではない最大で100桁の非負の数から幾つかの数を除いて8で割り切れる数にする。

方針のようなもの

・先頭から8で割り切れる数を作れないか探す。

python

dele,memo=[],[]
for i in range(125):
    a=str(i*8)
    dele.append(a)
    memo.append(a)

n=raw_input()
ans=chk=0
cnt=len(dele)
for i in n:
    for j in range(cnt):
        if dele[j][0]==i:
            dele[j]=dele[j][1:]
    if '' in dele:
        print 'YES'
        print memo[dele.index('')]
        exit()
print 'NO'

どういう探し方が綺麗で早いのかはわからず。。今回は0から992までを全てリストに入れて元の数のsを先頭の方から見ていって一致するものがあればチェックして全桁一致のものが出てくれば、それが割り切れる数として見つかったものになるので出力させた。