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

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

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

Codeforces Round #304 (Div.2)

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

A. Soldier and Bananas

ざっくりと大意

・w個のバナナが欲しくて1つ目にkドル払う、2つ目に2・kドル払う、3つ目に3・kドル...としていく。
・手持ちnドルでw個買い物するには借金が最低でいくら必要か。

方針のようなもの

・w個になるまでいくら支払うことになるのかを考える。

python

k,n,w=map(int,raw_input().split())
ans=chk=0
for i in range(w):
    n-=k*(i+1)
print 0 if n>=0 else abs(n)

毎回ごとに手持ち金を減算しても、支払額のi・kドルの和を取りつづけて最後に手持ちとの差額を求める方法でもどちらでも大丈夫だと思う。

B. Soldier and Badges

ざっくりと大意

・将軍はn個の勲章を持っていて、n人の兵士に授与したい??
・勲章は1ランク豪華にするのには費用が1掛かる。
・よく解読できないが勲章を同じ価値のものはなく、1つ前のものよりは少なくとも1ランク豪華にする??

方針のようなもの

・ソートして1つ手前のモノより豪華になるように調べる。

python

n=int(raw_input())
l=map(int,raw_input().split())
l.sort()
chk=l[0]
ans=0
for i in range(n):
    if l[i]<chk:
        ans+=(chk-l[i])
        l[i]=chk
    chk=l[i]+1
print ans

まぁ、ソートした後なので1つ手前のものより小さいことはないのですけど。。リアルタイムで参加してた時は手前のものより少なくとも1大きければよいということが書けずに無駄にWAで終わってました。。

C. Soldier and Cards

ざっくりと大意

・n枚のそれぞれ異なる数が書かれたカードでゲームをする。
・お互いに持っているカードから入力データでは左側のもの、解説図では上のものから出して勝負をする。
・数字が大きい方の勝利で、勝者はその手順の時の相手側含む2枚のカードを自分の手元の末尾に数の小さい方から手札に入れる??
・最終的にどちらかの手札が空になるならソレまでの手数と、勝者が先攻/後攻のどちらかを出力する。

方針のようなもの

・シミュレートしたら何か判定が甘くてTLEしたので解説で何回ループ回せばいいのかを見てしまった。。

python

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
from collections import deque
import copy
n=int(raw_input())


def lst():
    x=deque()
    l=map(int,raw_input().split())
    for i in range(1,l[0]+1):
        x.appendleft(l[i])
    return x

l=lst()
r=lst()
tmp_l=copy.copy(l)
tmp_r=copy.copy(r)
cnt=1
t=106
while t:
    p=l.pop()
    q=r.pop()

    if p>q:
        l.appendleft(q)
        l.appendleft(p)
    else:
        r.appendleft(p)
        r.appendleft(q)
    if len(l)==0:
        print cnt,2
        exit()
    elif len(r)==0:
        print cnt,1
        exit()
    elif tmp_r==r and tmp_l==l:
        print -1
        exit()
    cnt+=1
    t-=1
print -1

exit()とか終了条件がかなり雑なのですけど、ソレよりもループ回数が106回で大丈夫な根拠がn=10のときのグラフが106とかなんとかよくわからじ。。。

#