roiti46's blog

主に競プロ問題の解説を載せてます

Codeforces #281 Div.2

E以外は普段よりも簡単な問題セットだった気がする。A,B,C,D提出したけども、正解したのはB,Dのみ。見直しをきちんとしないといけないよね。問題はこちら

A: Vasya and Football

2チームのどちらかのある選手がレッドカードまたはイエローカードをとった時間が与えられるので、ある選手が初めてレッドカードを貰ったときにチーム名、背番号、時間を答える。レッドカードは複数回与えられることがあるらしい。もはやサッカーではない。

team1 = raw_input()
team2 = raw_input()
red1,red2,yellow1,yellow2 = [],[],[],[]
for roop in range(int(raw_input())):
    t,ha,m,yr = raw_input().split()
    if ha == "h":
        if m in red1: continue
        if yr == "r" or (yr == "y" and m in yellow1):
            print team1,m,t
            red1.append(m)
        else:
            yellow1.append(m)
    else:
        if m in red2: continue
        if yr == "r" or (yr == "y" and m in yellow2):
            print team2,m,t
            red2.append(m)
        else:
            yellow2.append(m)

B: Vasya and Wrestling

レスリングのポイントが時間順に与えられるので、よりポイントを獲得した方、同じ時はポイント配列が辞書順で大きい方、それも同じ時は最後に得点した選手を答える。”辞書順”の説明をきちんと読まないと誤解する可能性がある。

# coding: utf-8
fa,sa = [],[]
n = input()
for roop in range(n):
    a = raw_input()
    if a[0] != "-": fa.append(int(a))
    else: sa.append(int(a[1:]))
else:
    last = a

f,s = sum(fa),sum(fs)
ans = ""
if f > s  : ans = "first"
elif f < s: ans = "second"
else:
    for i,j in zip(fa,sa):
        if   i > j: ans = "first"
        elif i < j: ans = "second"
        if ans: break
    else:
        if   len(fa) > len(sa): ans = "first"
        elif len(fa) < len(sa): ans = "second"
        else:
            if last[0] != "-": ans = "first"
            else: ans = "second"
print ans

C: Vasya and Basketball

2つのチームそれぞれのシュート成功時のゴールからの距離(正の整数)が与えられる。距離dより大きい時に3ポイント、d以下の時は2ポイントとするとき、(チームAの得点)-(チームBの得点)がもっとも大きくなるようにdを設定した時のそれぞれの得点を答える。俺のシュートレンジは無限大なのだよ。

dを(チームAのとあるシュート成功時の距離)-1にしたとき、または無限大のときに(チームAの得点)-(チームBの得点)が最大になる可能性がある。どちらのチームも2ポイントシュートしか打たなかった場合を忘れないように注意。

import bisect
a = input()
A = sorted(map(int,raw_input().split()))
b = input()
B = sorted(map(int,raw_input().split()))
adv = -10**15
pa = pb = 0
for i in range(a):
    d = A[i]-1
    j = bisect.bisect(B,d)
    p1,p2 = 3*(a-i)+2*i,3*(b-j)+2*j
    tmp = p1-p2
    if tmp > adv or (tmp == adv and p1 > pa):
        adv = tmp
        pa,pb = p1,p2
p1,p2 = 2*a,2*b
tmp = p1-p2
if tmp > adv or (tmp == adv and p1 > pa):
    pa,pb = p1,p2
print "%s:%s"%(pa,pb)

D: Vasya and Chess

n×nのチェス盤の左下、右下それぞれに白、黒のクイーンを、それ以外の場所には緑のポーンを置く。白先手で交互に動かしていく。クイーンを動かしても緑のポーンを取れないときまたは相手に駒を取られた時に負けとなる。さてどちらが勝ちますか?白が勝つときは初手の移動先も答えてね。という問題。

紙の上で実験してみるとどうやら偶数の時は白が、奇数の時は黒が勝つらしいと推測できる。提出してみたら正解だった。その理由は次のような説明になると思います。

偶数の時、白はまず右に動いた後、黒の動きを左右反転した真似をすれば勝てる(例:黒が左上に動いたら白は右上に動く)。奇数の場合は白と黒の立場が(n+1)の偶数の場合と逆転したようなものなので黒が勝つ。

n = int(raw_input())
if n%2 == 0:
    print "white"
    print "1 2"
else:
    print "black"

E: Vasya and Polynominal

多項式P(x)について、P(t) = a, P(a) = b という条件が与えられる。これを満たすような0以上の係数の組み合わせの数を答えよという問題。さっぱりわからなかったけれども、下のようなコードで正解らしい。だれか説明お願いします。

t,a,b = map(int,raw_input().split())
if t==2 and a==3 and b>10000: ans = 0
elif a==t:
    if a ==b:ans = 'inf' if a==1 else 2
    else: ans = 0
else:
    if (a-b)%(t-a): ans = 0
    else: ans = 1 if t != b else 0
print ans
広告を非表示にする