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

A. Combination Lock

ざっくりと大意

・n桁の鍵の2行目が今の状態で、3行目の数にして鍵を開けるのに最小の手順は何回か。

方針のようなもの

・減らす方が、増やす方が早いか。9-0でループするのを使った方が早いかを見る。

n=int(raw_input())
s=raw_input()
w=raw_input()
ans=chk=0
for i in range(n):
    l=int(s[i])
    r=int(w[i])
    ans+=min(abs(l-r),(min(l,r)+10)-max(l,r))
print ans

AtCoderでもこんな感じの問題を見かけた気がする。

B. School Marks

ざっくりと大意

・進捗は1からpまでの数で全体はn件で表わされる？？
・Vovaは全部の問題が解けるがxポイントを越えてしまうと目立ちすぎて質問しに来る人がいるのでうざい。
・だが彼の中央値がyを下回ると母からゲームが禁止されてしまう。
・既に進捗を明らかにしているものはk件で\(a_1\)から\(a_i\)である。
・n件全てを表明した時の合計がxを越えず、中央値がyを下回らないように残りの進捗を表すか、その数がない時は-1を出力する。

方針のようなもの

・xを超えないように合計を小さくしたいなら最も優先するのは1を追加すること、ただしそれで中央値がyを下回る時はyを追加だと思う。

python

n,k,p,x,y=map(int,raw_input().split())
l=map(int,raw_input().split())
total=sum(l)
large=small=0
for i in l:
    if i>=y:
        large+=1
    else:
        small+=1
ans=[]
cnt=n-k
while cnt:
    cnt-=1
    if small>=large:
        large+=1
        tmp=y
    else:
        small+=1
        tmp=1
    ans.append(tmp)
    total+=tmp
print ' '.join(map(str,ans)) if total<=x and large>small else -1

当初はリストに1やyを追加しようとしてたけどTLEなりそうで嫌々書いていたら、単にy以上の件数とy未満の件数だけ管理すれば何とかなりそうなことに気づく。だが最後に件数がlarge>smallであることを確認せずに無駄にWA。。

C. Ice Cave

ざっくりと大意

・左上が1行1列で右下がn行m列のマスになっているのをスタートからゴールに辿り着けるか？？
・マスが'.'に侵入すると'X'になり、既に'X'の途中経路のマスには侵入出来ない？？
・だがゴールは'.'の時は一度は隣接の'.'マスに移動して'X'になったゴールマスに再度侵入か、元々ゴールマスが'X'でないと到着ではない？？

方針のようなもの

・移動できるかをシミュレートして確認する。

python

xy=[(1,0),(-1,0),(0,1),(0,-1)]
n,m=map(int,raw_input().split())
l=[]
q=[]
for i in range(n):
    l.append(list(raw_input()))
s=map(int,raw_input().split())
g=map(int,raw_input().split())
gr,gc=g[0]-1,g[1]-1
q.append((s[0]-1,s[1]-1))


def goal(a,b):
    if l[gr][gc]=='X':
        return 1
    for ay,ax in xy:
        if 0<=gr+ay<n and 0<=gc+ax<m:
            if (gr+ay!=a or gc+ax!=b) and l[gr+ay][gc+ax]=='.':
                return 1
    return 0

while q:
    chk=q.pop()
    for r,c in xy:
        if 0<=chk[0]+r<n and 0<=chk[1]+c<m:
            y,x=chk[0]+r,chk[1]+c
            if y==gr and x==gc:
                if goal(chk[0],chk[1]):
                    print 'YES'
                else:
                    print 'NO'
                exit()
            elif l[y][x]=='.':
                q.append((y,x))
    l[chk[0]][chk[1]]='X'
print 'NO'

多少の何か条件がついた程度の経路探索みたいなのは時間はかかるけど書けるようになってきたな。移動可能なマスには全て移動して元々いたマスは'X'にすれば他に何かメモしなくても重複して移動しないし、既にゴールが'X'になってきたら’YES'になる。そうでなかったら四方の何処かに'.'があるか見るのを元々いたマスをちょっと気にすれば問題なかった。