読者です 読者をやめる 読者になる 読者になる

君はまるで砂漠に咲く、一輪の花。

僕はその花に引き寄せられる蝶。

Codeforces Round #386 (Div.2)

はい。
http://codeforces.com/contest/746

A. Compote

ざっくりと大意

・材料を1:2:4の比率で使ってCompoteを作る。使う材料の合計はいくつか。

Python3

ans=1001
for i in (1,2,4):
    ans=min(ans,int(input())//i)
print(ans*7)

処理時間:Python3 77ms, PyPy3 156ms
1:2:4の比率で作成できる最大量はそれぞれの1,2,4での商の最小値。最小値だけ保存して最後に1:2:4を、総量7との積が解になる。

B. Decoding

ざっくりと大意

エンコードとデコード。長さnの文字列をデコードして出力する。
・サンプル1のlogvaという文字列のデコードは3文字目にlがきて??l??になる、2文字目にoがきて?ol??になる、そして2番目の位置(lが0番目、oが1番目という数え方?)にgがきて?olg?になる、残りのv,aを順番に使ってvolgaになる。

Python3

n=int(input())
s=input()
ans=''
for a,i in enumerate(s):
    if (a+n)%2:
        ans+=i
    else:
        ans=i+ans
print(ans)

処理時間:Python3 77ms, PyPy3 139ms
サンプル1のNoteの解説を参考にしようとすると惑わされるような気がする。。文字列長の偶奇によって処理方法が異なるのでそれにだけ気をつけてデコード作業すれば大丈夫だと思う。デコードは先頭から文字を取り出して文字列長奇数なら先に左に付け足す、偶数なら先に右に付け足して、以降は左右交互に付け足すとデコード作業完了する。

C. Tram

ざっくりと大意

・Berlandのtramは点0と点sの間を\(t_1\)秒あたり1mの速さで走っている。点0に到達すれば瞬時に点s向きになり、点sに到達すれば瞬時に点0向きになる。
・Igorは点\(x_1\)から点\(x_2\)へ移動したい。Igorは\(t_2\)秒あたり1mの速さで移動できる。
・また、tramとIgorの位置が重なると地点が整数の位置である必要はなく瞬時に乗り込み、いつでも瞬時に降りるなど移動に利用することが可能である。
・また、Igorは任意の地点で立って待つことも可能である?
・pはIgorが\(x_1\)の位置にいるときのTramの位置で、dが-1なら点0へ移動中、dが1なら点sへ移動中。

Python3

s,x1,x2=[int(i) for i in input().split()]
t1,t2=[int(i) for i in input().split()]
p,d=[int(i) for i in input().split()]

ig=abs(x1-x2)*t2
tr=0
while 1:
    if d==1:
        if p<=x1<x2:
            tr+=(x2-p)*t1
            break
        else:
            tr+=(s-p)*t1
            p=s
            d=-1
    else:
        if x2<x1<=p:
            tr+=(p-x2)*t1
            break
        else:
            tr+=p*t1
            p=0
            d=1
print(min(tr,ig))

処理時間:Python3 77ms, PyPy3 124ms Igorが目的地への移動時間の計算は\(x_1\) \(x_2\)の差分と\(t_2\)の積で求まる。Igorがtramに乗ってより早く\(x_2\)へ移動できるのはtramがIgorを追い越して移動した場合のみ。追い越して移動になるのはtramが点sへ向かって移動時に点の位置関係がtram <= \(x_1\) < \(x_2\) の場合のみ。tramが点0へ向かって移動時の点の位置関係は \(x_2\) < \(x_1\) <= pの場合のみ、だと思う。いつでも乗り降り出来るのでIgorが立ち止まって待つという行為は想定する必要はないと思う。重なればいつでも瞬時に乗り降りできるならば立ち止まって待つのも、Igorが移動中の重なった瞬間に乗るのもtramの\(x_2\)への到着時間は変わらないためである。

D. Green and Black Tea

ざっくりと大意

・お茶の合計がn杯ある、内訳は緑茶がa杯で紅茶がb杯である。
・同じ色の茶を連続でkより多くは飲まずにn杯飲みきれるか??

Python3

n,k,a,b=[int(i) for i in input().split()]
t=abs(a-b)
chk=max(1,k-1)
ans=''

if a==b:
    ans='BG'*((n+1)//2)
elif a>b:
    ans+=('G'*k+'B')*(t//chk)
    ans+='G'*max(1,(t%chk))+'B'
    ans+='GB'*(n//2)
else:
    ans+=('B'*k+'G')*(t//chk)
    ans+='B'*max(1,(t%chk))+'G'
    ans+='BG'*(n//2)
ans=ans[:n]
print(ans if ans.count('G')==a else 'NO')

処理時間:Python3 62ms, PyPy3 187ms
私的にはa,bの多い方をa==bになるまで最大kで使い切ってからBGを1つずつ交互に使う方法しか脳内で処理できず。。1度はwhileループで書いたがループ必要なかったのにループしてると入力の内容によってはTLEしたりするのでループなしに書き直し。
a,bの差分とk-1との商がk杯を続けて飲める量になる。a,bの差分とk-1との余りが1以上k以下杯を飲む量になる。あとはa,bが等しい状態になるのでB,Gを交互に飲んで最終型で飲んでいる量と入力のa,bが等しいかを確認して解を出力する。