Pythonで逆ポーランド記法の計算

後輩が楽しそうに解いてたので便乗して解いてみました
入力なんかの想定はAOJのコレ

素直に解く

まずはCやJavaなんかで解く時と同じような要領で
演算を辞書に押し込んでしまえば条件分岐が減ってすっきりします

ops = {"+": lambda a, b: b + a,
       "-": lambda a, b: b - a,
       "*": lambda a, b: b * a}
stack = []
for s in raw_input().split():
    if s in ops:
        stack.append(ops[s](stack.pop(), stack.pop()))
    else:
        stack.append(int(s))
print stack[-1]

listを継承して解く

要素を入れたら勝手に合成してくれるstackを作ってみました
あんまり上手な書き方ではないかもしれません

class RPN(list):
    ops = {"+": lambda a, b: b + a,
           "-": lambda a, b: b - a,
           "*": lambda a, b: b * a}
    def __init__(self):
        list.__init__(self)
    def append(self, value):
        if value in self.ops:
            list.append(self, self.ops[value](self.pop(), self.pop()))
        else:
            list.append(self, int(value))

rpn = RPN()    
for s in raw_input().split():
    rpn.append(s)
print rpn[-1]

高階関数を使って解く

組み込み関数のreduceを使って解きます
stackをリレーするイメージ

ops = {"+": lambda a, b: b + a,
       "-": lambda a, b: b - a,
       "*": lambda a, b: b * a}
def calc(stack, s):
    if s in ops:
        stack.append(ops[s](stack.pop(), stack.pop()))
    else:
        stack.append(int(s))
    return stack
print reduce(calc, raw_input().split(), [])[-1]

一行で解く

先の解き方からの発展形
if-elseが面倒でついにevalを使ってしまいましたが、もちろん使わなくても解けます

print reduce(lambda stack, s: stack[:-2] + [eval("{} {} {}".format(stack[-2], s, stack[-1]))] if s in "+-*" else stack + [int(s)], raw_input().split(), [])[-1]

まとめ

一つの問題を解くにもアプローチの仕方は様々
ワンライナーを目指すと2度楽しい

SRM608 div2

250-概要
数直線上を[-A, B]の範囲で動けるロボットがいます。
右(R)か左(L)へ進むよう指示を出します。
初めロボットは0の点に配置されています。
指示が終わったとき、ロボットはどの点にいるでしょう。

解法・感想
minとmaxで範囲を超えないよう押さえ込みます。

ソースコード

from math import *
class OneDimensionalRobotEasy:
    def finalPosition(self, commands, A, B):
        cur = 0
        for c in commands:
            if c == "R":
                cur = min(B, cur + 1)
            elif c == "L":
                cur = max(-A, cur - 1)
        return cur 

600-概要
飴の入った箱が与えられます。
全ての箱の中身を合わせると飴の数はC個になります。
それぞれの箱には、その箱に入っている飴の数の上限が与えられています。
今X個の飴が必要です。
最低でいくつの箱を取り出せば良いでしょう。

解法・感想
(最低限得られる飴の数) = max(0, C - (開けていない箱の上限の和))
あとは上限の大きな箱から開けていき最低限得られる飴の数がXを超えるまで回せば求まります。
tupleで与えられているのを忘れ.sort()を使っていたため弾かれてました。
プラグインに頼り切った結果です。残当。

ソースコード

class MysticAndCandiesEasy:
    def minBoxes(self, C, X, high):
        N = len(high)
        high = list(high)
        high.sort()
        su = [sum(high[:i]) for i in xrange(1, N + 1)]
        for i in xrange(N):
            if C - su[N - i - 1] >= X:
                return i
        return N

1000-概要
隣接行列が与えられます。
ある人が長さLの経路が何通りあるか調べたいそうです。
多項式時間で解けるでしょうか。

解法・感想
ある点を通る閉路（単純閉路？）が二つ以上存在すると指数時間必要になります。
これを求めるには始点（終点）を合流地点とするような二つの閉路の存在を確かめれば十分です。

ソースコード

class BigOEasy:
    def isBounded(self, graph):
        graph = [map(lambda x: x == "Y", g) for g in graph]
        N = len(graph)
        def check(start):
            q = set([start])
            visited = [False] * N
            flag = 0
            while len(q) != 0:
                cur = q.pop()
                for i in xrange(N):
                    if not graph[cur][i] or visited[i]:
                        continue
                    if i == start:
                        flag += 1
                        if flag > 1:
                            return True
                    else:
                        visited[i] = True
                        q.add(i)
            return False
        for i in xrange(N):
            if check(i):
                return "Unbounded"
        return "Bounded"

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