AtCoder Beginner Contest 040 参加記

はい。 ooo- (0/0)
http://abc040.contest.atcoder.jp
仕事休みだったので普通に参加。日本語力で問題文の理解に苦戦したりする。。

A - 赤赤赤赤青

python

n,x=map(int,raw_input().split())
print min(x-1,n-x)

1番目側に寄せるならx-1で、n側に寄せるならn-x。minで最小回数になる。

B - □□□□□

python

IS=float('inf')
ans=IS
n=int(raw_input())
if n==1:
    print 0
    exit()
for i in range(int(n**0.5),0,-1):
    tmp=n/i
    ans=min(ans,(n-i*tmp)+abs(i-tmp))
print ans

手元でテストが少なくてn=1の場合を無駄にWA。。コンテスト中は無駄に1からnまでforで探してたけど、1からnの平方根あたりまで探せば大丈夫そうな気がした。

C - 柱柱柱柱柱

python

IS=float('inf')
n=int(raw_input())
l=map(int,raw_input().split())
l.append(l[-1])
ans=t=0
chk=[IS]*(n+1)
chk[0]=0
while t<n:
    chk[t+1]=min(chk[t+1],chk[t]+abs(l[t+1]-l[t]))
    if t<n-1:
        chk[t+2]=min(chk[t+2],chk[t]+abs(l[t+2]-l[t]))
    t+=1
print chk[-1]

DPっぽいことが必要になるのかと思って当初は諦らめかかった。。nにたどり着くまで1移動と2移動の場合の最小コストを全部調べてれば大丈夫そうなことに気づいてそれでなんとかAC。

D - 道路の老朽化対策について

コードはまたいつかに。。Union-Find使えば良さそうなことまでは気づくが人によって古い道を使えないことの解決法が思いつかず。。道路と人を年でソートしておいて使える道路だけ繋いで同じグループ内の頂点数をみるようにすればなんとかなったらしいです。。気づくべきだった。
pythonで部分点とるのも3日位かかった。。辛い。。

python

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
import time
import sys
import io
import re
import math
import itertools
import collections
import bisect

class UnionFind: #uf=UnionFind(n) で初期化？実行する。nは全体の頂点数
    def __init__(self, size):
        self.rank=[0]*size #高さ管理
        self.par=range(size) #グループの根 初期値は全て自身
        self.g_num=size #グループ数 初期値は頂点数

    def find(self, x): #圧縮
        if x==self.par[x]:
            return x
        self.par[x]=self.find(self.par[x]) #圧縮
        return self.par[x]

    def same(self, x, y): #x,yが同じグループか判定
        return self.find(x)==self.find(y)

    def unite(self, x, y):
        x,y=self.find(x),self.find(y) #findで圧縮発生することあり
        if x==y: #既に同じグループで閉路になる辺
            return
        self.g_num-=1 #違うグループ頂点を結ぶ辺なのでグループ数を1減らす
        if self.rank[x]>self.rank[y]:
            self.par[y]=x

        else:
            self.par[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

    def group_num(self):
        return self.g_num
    def chk_rank(self):
        return self.rank
    def chk_par(self):
        return self.par

n,m=map(int,raw_input().split())

uf=UnionFind(n+1)
q=[]
for i in range(m):
    a,b,y=map(int,raw_input().split())
    q.append((-y,1,a,b))

Q=int(raw_input())
ans=[0]*(Q)
for i in range(Q):
    a,y=map(int,raw_input().split())
    q.append((-y,0,a,i))
q.sort()

for i in q:
    if i[1]==1:
        uf.unite(i[2],i[3])
    else:
        for j in range(n+1):
            uf.find(j)
        tmp=uf.chk_par()
        ans[i[3]]=tmp.count(tmp[i[2]])
for i in ans:
    print i

辺の情報と国民の情報は同じ配列に入れてしまったほうがいいと思う。同年の時は国民が先に出てくるとか、国民の入力された順がわかるとかしないといけないですけど。。 あとACするならpythonでは無理なのでまた後日に。。