Codeforces Round #323 (Div.2) - 君はまるで砂漠に咲く、一輪の花。

A. Asphalting Roads

ざっくりと大意

・都市Xに縦にn本の道路と横にn本の道路が1からn番でナンバリングされており交差点を形成している。
・砂利道は舗装されるべきで計画が立てられた。舗装計画はn²日間で実施される。
・舗装ルールが理解できないが、サンプル1では1日目[1,1]を舗装、2日目[1,2]は1日目に水平道路1が舗装済で何もしない、3日目[2,1]は1日目に垂直道路1が舗装済で何もしない。4日目[2,2]は舗装。答え出力は1 4となる。

方針のようなもの

・サンプル1の通りの処理をする。

python

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だった。詳細はあとで

方針のようなもの

・詳細はあとで

python

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))

あとで