最近プロコン界隈で話題のyukicoderがコンテストを開くとTwitterで知り、とくにすることもなかったので参戦してみました。これが初めてのyukicoderでした。計算量に苦しめられ、2度pythonコードをC++に書き直したりもしましたが、結果としては10問中6問(A,B,C,D,E,G)正解と、今の自分の実力を考えると満足のいく結果でした。問題セットのバランスがすごくよく、楽しいコンテストだったのでぜひ定期的にコンテストを開いてほしいですね。コンテスト結果と問題へのリンクページはこちら。本番に正解できた解答は続きから。

A: No.88 次はどっちだ

先手の名前と、オセロの盤面情報が与えられる。どちらもパスをしていないとして次の手番の人を答える問題。最初全然わからなくて結構焦った。石の総数（または空きの総数）に注目すれば答えられる。

S = raw_input()
B = [raw_input() for _ in range(8)]
empty = sum(B[i].count(".") for i in range(8))
if empty%2 == 0:
    print S
else:
    print {"oda":"yukiko","yukiko":"oda"}[S]

B: No.89 どんどんドーナツどーんといこう！

トーラスの内半径と外半径が与えらるので、その体積に係数をかけて答える問題。トーラスの体積ついてはWikipediaなどを参照のこと。

import math
pi = math.pi
c = int(raw_input())
r,R = map(int,raw_input().split())
r,R = (R-r)/2.0, (R+r)/2.0
print 2*(pi**2)*(r**2)*R*c

C: No.90 品物の並び替え

2以上9以下の品物と、その順番による得点リストが与えられる。得点リストの各行は A, B, C の3つの数字からなり、品物 A が品物 B より前にあるとき得点 C (>0) を得ることができることを意味している。品物を適当に並べたときの総得点の最大値を答える問題。

単純に順列を作成すれば答えられるが、pythonだとぎりぎり間に合わなかった。しかし、pythonで通していた人はいたのでちょっと悔しい。

#include <iostream>
#include <algorithm>
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define REP(i,a) FOR(i,0,a)

using namespace std;
int main(void){
    int n,m;
    cin >> n >> m;
    int score[n][n];
    REP(i,n) REP(j,n) score[i][j] = 0;
    int a,b,c;
    REP(i,m){
        cin >> a >> b >> c;
        score[a][b] = c;
    }
    int item[n];
    REP(i,n) item[i] = i;
    int ans = 0;
    do{
        int tmp = 0;
        REP(i,n-1){
            FOR(j,i+1,n){
                tmp += score[item[i]][item[j]];
            }
        }
        ans = max(ans,tmp);
    }while(next_permutation(item,item+n));
    cout << ans << endl;
}

D: No.91 赤、青、緑の石

赤、青、緑の石がいくつかずつ与えられる。魔法のネックレスは各石１つずつを消費して作られる。ある石２つで別の石１つに交換できるとしたとき、魔法のネックレスは最大いくつ作れるか答える問題。

最初に３つのなかで最低個数の石の分だけ減じておけば、あとは２つの石の個数の場合分けをしながらで答えが求められる。

R,G,B = map(int,raw_input().split())
M = min(R,G,B)
R,G = sorted([R-M,G-M,B-M],reverse = True)[:2]
ans = M
while 1:
    if R >= G > 0 and R >= 3  : R -= 3; G -= 1
    elif G >= R > 0 and G >= 3: R -= 1; G -= 3
    elif G == 0 and R >= 5    : R -= 5
    elif R == 0 and G >= 5    : G -= 5
    else: break
    ans += 1
print ans

E: No.92 逃走経路

N個の街があり、そのなかのある街と街を結ぶ合計M本の道路がある。それぞれの道路には交通料がかかり、ある街と街を結ぶ道路は複数本ある場合がある。指名手配中の犯人の交通料支払い記録が時間順に与えられるので、犯人が潜伏している可能性のある街をすべて答える問題。

ある街から支払い記録の逆順に交通料をたどれるかどうかを調べていけば答えが求められる。あまり効率的なやり方ではないのでpythonだと制限時間ぎりぎりだった。

import sys
sys.setrecursionlimit(10000)

def solve(s,k):
    if k == K: return True
    res = False
    for i in range(N):
        for c in G[s][i]:
            if c == d[k]:
                res = (solve(i,k+1) or res)
                break
        if res: break
    return res

N,M,K = map(int,raw_input().split())
G = [[[] for _ in range(N)] for _ in range(N)]
for roop in range(M):
    a,b,c = map(int,raw_input().split())
    G[a-1][b-1].append(c);G[b-1][a-1].append(c)
d = map(int,raw_input().split())[::-1]

start = []
for s in range(N):
    if solve(s,0):
        start.append(s+1)
print len(start)
print " ".join(map(str,sorted(start)))

G: No.94 圏外です(EASY)

無線を持った二人が通信しようとしている。無線機はそのままでは半径1kmにある無線機としか通信できないが、中継機を経由することで、通信距離を伸ばすことができる。中継機は半径10kmにある中継機と通信することができる。ただし、無線機と中継機は1km以上離れると通信できない。二人の座標と N 機の中継機の座標が与えられるので、二人は直線距離で最大どれだけ離れて通信することができるかを答える問題。N は最大1000、EASYである。

自分は次のように解答した。まず、各中継機間の距離が10km以下かどうかを調べて、直接通信可能な中継機のグラフを作る。あとはワーシャル・フロイド法を用いて各中継器の距離を調べる。距離が有限だとそれらの中継器は通信可能である。あとは (通信可能な各中継機間の距離) + 2 の最大値を答えれば正解となる。Nが最大1000で、ワーシャル・フロイド法はO(N³)なので、pythonだとまったく間に合わないと思う。スタンダードな解法はUnion-Findなどを用いる方法か？

#include <iostream>
#include <algorithm>
#include <math.h>
#define FOR(i,a,b) for(int i=(a); i<b; i++)
#define REP(i,a) FOR(i,0,a)
#define inf (1<<16)
using namespace std;

int G[1000][1000];
int N;

void warshall(){
    REP(k,N)
        REP(i,N)
            REP(j,N)
                G[i][j] = min(G[i][j],G[i][k]+G[k][j]);
}

int S(int ax, int ay, int bx, int by){
    return (bx-ax)*(bx-ax)+(by-ay)*(by-ay);
}

int main(void){
    cin >> N;
    int X[N],Y[N];
    REP(i,N) cin >> X[i] >> Y[i];
    REP(i,N){
        REP(j,N){
            if (S(X[i],Y[i],X[j],Y[j]) <= 100 ){
                G[i][j] = G[j][i] = 1;
            }else{
                G[i][j] = G[j][i] = inf;
            }
        }
    }
    warshall();
    double ans = 1.0;
    REP(i,N)
        REP(j,N)
            if (G[i][j] < inf)
                ans = max(ans,sqrt(S(X[i],Y[i],X[j],Y[j]))+2);
    printf("%.10f",ans);
    return 0;
}