SRM 600 div2

250-概要
座席数xのバスをy本運行する。バスの運行には１台につきbaseCost + (座席数) * seatCost掛かる。
地点tにはcnt[t]人の乗客がいる。これをすべて乗せなければならない。
バスはy本同時に出発し、スタート地点と地点tを１往復する。
（地点tに複数のバスが向かってもよい。）
座席数、バスの本数を調整した時、最小のコストはいくらか。

解法
１台のバスに積む座席の数を1..max(numbers)に変化させた時のコストを全て調べた。
min(numbers)..max(numbers)でよかった。色々冗長。

ソースコード

from math import *

class TheShuttles:
    def getLeastCost(self, cnt, baseCost, seatCost):
        ret = 1 << 30
        for n in map(float,xrange(1,max(cnt)+1)):
            ret = min(ret,sum(baseCost*ceil(c/n)+seatCost*ceil(c/n)*n
                              for c in map(float,cnt)))
        return ret

600-概要
いくつかの数値numbersと目標の数値goalが一つ与えられる。
or演算によってnumbersからgoalを作るゲームをしている人がいる。
numbersから最低いくつの数値を取り除けば、or演算によってgoalを作れなくすることができるか。

解法
numbersから要素nを取り出し、goal | n > goalならnは不用
考慮する必要がない為これらは初めに取り除く
ここでnum=(110, 101, 010)からgoal=111を作り出すことを考える（いずれも2進数）
このとき1桁目のbitを埋めるにはnum[1]が必ず必要。2桁目を埋めるにはnum[0]かnum[2]が必要。
3桁目を埋めるにはnum[0]かnum[1]が必要。
以上から、少なくともnum[1]を取り除けばgoalを作れなくことがわかる。
また、どのようなnum, goalのときも同じ議論で求めることができる。
つまり (取り除くべき最小の要素数) = min(n桁目を埋めるのに使えるnumの要素数)
簡潔に書けて満足。初めに不用な要素を取り除いたのが良かった。

ソースコード

class ORSolitaireDiv2:
    def getMinimum(self, numbers, goal):
        numbers = filter(lambda x:(goal|x)<=goal,numbers)
        bl = len(format(goal,"b"))
        ret = 1 << 30
        for i in map(lambda x:1<<x,xrange(bl)):
            if i & goal > 0:
                ret = min(ret,len(filter(lambda x:i&x>0,numbers))) 
        return ret

1000-概要

解法
わかんない

POJ 3255: Roadblocks

問題
http://poj.org/problem?id=3255

概要
1番目の頂点からN番目の頂点への経路の内二番目に短いものの長さを求めよ。
（最短経路が二つ以上ある場合、その値を出力）

解法・感想
アリ本p102より。ダイクストラ法の改良。
最小の距離と二番目に小さい距離をdist,dist2に記憶するようダイクストラ法を進めればOKです。
ただし、既に通った/通っていないかでヒープに追加するかの判断はできません。
また、1->2->1->2のような経路がdist2となる場合もあるので注意が必要です。
アリ本ではdist2を更新するブロックで
if(dist2[e.to] > d2 && dist[e.to] < d2)
となっていますが、dist[e.to] < d2 は不要です

ソースコード

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
#define INF (1 << 30)
#define MAX_N 5001
#define MAX_R 100001
#define DBG 0
using namespace std;
int N,R;
struct edge{int to, cost;};
typedef pair<int, int> P;
vector<edge> G[MAX_N];

int dist[MAX_N];
int dist2[MAX_N];

void solve(){
  priority_queue<P, vector<P>, greater<P> > pq;
  fill(dist, dist+N, INF);
  fill(dist2, dist2+N, INF);
  dist[0] = 0;
  pq.push(P(0, 0));
  while(!pq.empty()){
 P p = pq.top();
 if(DBG){
   cout << p.first << " " << p.second << endl;
 }
 pq.pop();
 int v = p.second, d = p.first;
 if(dist2[v] < d){
   continue;
 }
 for(int i = 0; i < G[v].size(); i++){
   edge &e = G[v][i];
   int d2 = d + e.cost;
   if(dist[e.to] > d2){
  swap(dist[e.to], d2);
  pq.push(P(dist[e.to], e.to));
   }
   if(dist2[e.to] > d2){
  dist2[e.to] = d2;
  pq.push(P(dist2[e.to], e.to));
   }
 }
  }
  cout << dist2[N-1] << endl;
}

int main(){
  cin >> N >> R;
  for(int i = 0; i < R; i++){
 int s,t,c;
 scanf("%d %d %d", &s, &t, &c);
 G[s-1].push_back((edge){t-1, c});
 G[t-1].push_back((edge){s-1, c});
  }
  solve();
  return 0;
}

こっちの方が個人的にはわかりやすい。

if(dist2[e.to] > d2){
    dist2[e.to] = d2;
    if(dist[e.to] > dist2[e.to]){
        swap(dist[e.to], dist2[e.to]);
        pq.push(P(dist[e.to], e.to));
    }
    else{
        pq.push(P(dist2[e.to], e.to));
    }
}

POJ 1182: 食物链

問題
http://poj.org/problem?id=1182

概要
動物がN匹いて、1..Nの番号が振られている。
動物はA,B,Cの3種に分けられ、A->B->C->Aの強弱関係。
次の2種類の情報が順番にk個与えられる。

1. xはy同じ種類
2. xはyを食べる

逐次処理したとき矛盾する情報はいくつ出てくるか。
ただし矛盾した情報はその場で捨て、以降考慮しないで良い。

解法・感想
アリ本p85より。Union-Find木を使います。
A,B,C用の配列を作ったらダメだし...と明後日の方向を見つめていた為、init(N*3)に目から鱗でした。
ただ、感動した割にpar[MAX_N*3]としないで弾かれるあたりが限界です。
最大入力数が10万と大きいため、cinを使うと弾かれます。

ソースコード

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
#define MAX_N 50001
#define MAX_K 100001
#define DBG 0
using namespace std;
int par[MAX_N*3];
int rank[MAX_N*3];
int N,K;
int T[MAX_K],X[MAX_K],Y[MAX_K];

// n要素で初期化
void init(int n){
  for(int i = 0; i < n; i++){
 par[i] = i;
 rank[i] = 0;
  }
}

//木の根を求める
int find(int x){
  if(par[x] == x){
 return x;
  }
  else{
 return par[x] = find(par[x]);
  }
}

//xとyの属する集合を併合
void unite(int x, int y){
  x = find(x);
  y = find(y);
  if(x==y){
 return ;
  }
  
  if (rank[x] < rank[y]){
 par[x] = y;
  }
  else{
 par[y] = x;
 if(rank[x] == rank[y]){
   rank[x] += 1;
 }
  }
}  
// xとyが同じ集合に属するか否か
bool same(int x, int y){
  return find(x) == find(y);
}

void solve(){
  init(N*3);
  
  int ans = 0;
  for(int i = 0; i < K; i++){
 int t = T[i];
 int x = X[i] - 1, y = Y[i] - 1;
 if(x < 0 || N <= x || y < 0 || N <= y){
   ans += 1;
   if(DBG){
  cout << i << endl;
   }
   continue;
 }
 
 if(t == 1){
   if(same(x, y+N) || same(x, y+2*N)){
  ans += 1;
  if(DBG){
    cout << i << endl;
  }
   }
   else{
  unite(x, y);
  unite(x+N, y+N);
  unite(x+2*N, y+2*N);
   }
 }
 else{
   if(same(x, y) || same(x, y+2*N)){
  ans += 1;
  if(DBG){
    cout << i << endl;
  }
   }
   else{
  unite(x, y+N);
  unite(x+N, y+2*N);
  unite(x+2*N, y);
   }
 }
  }
  cout << ans << endl;
}

int main(){
  cin >> N >> K;
  for(int i = 0; i < K; i++){
 scanf("%d %d %d", &T[i], &X[i], &Y[i]);
  }
  solve();
  return 0;
}

AOJ 1163: Cards

問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1163&lang=jp

概要
2以上10000000未満の数値が書かれた青と赤のカードが複数与えられる。2以上の公約数を持つような赤と青のペアは最大でいくつ作れるか。

解法
二部マッチング。アリ本p197をそのまま写しました。
入力が特殊な為、言語によっては注意が必要です。
enumerateがstartを指定できることを知った。幸せ。
20秒強掛かったので直すべき箇所があるかもしれません。

ソースコード

from fractions import gcd
 
V = 1002
G = []
visited = []
match = []
 
def add_edge(u,v):
    G[u].append(v)
    G[v].append(u)
 
def dfs(v):
    visited[v] = True
    for u in G[v]:
        w = match[u]
        if w < 0 or not visited[w] and dfs(w):
            match[v] = u
            match[u] = v
            return True
 
def bipartite_matching():
    global match,visited
    res = 0
    match = [-1]*V
    for v in xrange(V):
        if match[v] < 0:
            visited = [False]*V
            if dfs(v):
                res += 1
    return res
 
while True:
    m,n = map(int,raw_input().split())
    if (m,n) == (0,0):
        break
    V = m+n+2
    G = [[] for _ in xrange(V)]
    visited = [True] * V
    data = []
    while len(data) < n+m:
        data += map(int,raw_input().split()) 
    for i,b in enumerate(data[:m]):
        for j,r in enumerate(data[m:],m):
            if gcd(b,r) != 1:
                add_edge(i,j)
    print bipartite_matching()