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

A. Display Size

ざっくりと大意

・合計の数がnである画面でb-aの差分が最も小さいものを探す。

Python3

n=int(input())
chk=0
for i in range(1,n+1):
    if i*i>n:
        break
    elif n%i==0:
        chk=i
ans=[min(chk,n//chk),max(chk,n//chk)]
print(*ans)

処理時間: Python3 77ms, PyPy3 109ms
最大を期待できるのはi * i、同じ数同士での掛け算の時なのでそれがnより大きくなったら探索終了できる。それまでの間での最後のnを割り切れるiを解に使う。

B. Mammoth's Genome Decoding

ざっくりと大意

・?をACGTのいずれかに置換して、ACGTのいずれも出現回数が等しいような文字列にする。

Python3

n=int(input())
s=input()
ans=''
chk=[0]*4
for i in s:
    if i=='A':
        chk[0]+=1
    elif i=='C':
        chk[1]+=1
    elif i=='G':
        chk[2]+=1
    elif i=='T':
        chk[3]+=1
for i in s:
    if i!='?':
        ans+=i
    else:
        if min(chk)==chk[0]:
            ans+='A'
            chk[0]+=1
        elif min(chk)==chk[1]:
            ans+='C'
            chk[1]+=1
        elif min(chk)==chk[2]:
            ans+='G'
            chk[2]+=1
        else:
            ans+='T'
            chk[3]+=1
print(ans if len(set(chk))==1 else '===')

処理時間: Python3 77ms, PyPy3 140ms
元々の文字列でのACGTそれぞれの出現回数を数えておいて、解候補の文字列を作成する時に?をもっとも回数が少ない文字に置換して回数は+1しておく。その操作後に出現回数が全て等しくなれば作成した文字列を、そうでなければ===を出力する。

C. Servers

ざっくりと大意

・研究所ではn台のサーバが1からnまでIDがナンバリングされていて、処理予定タスクはq件ある。
・タスクは\(t_i\)秒の時に発生して、\(k_i\)台のサーバが必要、処理には\(d_i\)秒かかる。
・サーバに\(k_i\)台の空きがある場合は最小のIDのものから優先して使用する。
・結果をq行で処理が実施できたタスクは使用したサーバのIDの合計を、処理できなかったら-1を出力する。

D. Winter Is Coming

ざっくりと大意

・n日間の天気情報でそれぞれの日の気温が予めわかっている。
・1セットしかない冬用タイヤはk日間は安全に使用できるが、それをすぎると使用できなくなる。k日は連続した日である必要はない。
・最初は夏タイヤが装備されている。気温がマイナスで日は夏タイヤが使用できるが、マイナスの日は夏タイヤは使用できない(冬タイヤである必要がある)。
・タイヤはいつでも夏、冬のを交換できる。またn日間の終了時にはどちらのタイヤでも良い。

Python3

import heapq

n,k=[int(i) for i in input().split()]
l=[int(i) for i in input().split()]
cnt=[i for i in l if i<0]
m=0
for a,i in enumerate(l):
    if i<0 and m==0:
        m=1
    elif i<0 and l[a-1]>=0:
        m+=1
d={}
q=[]
chk=-1
for i in l:
    if i<0:
        if chk>0:
            if chk in d:
                d[chk]+=1
            else:
                d[chk]=1
                heapq.heappush(q,chk)
        chk=0
    elif chk>=0:
        chk+=1
ans=m*2
k-=len(cnt)
while len(q) and k>=q[0]:
    k-=q[0]
    ans-=2
    d[q[0]]-=1
    if d[q[0]]==0:
        heapq.heappop(q)
if k>=chk and chk>-1:
    ans-=1
print(ans if ans>=0 and k>=0 else -1)

処理時間: Python3 280ms, PyPy3 295ms
純な最多の交換回数は気温がマイナスの日に冬タイヤに変えて、その日に夏タイヤに戻す場合でマイナスの日 * 2回の交換を行う。だが、連続したマイナスの日は夏タイヤに戻して更にまた冬タイヤにする必要がない。そして、マイナスの日の間に０度以上の日があっても耐久日数のkを超えない範囲でそのまま使えば交換回数を2減らせる。また、最終日に冬タイヤでk日使い切るのも良いようなのでそのパターンでは交換回数を1減らせる。
先に優先して2減らすパターンを全部見てから、後に残った使用可能日数で最後のn日まで走れるならば夏タイヤに戻さずに交換回数を１減らしたものが解になる。なお、マイナスの日がkより多いと-1になる。

E. Comments

ざっくりと大意

・図の通り。helloの下には2つの要素があり、その2つのok,byeは共に下に要素が0。testは下に要素が0。oneの下には要素が1つ、その1つのtwoの下には要素が2つでa,b。。。。
・最も深い階層になるのが何段か、と全体で同じ階層のものを1段目から同じ行で出力する。