Regionals 2011 :: Asia - Dhaka

Live Archive

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=518

Binary Matrix

問題

要素が1,0のみのN×M行列が与えられる。
隣接する要素同士をスワップするという操作のみ認められる。
ただし、1行目とN行目のスワップや、１列目とM列目のスワップも認められる
全ての行の1の数が等しく、全ての列の1の数が等しくなるようにしたい。
どちらも可能か、行のみ可能か、列のみ可能か、どちらも不可能か、
また、そのとき最小で何回のスワップが必要かを求めよ。

制約

2 ≤ M, N ≤ 1000

解法

行と列は別々に考える。
i行の1の数をaiとすると、aiから1ずつ隣接するajのどちらかに値を移動することが出来るときaiの値を等しくするという問題になる。
これは最小費用流で解くことが出来る。

中央値解法

http://one-problem-a-day.blogspot.jp/2011/08/uva-11300-spreading-wealth.html
sumをaiの合計とする。
sumがnで割り切れなければ、aiを同じ値にすることはできない。
割り切れる時を考える。
per = sum / n とする。
x(p,p+1)を、pからp+1に移す値とする(mod n)。
x(i-1,i) - x(i,i+1) = per - a[i]
が成り立つ。
A[i] = per - a[i]とすると

x(0,1) = A[1] + x(1,2)
x(1,2) = A[2] + x(2,3)
.............
x(n-2, n-1) = A[n-1] + x(n-1, 0)
x(n-1, 0) = A[0] + x(0, 1)

右辺を変数x(n-1,0)だけで表現すると、

x(n-1, 0) = 0 + x(n-1, 0)
x(n-2, n-1) = A[n-1] + x(n-1, 0)
x(n-3, n-2) = A[n-2] + x(n-2, n-1) = A[n-2] + A[n-1] + x(n-1, 0)
..............
x(1,2) = A[2] + A[3] + ... + A[n-1] + x(n-1, 0)
x(0,1) = A[1] + A[2] + A[3] + ... + A[n-1] + x(n-1, 0)


B[i] = 0 + A[1] + ... + A[i]
とする。

x(0,1) + x(1,2) + .... + x(n-1,0) が最小になるようにするには、

x(n-1,0)をB[0]...B[n-1]の中央値のマイナスにすればよい。
すなわち中央値をmedとすると、

x(0,1) + x(1,2) + ... + x(n-1,0) の最小値は
B[0]-med + B[1]-med + ... + B[n-1]-med となる。

これは、min{|y1-x| + |y2-x| + ... + |yn-x|}を考えたとき、
それぞれの項のグラフを考えると分かる。

Candles

問題

0から9の数字プレートが1枚ずつある。
この数字プレートを使ってn個の数字を表したい。
数字プレートの他に+と書かれた特殊なプレートを使うことで、和として表すこともできる。
例えば12は、2+10, 3+9, 4+8, 5+7, 7+5, 8+4, 9+3, 10+2, 12 として表すことが出来る。
ここで例えば10は、プレート1とプレート0を並べて作ることが出来る。
n個の数字を表せるような数字プレートの部分集合で、要素数をできるだけ小さいものを求めよ。

制約

1<=n<=10
1<=表したい値<=100

解法

まず全ての部分集合に対して、表すことの出来る数字を全て列挙する。
表したい値が100までしか無いことに注目すると、表し方としては、

  • 1枚のプレート
  • 2枚のプレートを並べる
  • 2枚のプレートの和
  • 2枚のプレートを並べたものと1枚のプレートの和
  • 2枚のプレートを並べたもの×2の和

の5パターンしか無い。
あとは、n個の数字を全て表せるような部分集合のうち要素数が最小のものを選べば良い。
前処理にsetを使ってO(2^n*n^4*log(n))
各テストケースに対してO(2^n*n)

Cards

問題

ジョーカー2枚入りのトランプをシャッフルしてデッキを作り、上から順にスートごとに分けて置いていく。
このときC枚のクラブ、D枚のダイヤ、H枚のハート、S枚のスペードが出るまでに置くカードの枚数の期待値を求めよ。
ただしジョーカーを引いたときは、そのジョーカーをある1つのスートに属するとみなして置く事ができる。
ここでジョーカーが属するスートは求めたい期待値が最小になるように決めるとする。

制約

0<=C,D,H,S<=15

解法

dp[c][d][h][s][j1][j2] =
クラブをc枚、ダイヤをd枚、ハートをh枚、スペードをs枚引き、
j1 = 0ならジョーカーをまだ引いてない
j1 = {1,2,3,4}ならジョーカーを引き{クラブ,ダイヤ,ハード,スペード}とみなした
j2についても同様
なときに後何枚トランプを必要があるかの期待値としてDPかメモ化再帰。
メモ化再帰のほうが楽そう。

Game of Connect

保留

Guards

問題

N×Nのフィールドがあり、2N個の丸を各行各列にちょうど２つの丸があるように配置する。
同じ行、同じ列の丸を線で結んだときサイクルがK個あるようにしたい。
このような丸の配置の仕方は難通りあるか求めよ。

制約

2 ≤ N ≤ 105, 1 ≤ K ≤ min(N, 50)

解法

dp1[n][k] = n×nのフィールドで、サイクルがkであるような配置の仕方
dp2[n][k] = (n-1)×nのフィールドで、既に2つの列には丸が（フィールドの外側で）配置されているとき、サイクルがkであるような配置の仕方

dp1[n][k]

１列目に丸を２つ配置する（n*(n-1)/2通り）
１列目に配置した２つの丸と同じ行に丸を１つずつ配置する。

  • 同じ列に配置（n-1通り）　：　サイクルが出来る　→　dp1[n-2][k-1]へ
  • 違う列に配置（(n-1)*(n-2)通り）　：　サイクルは（まだ）出来てない　→　dp2[n-1][k]へ

以上より、
dp1[n][k] = n*(n-1)/2 * (n-1) * dp1[n-2][k-1] + n*(n-1)/2 * (n-1) * (n-2) * dp2[n-1][k]

dp2[n][k]

既に丸が（フィールドの外側で）配置されている２つの列に丸を配置することを考える。

  • 同じ行に配置（n-1通り）　：　サイクルが出来る　→　dp1[n-2][k-1]へ
  • 違う行に配置（(n-1)*(n-2)通り）　：　サイクルは（まだ）出来てない　→　dp2[n-1][k]へ　（行と列が逆になるが、対称なので問題ない）

以上より、
dp2[n][k] = (n-1) * dp1[n-2][k-1] + (n-1)*(n-2) * dp2[n-1][k]

Packing for Holiday

やるだけ

Pair of Touching Circles

問題

W×Hのグリッドがある。
このグリッドに円を２つ書く。
円は以下の条件を満たす。

  • ２つの円は接する
  • ２つの円の共通部分はない
  • 円の中心は整数座標
  • 円の半径は整数

このとき、円の書き方の総数を求めよ。

制約

0 < H, W ≤ 1000

解法

整数cに対して、
mp[c] = √(a^2+b^2)を満たす(a,b)のリスト
を求めておく。
２つの円の半径に関して二重ループを回して、
円を軸に平行に置いたとき、ずらして置いたときそれぞれについて、場合の数を計算する。
１つの円を含む最小正方形にもう一方の円が完全に内包されることもあることに注意。

Treasure Hunt

問題

長方形領域に４人が落ちる。
長方形領域は（多分１点で支えられていて）最初バランスが取れているが、
４人が落ちたことによってバランスが崩れてしまうので、４人はバランスが取れるように移動する。
４人の移動量の総和が最小になるように移動したとき、４人の最終的な位置を出力せよ。
ただし４人の体重は同じ。

制約
解法

長方形領域の重心をG、４人の重心をOとすると、４人の重心をOからGに移動させれば良いことが分かる。
そこで、４人をベクトルOGだけ動かせば良い。
もしある人が長方形領域から外れてしまう場合は、その人は端まで移動させておいて、他の人でその分を賄うという感じでできる。

Truchet Tiling

https://icpcarchive.ecs.baylor.edu/external/58/5817.html

問題

図のようなmotifが２種類あり、R×Cのセルが埋められている。
各クエリで座標が与えられるので、その座標を含む領域の面積を求めよ。

制約

0 < R, C ≤ 100
1 ≤ Q ≤ 100

解法

１つのセルを、LEFT,CENTER,RIGHTという３つの領域にわけて考える。
Union-Findを用いて各セル各領域の接続関係を求め、同時に面積も足し合わせることで計算する。
各クエリに対しては、その座標がどの領域に含まれるのかを判定してUnion-Findで求めておいた面積を出力すれば良い。
O(RCα+Qα)
O(RCQ)も許されると思うのでBFSでも良いはず。

As Long as I Learn, I Live

問題文に書いてある貪欲グラフ探索を実装するだけ

Regionals 2011 :: Asia - Kanpur

Live Archive

Strongly Connected Chemicals

問題

(V=L∪R,E)な2部グラフGが与えられる。
L'⊂L,R'⊂R（|L'|>=1, |R'|>=1）なL',R'を選んで、
全ての(i,j)∈L'×R'の間に辺があるようにしたい。
このとき|L'|+|R'|の和の最大値を求めよ。

制約

1 ≤ m, n ≤ 50

解法

L'=ΦもしくはR'=Φも許す場合は2部クリークというらしい。
最大クリークは補グラフに対する最大独立集合と等価らしい。
2部グラフの最大独立集合は(頂点数-最大マッチング)となる。
これで2部クリークは解けるが、この問題は左の頂点と右の頂点をそれぞれ1つ以上選ばなければならない。
そこで、頂点a(∈L)と頂点b(∈R)（(a,b)∈E）は必ず選ぶことにして、
~L = {i∈L | (i,b)∈E}
~R = {j∈R | (a,j)∈E}
~G = 頂点~L∪~RなGの部分誘導グラフ
としたとき、~Gの最大2部クリーク+2の最大値が答えになる。

Confusion in the Problem Set

問題

a[0],a[1],...,a[n-1]が与えられる。
a[i]を並べ替えて、
a[i] ∈ {i, n-i-1}
を満たすようにしたい。
このような並べ替え方法があるか判定せよ。

制約

T<=60
n<=10^4
a[i]<=10^6

解法

b[i] = iまたはn-i-1の数 (i < (n+1)/2)
とする。
nが偶数のとき、b[i] > 2なるb[i]があったらno。
nが奇数のとき、b[i]>2,i1ならばno。
それ以外ならyes。

LCM Extreme

問題

[tex:\sum_{1<=i

制約

T <= 25000
n <= 5*10^6

解法

http://apps.topcoder.com/forums/?module=Thread&threadID=729936&start=0&mc=2#1473205
の通り実装したら通った。
S(n) = n*(1+S2(n))/2
を計算するときに2で割るのに躊躇したが、
少なくともnや1+S2(n)はunsigned long longの範囲を超えないので大丈夫だった。

Tetromino

10^6*log(N)くらいに出来るのかなあ・・・

Blade and Sword

ただのBFS

The Falling Circle

問題

円c1,円c2,円cが与えられる。
c1とc2の接線のうち、接点のy座標が中心のy座標より小さいものが地面となる。
円cはこの地面より上にあり、秒速1で落ちる。
地面まで落ちたら地面が傾いている方に転がり、c1もしくはc2にぶつかったら止まる。
ここで、c1とc2の間に落ちることは保証される。
cは1秒で1回転する。
このとき、cが落ち始めてから止まるまでにかかる時間を求めよ。
ただし地面が傾いていなければ落ちた所で止まる。

制約

T<=10000

座標 <=10^5

1<=半径<=100

解法

接線は上手いこと下側のもの１つを取ってくるようにする。
接線を表すときに(c1における接点),(c2における接点)を保持しておくと良い。
地面と落ちたとき円cの中心がどこになるかは二分探索で求めた。
転がる距離は点と直線の距離と三平方の定理を用いることで求まる。

My Visit to Spring Secret

超やるだけ

Scrabble

無かった

An Average Game

問題

数列a[1],..a[n]がある。
クエリがQ個来るので、各クエリに対して
a[li],...,a[ri]をセットに入れたときの値の平均を求めよ。

制約

T<=100
n<=10^4

a[i] <=10^9

Q<=10^5

解法

数列aを平方分割する。
またa[i]を座標圧縮して0~hogeの値として考え、要素数10000テーブルに入れられるようにする。
座標圧縮後のa[i]に対応する値をb[i]とする。
前処理として、

をO(n√n)で求めておく。

クエリに対しては、
liに対応するバケットをlid, riに対応するバケットをridとすると、
p[rid][b[i]] - p[lid+1][b[i]] == 0
であるとき、間に挟まれたバケットに関してb[i]は現れてないことが分かる。
この事実と、SUM、NUMを使うことで、
liからriまでのdistinctな値の和と数を求めて平均を算出する。
これはO(√n)で行うことが出来る。

よって計算量O(n√n + Q√n)
で解ける。

Permutation Counting

問題

1~nの順列で、a,a+1がこの順で隣接しているような部分がないものの数を求めよ。

制約

T <= 10000
1 ≤ N ≤ 10^6

解法

http://oeis.org/A000255
OEIS無しだとどう考えたら解けるんだろう

立命合宿2013参加記

その他コンテスト

3/11~3/13に立命館で行われたプロコン合宿に行って来ました。
主にコンテストの反省書きます。

1日目

  • チーム名はevisuto、チームメイトはevimaさんとtokoharuさん
  • 結果は3位
感想

強いお二人と組めてとても楽しかった。
びっくりするくらい楽しかった。
Fは見たことあるような問題だったのですぐ解けてFirstACをゲットした。
Cは３人デバッグ体制で望んだが通らず。
ジャッジの解答がおかしかった（というか問題文の記述が不適当だった？）らしい。

2日目

  • チーム名はSAK2、チームメイトはきゅうりさん、kawashiroさん（若い！）
  • 結果は6位
感想

阪大セットということで、さすが良問揃いですごい。
Fはそれっぽい実装を適当にやったら通ってしまった。
Iが通ったのがめちゃくちゃ嬉しい。積分力ほしいです。

3日目

  • チーム名はKITSUNE_KON、チームメイトはjapljさん、climpetさん
  • 結果は1位！
感想

Bを解かせて頂いたが、この日だけ自分のではないパソコンでやったこともあり、
ひどく時間がかかった挙句2WAというとんでもない失態を犯してしまった。
ということでその後は一切実装せず後ろから見守る係となった。
japljさん実装力ぱない〜
climpetさんEを謎解法で通してぱない〜
とか思っていたら1位になっていた。
実はEは嘘解法でFはジャッジと同じミスをした解法だったので、幻の1位だったっぽい。

全体の感想

Twitterやコンテストで名前は知っているものの、今まで絡んだことのなかった人達とチームを組めて楽しかった。
2Dさん始め立命の人たちに感謝です。
あと「3人組作って〜」フェイズで救いの誘導をしてくれたkioaさんが神様に見えた。
来年もあるといいなあ。

Regionals 2009 :: Europe - Northwestern

Live Archive 練習会

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=362

A - 4609 - An Industrial Spy

篩＆全探索という日本のICPCによくありそうな問題

B - 4610 - Common Subexpression Elimination

問題

二分木を縮約する。
文字列表現した際に、前に出てきた部分木は出てきた順に付けられた番号によって置き換える。

制約

ノード数 <= 50000

解法

パースするときに、今見ている部分木をエンコードし、既に出てきた部分木と同じであればその番号に対応させる。
このとき、全ての部分木は順番に番号（答えの番号とは違う）をつける。
ここで、同じ形をした部分木は違う場所に現れていても同じ番号が振られる。
部分木をエンコードするには、ノード名と左右の子の番号を用いれば良い。

C - 4611 - Divisible Subsequences

部分和のmodを取ったときの値がそれぞれ何回現れたかのテーブルを用意し、ループを回せば出来る。

D - 4612 - Fractal

問題

折れ線が与えられる。
折れ線の各線分に同じ折れ線を縮小・回転して埋め込むという操作を、再帰的にd-1回行なってフラクタルを作る。
このフラクタルにおいて、始点から割合f進んだ場所の座標を求めよ。

制約

頂点数<=100
d <= 10

解法

フラクタルを構成しても、初めの折れ線の各線分に対応する部分の長さの全体からの割合は変わらない。
そこでまず、初めの折れ線の、どの部分に目標とする点が存在するかを見つける。
どの部分か分かったら、折れ線を縮小・回転し、新たな折れ線とする。
また、割合fもその部分の中での割合になるように適切に変更する。
このような操作を全部でd回行う。
d回行った後は、現在の折れ線の始点と終点をf:(1-f)に内分する点を答えとすれば良い。

E - 4613 - Mountain Road

問題

1本道を両方の向き（両端をA、Bとする）に計n台の車が通る。
道は狭いので、一方の向きから車が通ってる時は、もう一方の向きから車は通れない。
また安全のため、同じ向きの場合、ある点を車が通過したあと10秒未満で他の車が通過することは許されない。
車がA、Bどちらから通るか、何秒にスタートできる状態になるか、道を通過するのに何秒かかるか、が与えられる。
このとき、車が全て通過し終わるのにかかる時間の最小を求めよ。
ただし、A,Bそれぞれに対し、先にスタートできる状態になった車が先にスタートする（待っている車の順番を入れ替えることは出来ない）。

制約

n <= 200

解法

dp[i][j][k] = Aの車がi台、Bの車がj台通過し終わっており、前に通過し終わったのが{A(k=0)/B(k=1)}のときの最短時間
初期値は、dp[0][0][0]=dp[0][0][1]=0,それ以外INF。
更新のときは、AまたはBから車を一気に通すことを考える。
このとき10秒制約に注意して、次の車がスタート出来る最短時間とゴール出来る最短時間を保持して利用する。
計算量はO(n^3)となる。

F - 4614 - Moving to Nuremberg

問題

重み付きの木が与えられる。
このとき、以下の和の最小値と、最小値を達成するuを全て求めよ。
\sum_v 2dist(u,v)f[v]　・・・　☆

制約

頂点数 <= 50000

解法

まず、ある頂点における☆をO(n)で求め、その頂点から１つ動いた時の☆をO(1)で求めることを繰り返すことにより、全体としてO(n)で全てのuについて☆を求める。
適当に根を決めて、DFSすることにより、頂点i以下のfの和sum[i]を求めておく。
また、根における☆もDFSで求まる。
１つ動いたとき、☆がどう変わるかはsum[i]を上手く使うことによって求めることが出来る。
intでは微妙にオーバーフローするので注意。

G - 4615 - Room Assignments

問題

n人とn部屋がある。
n人は1部屋に割り当てられ、1部屋に複数人が割り当てられることは許されない。
n人は、部屋を2つ希望することができる。
n人がコインを投げ、裏表によって希望した２つの部屋のうち、どちらかが採用される。
このとき、割り当てに失敗したら、成功するまで繰り返す。
何回やっても失敗するときは誰も部屋に割り当てられずに終わる。
今、n-1人の希望は揃っている。
最後の１人はどの部屋を希望すれば、得られる満足度の期待値を最大に出来るか。
ある部屋に割り当てられた時の満足度は与えられる。
どうやっても失敗に終わるときはImpossible。
部屋の選び方が複数あるときは辞書順最小。

制約

n <= 50000

解法

人と部屋の関係は特殊な二部グラフとなる。
ここではまだn-1人分を考える。
連結成分に分けた時、人に対応する頂点数をn1、部屋に対応する頂点数をn2とする。
このとき、以下が成り立つ。

  1. n1>n2のとき、割り当ては存在しない。
  2. n1=n2のとき、条件を満たす割り当てが存在する。
  3. n1

n1=n2のときの条件を満たす割り当ての存在性は、部屋から１本しか辺が出てないときその辺が接続する頂点を消去すると、単純な閉路しか残らないことから言える気がする。
n1

  • n1>n2な成分があればimpossible
  • 成分が１つの時は満足度が大きい２つ
  • それ以外では、n1=n2-1となる成分における満足度が大きい部屋と、同じ成分で満足度が同じ値もしくは他の成分の部屋

で解けるが、辞書順最小もあり結構だるい。

H - 4616 - Settlers of Catan

六角座標における螺旋の動きを実装するだけ。

I - 4617 - Simple Polygon

問題

自己交差のないように与えられた点を頂点とする多角形を構成せよ。

制約

点数<=2000

解法

凸包を下半分作り、あとはx座標の順に点を選んでいく。
凸包を使わない方法ってなんだろ。

J - 4618 - Wormholes

ベルマンフォードを何回かやるっぽいけど何で動くのか良く分からん。

KUIS卒論諮問会頻出質問集?

研究

昨日発表してきました
疲れた

↓頻出順（適当）

  • この研究のポイント（困難な点、自分がやった点、工夫点、新規性）は？
  • （参考文献を見て）本当にちゃんと調べた？
  • 何がしたかったの？（目的が分からん、目的と手法があってない、目的と評価方法があってない）
  • 変な工夫しなくても○○の手法が自然じゃない？
  • 比較実験では公平な比較をしている？
  • 考察は？（何で良くなったのか、何で良くならなかったのか）
  • 誰がこの技術を使うの？何の役に立つの？

補足

分からん質問には分からんというのが吉
あまりに分からんかったらオイオイとなる

各種典型再帰関数を非再帰に変換する

雑記

再帰関数はあんまり再帰が深くなるとスタックオーバーフローの危険があり、できれば非再帰で処理を書きたいというケースが稀にある。
再帰関数はスタックを使えば非再帰で書けるとたまに聞くが、実際どうやれば良いか分からなかったので調べてみた。
典型的な再帰関数について、非再帰バージョンの書き方を以下にまとめる。

階乗

簡単にループで書ける。
末尾再帰なので末尾再帰 - Wikipediaのように簡単に変換できる。
再帰版

int factorial(int n) {
  if (n == 0) return 1;
  else return n * factorial(n-1);
}

非再帰版
次のGCDに合わせてちょっと変な書き方。

int factorial2(int n) {
  int res = 1;
  while(1) {
    if (n == 0) return res;
    else {
      res *= n;
      n--;
    }
  }
}

最大公約数（ユークリッドの互除法）

階乗と同じ感じ。
再帰版

int gcd(int a, int b) {
  if (b == 0) return a;
  else return gcd(b,a%b);
}

非再帰版

int gcd2(int a, int b) {
  while(1) {
    if (b == 0) return a;
    int t = a;
    a = b;
    b = t%b;
  }
}

アッカーマン関数

末尾再帰にできない。
再帰版

int ack(int m, int n) {
  if (m == 0) return n+1;
  if (n == 0) return ack(m-1,1);
  else return ack(m-1,ack(m,n-1));
}

できるだけループにしてみる。

int ack2(int m, int n) {
  while(1) {
    if (m == 0) return n+1;
    else if (n == 0) {
      m--;
      n = 1;
    } else {
      n = ack2(m,n-1); // ☆ 
      m--;
    }
  }
}

スタックを使って非再帰にする

int ack3(int m, int n) {
  stack<int> S;
  while(1) {
    if (m == 0) {
      n++;
      if (S.empty()) return n;
      else {
        m = S.top(); S.pop();
      }
    } else if (n == 0) {
      m--;
      n = 1;
    } else {
      // ack2の☆部分を今から計算する
      // ☆部分の計算が終わったらスタックからm-1を取り出して先に進めるようにする
      S.push(m-1);　 
      n--;
    }
  }
}

ハノイの塔

アッカーマン関数とだいたい同じ
再帰版

void hanoi(int n, char from, char work, char to) {
  if (n == 1) {
    printf("%c -> %c\n", from, to);
  } else {
    hanoi(n-1, from, to, work);
    printf("%c -> %c\n", from, to);
    hanoi(n-1, work, from, to);
  }
}

できるだけループに

void hanoi2(int n, char from, char work, char to) {
  while(1) {
    if (n == 1) {
      printf("%c -> %c\n", from, to);
      return;
    } else {
      hanoi2(n-1, from, to, work);
      printf("%c -> %c\n", from, to);
      n--; swap(work,from);
    }
  }
}

スタックを使って非再帰に。
スタックには元に戻るために必要な情報をすべて積んでおく。

struct P {
  int n;
  char from, work, to;
};
void hanoi3(int n, char from, char work, char to) {
  stack<P> S;
  while(1) {
    if (n == 1) {
      printf("%c -> %c\n", from, to);
      if (S.empty()) {
        return;
      } else {
        P p = S.top(); S.pop();
        n = p.n, from = p.from, to = p.to, work = p.work;
        printf("%c -> %c\n", from, to);
        n--; swap(work,from);
      }
    } else {
      S.push((P){n,from,work,to});
      n--;
      swap(work,to);
    }
  }
}

再帰下降構文解析

いきなりレベルアップ。
文法としては、括弧と+と-と*があるような数式を対象とする。
例えば、"2+3*(4+7)"

char s[1010]; // パースする文字列が入っている

int term(int &i);
int fact(int &i);

int exp(int &i) {
  int p = term(i);
  while(s[i]=='+' || s[i]=='-') {
    char c = s[i++];
    if (c == '+') {
      int a = term(i);
      p += a;
    }
    else p -= term(i);
  }
  return p;
}

int term(int &i) {
  int p = fact(i);
  while(s[i]=='*') {
    i++;
    p *= fact(i);
  }
  return p;
}

int fact(int &i) {
  if (s[i] == '(') {
    i++;
    int p = exp(i);
    assert(s[i++]==')');
    return p;
  } else {
    int num = 0;
    while(isdigit(s[i])) {
      num *= 10;
      num += s[i]-'0';
      i++;
    }
    return num;
  }
}

とりあえず関数を１つにしてみる。

char s[1010]; // パースする文字列が入っている

enum Type {EXPR, TERM, FACT};
int parse(Type t, int &i) {
  int p;
  if (t == EXPR) {
    p = parse(TERM, i);
    while(s[i]=='+' || s[i]=='-') {
      if (s[i++] == '+') p += term(i);
      else p -= term(i);
    }
  } else if (t == TERM) {
    p = fact(i);
    while(s[i]=='*') {
      i++;
      p *= fact(i);
    }
  } else if (t == FACT) {
    if (s[i]=='(') {
      i++;
      p = exp(i);
      assert(s[i++]==')');
    } else { 
      p = 0;
      while(isdigit(s[i])) {
        p *= 10;
        p += s[i]-'0';
        i++;
      }
    }
  }
  return p;
}

スタックを用いて非再帰にする。
スタックの中身としては、今処理するべきなのはどの関数（expr,term,fact）のどの部分かという情報がまず必要。
さらに、２項演算を実行するために左オペランドが何であったかという情報や、exprにおいて今処理しているのは+なのか-なのかという情報も必要。
ちなみにAOJで見かけたfura2さんのコードを大いに参考にしています。

enum Type {EXPR1, EXPR2, EXPR3, TERM1, TERM2, TERM3, FACT1, FACT2};
struct state {
  Type t;
  int v;
  bool f;  // EXPR3用（+か-か）
  state(Type t) : t(t) {}
  state(Type t, int v) : t(t),v(v) {}
  state(Type t, int v, bool f) : t(t),v(v),f(f) {}
};

int parse(const string &s) {
  int i = 0;
  int now = 0;                  // 直近に処理した”関数”の返り値
  stack<state> S;
  S.push(EXPR1);
  while(!S.empty()) {
    Type t = S.top().t;
    int v = S.top().v;
    bool f = S.top().f;
    S.pop();
    if (t == EXPR1) {
      // TERM1を処理　→　EXPR2を処理というイメージ
      S.push(state(EXPR2));
      S.push(state(TERM1));
    } else if (t == EXPR2) {
      // nowにTERM1の結果が入っている
      if (s[i] == '+' || s[i] == '-') {
        S.push(state(EXPR3,now,s[i]=='+'));
        S.push(state(TERM1));
        i++;
      }
    } else if (t == EXPR3) {
      // nowにTERM1の結果（右オペランド）が入っている
      // vに左オペランドが入っている
      if (f) now = v+now;
      else now = v-now;
      if (s[i] == '+' || s[i] == '-') {
        i++;
        S.push(state(EXPR3,now,s[i]=='+'));
        S.push(state(TERM1));        
      }
    } else if (t == TERM1) {
      S.push(state(TERM2));
      S.push(state(FACT1));
    } else if (t == TERM2) {
      if (s[i] == '*') {
        i++;
        S.push(state(TERM3,now));
        S.push(state(FACT1));
      }
    } else if (t == TERM3) {
      now = v * now;
      if (s[i] == '*') {
        i++;
        S.push(state(TERM3,now));
        S.push(state(FACT1));
      }      
    } else if (t == FACT1) {
      if (s[i] == '(') {
        i++;
        S.push(state(FACT2));
        S.push(state(EXPR1));
      } else {
        // number
        now = 0;
        while(isdigit(s[i])) {
          now *= 10;
          now += s[i]-'0';
          i++;
        }
      }
    } else if (t == FACT2) {
      // ()の後処理
      assert(s[i++]==')');
    }
  }
  return now;
}

まとめ

  • 末尾再帰にできるならスタックを使わないループ（factorial,gcd）
  • できるだけループに直した結果、再帰呼び出しを１箇所にできるなら、再帰呼び出しの後の処理をするために覚えておくものをスタックに積み込む（ack,hanoi）
  • 再帰呼び出しが複数ヶ所あるなら、上に加えて今からどの再帰呼び出しの処理をするのかという情報を加える（parse）

フィボナッチ数まとめ

AOJ 雑記

フィボナッチ数をまとめてみた。
「AOJ2372 - IkaNumber」の解説も入ってる。

https://www.dropbox.com/s/6nx2f9htpfyvnkv/fibonacci.pdf

競技プログラミングと関係のありそうなフィボナッチ数の話題があったら教えて下さい。

とりあえずProject Eulerまわりを近いうちに追加したい・・・。