Subscribed unsubscribe Subscribe Subscribe

stkblog

白血病と関係ないことを書きます なにかあったら教えて下さい

ARC #046 やった

実ははじめて

arc046.contest.atcoder.jp

2完半(230/400)で49位、10級→6級
目標はAは解いてBは頑張るって感じだったので思ったよりできてよかった

A. ゾロ目数

arc046.contest.atcoder.jp

ゾロ目数リストさえできればなんでもいいはず→適当にforループ
→AC(0:04)

zoro = []

for j in xrange(1, 7):
    for i in xrange(1, 10):
        i = str(i)
        n = i * j
        n = int(n)
        zoro.append(n)

print zoro[input()-1]

B. 石取り大作戦

arc046.contest.atcoder.jp

A=Bのとき部分点らしいのでとりあえず雰囲気で書く→WA(0点)(0:09)

N = input()
A, B = map(int, raw_input().split())
 
if (N-1)%A == 0:
    print 'Aoki'
else:
    print 'Takahashi'

冷静になって書き直す。1手で終わる場合も追加→WA(部分点40点 (0:12)

N = input()
A, B = map(int, raw_input().split())
 
if N <= A:
    print 'Takahashi'
    exit()
 
if N%(A+1) == 0:
    print 'Aoki'
else:
    print 'Takahashi'

下のelse節を考える。こんな単純じゃないと思うけど何個WAになるか見てみよう→AC(!)(0:19)

N = input()
A, B = map(int, raw_input().split())
 
if N <= A:
    print 'Takahashi'
    exit()
 
if A == B:
    if N%(A+1) == 0:
        print 'Aoki'
    else:
        print 'Takahashi'
 
else:
    if A > B:
        print 'Takahashi'
    else:
        print 'Aoki'

C. 合コン大作戦

arc046.contest.atcoder.jp

男をスペック低い順、女を要求低い順に並べといて適当にペアリング→TLEだったりWAだったり(0:31)

N, M = map(int, raw_input().split())
 
mal = [map(int, raw_input().split()) for loop in xrange(N)]
fem = [map(int, raw_input().split()) for loop in xrange(M)]
 
mal.sort()
fem.sort(key=lambda x: x[1])
 
cnt = 0
for f in fem:
    for m in mal:
        if m[1] <= f[0] and f[1] <= m[0]:
            cnt += 1
            mal.remove(m)
            break
print cnt


これは部分点狙いしかない。
部分点のデータセットではBとCは無視していいらしいので、AとDをソートしてスペック低い順と要求低い順に貪欲的にペアリング。
a, d を増やしてく方式*1にしたのでTLEしないはず → WA(部分点30点)(0:56)

N, M = map(int, raw_input().split())
mal = [map(int, raw_input().split()) for loop in xrange(N)]
fem = [map(int, raw_input().split()) for loop in xrange(M)]
 
A = [m[0] for m in mal]
D = [f[1] for f in fem]
 
A.sort()
D.sort()
 
a, d = 0, 0
 
cnt = 0
while a < len(A) and d < len(D):
    if A[a] >= D[d]: #ペア成立
        a += 1
        d += 1
        cnt += 1
    else: #ペア不成立→男は手ぶらで帰宅
        a += 1
 
print cnt

とりあえずシャワー浴びよう(00:57)
終了(1:30)


Cの満点解法は解説みてもよくわかってないので一両日中に理解したい
Dは知らない

いやなことは後まわし

いやなことは後まわし

*1:しゃくとり法ってこういうやつ?→じゃなさそう。名前がわからん