Codeforces Beta Round #71
はい。
http://codeforces.com/contest/79
A. Bus Game
ざっくりと大意
・狐のCielと、兎のHanakoさんは100円x枚と10円y枚から220円を抜いていく。
・先行はCiel抜き方は100円を優先で抜く、後攻はHanako抜き方は10円を優先で抜く。
方針のようなもの
・偶数回・奇数回を上記のルールで抜けなくなるまでループ。
#!/usr/bin/env python # -*- coding: UTF-8 -*- import time import sys, io import re, math #start = time.clock() x,y=map(int,raw_input().split()) #l=[int(x) for x in raw_input().split()] cnt=0 while 1: if cnt%2==0: if x>=2 and y>=2: x-=2 y-=2 elif x>=1 and y>=12: x-=1 y-=12 elif y>=22: y-=22 else: print 'Hanako' sys.exit() else: if y>=22: y-=22 elif x>=1 and y>=12: x-=1 y-=12 elif x>=2 and y>=2: x-=2 y-=2 else: print 'Ciel' sys.exit() cnt+=1
初見では100円・10円の優先なんてあんま関係ないんじゃね??みたいに甘く考えてたら、100円 5枚 10円 12枚とかの状況だと優先が勝敗に大きく影響した。。
B. Colorful Field
ざっくりと大意
・横n 縦mのマスが並んでいて、その中のk箇所の座標には何も植えられない。
・植物はCarrots, Kiwis, Grapes の順で植えられる。
・t箇所のそれぞれの座標がどんな状態か?
方針のようなもの
・自力では無理でした。。
422362のminiputさんの回答をパクリ。
#!/usr/bin/env python # -*- coding: UTF-8 -*- #import time from bisect import bisect #start = time.clock() n,m,k,t=map(int,raw_input().split()) #k回分だけ、Wasteがある回数分だけループ #入力を空白区切りで受け取ってソート #p=sorted(map(int,raw_input().split()) for i in range(k)) p=[map(int,raw_input().split()) for i in range(k)] p.sort() for j in range(t): #何があるか聞かれる座標を受け取る a,b=map(int,raw_input().split()) #座標 p[i] はa,b以降で最も近いWasteの座標が呼べる i=bisect(p,[a,b]) #ということでa,b以降で最も近いWaste座標の1個前とa,bの座標が同じならば #a,bがWasteの位置の座標ということになる if p[i-1]==[a,b]: print 'Waste' #また後で考える else: print ('Carrots','Kiwis','Grapes')[(m*(a-1)+b-i-1)%3]
座標を1<=p<=50000で100万行試してみたけど
#p=sorted(map(int,raw_input().split()) for i in range(k))
と
p.sort()``` どちらでも特に明確に時間差は出なかったと思う。計測メモは省略。ただし100万行をソートするような状況はどちらの方法でもTLEになるかと思う。 [(m*(a-1)+b-i-1)%3] の解読が出来てないけど一旦ここまで。。