Codeforces Round #323 (Div.2)
はい。
http://codeforces.com/contest/583
A. Asphalting Roads
ざっくりと大意
・都市Xに縦にn本の道路と横にn本の道路が1からn番でナンバリングされており交差点を形成している。
・砂利道は舗装されるべきで計画が立てられた。舗装計画はn2日間で実施される。
・舗装ルールが理解できないが、サンプル1では1日目[1,1]を舗装、2日目[1,2]は1日目に水平道路1が舗装済で何もしない、3日目[2,1]は1日目に垂直道路1が舗装済で何もしない。4日目[2,2]は舗装。答え出力は1 4となる。
方針のようなもの
・サンプル1の通りの処理をする。
n=int(raw_input()) ans=[] hl=range(1,n+1) vl=range(1,n+1) for i in range(n**2): x,y=map(int,raw_input().split()) if x in hl and y in vl: ans.append(str(i+1)) hl.remove(x) vl.remove(y) print ' '.join(ans)
問題文がとにかくよくわからなかった。。水平と垂直の道路は別のリストで管理しないと無理だと思う。
B. Robot's Task
ざっくりと大意
・あとで
方針のようなもの
・あとで
C. GCD Table
ざっくりと大意
・n * nの最大公約数のテーブルがある。
・テーブルの\(g{ij}\)の位置には\(a_i\)と\(a_j\)の最大公約数が入っている。 \(g{ij}\) = gcd(\(a_i\), \(a_j\))
・誰の何を写したのか提出済でACだった。詳細はあとで
方針のようなもの
・詳細はあとで
import collections def gcd(a,b): return a if b==0 else gcd(b,a%b) def lcm(a,b): return a*b/gcd(a,b) n=int(raw_input()) a=map(int,raw_input().split()) a.sort() cnt=collections.defaultdict(int) ans=[] while a: e=a.pop() if cnt[e]>0: cnt[e]-=1 continue for i in ans: g=gcd(i,e) cnt[g]+=2 ans.append(e) print ' '.join(map(str,ans))
あとで