Codeforces Round #373 (Div.2) 参加記

はい。 oox-- (0/0) 1198(+144) http://codeforces.com/contest/719
はい。あんま考えないで適当にやったらA問題で1Hack食らった。。結構悔しい。B問題も無駄に再提出。D問題で想定解やテストケースに穴が合ったようで問題は無効に。レーティングはDiv.1ではunrated、Div.2ではratedに。影響範囲の人数の違いでそうしたらしい。

A. Vitya in the Countryside

ざっくりと大意

・明日の月は今日と比べて大きくなるならUP、小さくなるならDOWN、わからないなら-1を出力。

Python

n=int(raw_input())
a=map(int,raw_input().split())
if len(a)==1:
    if a[0]==15:
        print 'DOWN'
    elif a[0]==0:
        print 'UP'
    else:
        print -1
elif a[-2]>a[-1] and a[-2]!=1:
    print 'DOWN'
else:
    if a[-2]==14:
        print 'DOWN'
    else:
        print 'UP'

昨日と今日を比較してUP/DOWNのどちらの周期なのかをみるので情報が2日分必要だと思った。1日分しか情報がないときは-1で良いでしょうと思って提出したらpreは通ったけど数分後にHackされた。0,15が例外でUP/DOWN定まることに気づいて再提出。何回もミスしてるけど最小値、最大値の扱いは要注意。あと解法とは別件でUP/DOWNのtypoもHackとして狙うことが可能な場合がありうるという知見を得た。

B. Anatoly and Cockroaches

ざっくりと大意

・r,bを最小手数で交互に出てくるようにする。1文字だけ置換しても、2文字をswapしても1手。
・rbbrrは3,4番目をswapするとrbrbrに出来るので1。bbbbbは2,4番目をそれぞれrに置換して2手。

Python

n=int(raw_input())
s=raw_input()
t1=t2=t3=t4=0
if n%2 or n%2==0:
    for a,i in enumerate(s):
        if a%2 and i=='r':
            t2+=1
        elif a%2==0 and i=='b':
            t1+=1
    chk=abs(t2-t1)+min(t2,t1)
    for a,i in enumerate(s):
        if a%2 and i=='b':
            t3+=1
        elif a%2==0 and i=='r':
            t4+=1
    print min(chk,abs(t3-t4)+min(t3,t4))

問題文の解読にミスしてたりで無駄に2回WAした。r,bが交互でかつ回文みたいすると勘違いしていて文字長が偶数のときは最終形がrr, brrb,brbbrb..かと思っていた。preが通らなくてr,bを交互にするのだろうと推定で書き直してなんとかAC。

C. Efim and Strange Grade

ざっくりと大意

・小数点以下の数を最大でt回四捨五入して最大の数になるようにする。
・t=1で10.245なら3番目を四捨五入で10.25に、t=2で10.245なら3番目を四捨五入で10.25になった後に2番目を四捨五入で10.3に。t=100で9.2は四捨五入しないのが最善でそのまま9.2になる。
・四捨五入できるのは小数部分だけで、最終形が5.0トカになった場合には整数で5を出力するなどに注意が必要。

Python

n,t=map(int,raw_input().split())
x,y=map(str,raw_input().split('.'))
ans=chk=0
p=[i for i in y]
P=range(len(p))
q=[i for i in x]
z=0
def sol(ans):
    t=-len(ans)-1
    ans[-1]=chr(ord(ans[-1])+1)
    for i in range(-1,t,-1):
        if ans[i]==':' and i>t+1:
            ans[i]='0'
            ans[i-1]=chr(ord(ans[i-1])+1)
        elif ans[i]==':':
            ans[i]='10'
        else:
            break
    print ''.join(ans)

for i in P:
    if i==0 and ord(p[i])>=53:
        sol(q)
        exit()
    elif ord(p[i])>=53:
        p[i-1]=chr(ord(p[i-1])+1)
        t-=1
        z=1
        p=p[:i]
        P=P[:i]
        break

if z==1 and t>0:
    tmp=-len(p)-1
    for i in range(-1,tmp,-1):
        if p[0]==':' or ord(p[0])>=53:
            sol(q)
            exit()
        elif ord(p[i])>=53:
            p[i-1]=chr(ord(p[i-1])+1)
            p[i]='0'
            t-=1
        elif ord(p[i])<53:
            break
        if t==0:
            break
syo=''.join(p)
syo=syo.rstrip('0')
print x+'.'+syo

コンテスト後に復習？で何回もやり直してなんとかAC。四捨五入の処理の仕方とか、解法とかよりintキャストのTLE対策がめんどうすぎた。解法というほどでもないけど一番最初に四捨五入をするのは最も位が高い5以上の箇所ですると思う。 例えば、5.225335のような数の場合に後ろの･･･335で四捨五入をしても、225･･の箇所でも四捨五入をすると後ろの部分を捨てることになる。そのために四捨五入の操作出来る回数が無駄になる。tの回数が大きい場合には偶然同じ解になることもあるかもしれないが、最大の数にするためには後ろの数から四捨五入をする意味はないと思う。あとは四捨五入した先の数が9で更に繰り上がる場合とかに気をつけるのかな、多分。