パソコン甲子園２０１３本選
プログラミング部門 解説

会津大学
1

問１ テニス問題概要• テニスの得点が図のように遷移する．
• 得点を0-0から始めて、指定された得点に至る経路をすべて列挙せよ．

講評• 組み合わせ・パタンを列挙するプログラミング技法が必要．
2

問１ テニス解法• 再帰によって全ての経路を列挙する．
– ある関数で再びその関数を呼び出すプログラミング技法• ジョー君、ヤエさんそれぞれへの加点で分岐．
• 適切に再帰を打ち切る必要がある． score(ジョー君に加点)・・・score(ジョー君に加点)score(ヤエさんに加点)score(ジョー君に加点)score(ヤエさんに加点)・・・
score(ヤエさんに加点)3

問１ テニス
C++による解答例
void score(int j, int y, string p){
if ( j == J && y == Y ){cout << p << endl; return;}
if ( j == 5 && y <= 3 || y == 5 && j <= 3) return;if ( j > J || y > Y ) return;score(j+1, y, p + "A");score(j, y+1, p + "B");}main(){cin >> J >> Y;
score(0, 0, "");}
4問２ 親方の給料計算
問題概要• 職人の種類と工事の種類が与えられる．
• 工事の単価がいくつか与えられる．
• 次の計算（親方が書いたプログラム）で職人の給料を求める．
int i, j;for ( i = 0; i < N; i++ ){c[i] = 0;
for ( j = 0; j < M; j++ ){c[i] = c[i] + a[i][j]*b[j];}}• 職人の人数N≦10000、工事の種類の数M≦10000．
• ただし、職人が工事をこなした総数は50000以下．
5

問２ 親方の給料計算
講評• 入力値の最大ケースを考慮すると、親方が書いたプログラム
では効率が悪い．
• 無駄を無くしプログラムを高速化する必要がある．
• 適切なデータ構造とアルゴリズムに変更できるかが問われている．

6

問２ 親方の給料計算
解法• k番目に現れたデータを e[k], i[k], j[k]として１次元配列に格納．
• （e[k]は2次元配列a[i][j]の代わり）
a[i][j]123456e[k] i[k] j[k]781729342510727933258

1666721679687

問２ 親方の給料計算
解法• 親方のプログラム中の a[i][j]は、表のすべての要素を持つ．

• 値のある要素だけを持つように変更する．

– 最悪10000×10000回の計算– 題意より最大５万回の計算
eiの合計が５万ei≧1で整数
つまり1≦i≦50000

for ( i = 0; i < N; i++ ){c[i] = 0;
for ( j = 0; j < M; j++ ){c[i] = c[i] + a[i][j]*b[j];}}N * M = 100,000,000

for(k = 0; k < K; k++ ){c[i[k]] += e[k] * b[j[k]]}K = 50,0008問３ 塵劫記問題概要• m(2≦m≦20)を基数、n(1≦n＜240)を指数とした mn を日本の数の単位で表す．
• 最大1072(無量大数)．

講評• int(最大21億程度),long long(最大922京)等では表現できない．
• doubleは10308程度だが、有効桁数が15～16程度しかない．
• 多倍長整数の乗算を実装できるかが問われている．

9

問３ 塵劫記
解法• 単位は１７種類＋10000未満．
→ 要素が１８個のint配列でブロック分けする．
無量大数 不可思議

那由他

阿僧祇

恒河沙極載

正澗溝穣

𥝱

垓

京

兆

億万9999～0 9999～0 9999～0 9999～0 9999～0 9999～0 9999～0 9999～0 9999～0 9999～0 9999～0 9999～0 9999～0 9999～0 9999～0 9999～0 9999～0

1. 10000未満の数値を基数mで初期化．
2. 全ブロックにmを掛ける．
3. 各ブロックで10000以上になったものは一つ上のブロックに繰り上げる．
4. 手順2,3をn-1回繰り返す．
10

問３ 塵劫記解法• 例： m = 5 のとき n = 11 から n = 12 へ
億万1万未満048828125

億万1万未満02441040625

億万1万未満024414625

億万1万未満24414

625
11問３ 塵劫記
Javaによる解答例
Stirng[] table = {"", "Man", "Oku", "Cho", "Kei", "Gai", "Jo","Jou", "Ko", "Kan", "Sei", "Sai", "Gok","Ggs", "Asg", "Nyt", "Fks", "Mts"};//18種類
ArrayList<Integer> aBlock = new ArrayList<Integer>();BigInteger val = BigInteger.valueOf(m).pow(n); //m^n
BigInteger tts = BigInteger.valueOf(10000);//ブロック区切り

while (val != BigInteger.ZERO) {aBlock.add(val.mod(tts).intValue());
val = val.divide(tts);}
for (int i=aBlock.size()-1; i>=0; --i) {if (aBlock.get(i) != 0)
System.out.print(aBlock.get(i) + table[i]);}System.out.print("¥n");12

問３ 塵劫記
C++による解答例
const char* table[] = {"", "Man", "Oku", "Cho", "Kei", "Gai", "Jo","Jou", "Ko", "Kan", "Sei", "Sai", "Gok", "Ggs","Asg", "Nyt", "Fks", "Mts"};//18種類
int block[18]; //←すべて0に初期化
block[0] = m;for (int i=1; i<n; ++i) {for (int j=0; j<18; ++j) block[j] *= m; //全ブロックにmを掛ける
for (int j=0; j<18; ++j) {//繰り上がり処理
if (block[j] >= 10000) {int nCarry = block[j]/10000;//繰り上がり分
block[j+1] += nCarry;block[j] -= nCarry*10000;}}}//出力
for (int i=17; i>=0; --i)if (block[i]) printf("%d%s", block[i], table[i]);printf("¥n");13

問４ 巨樹の刻み手問題概要••••

耐久力 D の巨樹を N 種類の道具を使ってたたく.
道具 i でたたくと、巨樹の耐久力が ai 減り ei の経験値を得る.
ただし、道具 i を使用するには ri の経験値が必要.
D を 0 にするたたく回数の最小値を求めよ.

解法１• （巨樹の耐久力、現在の経験値）を頂点とした幅優先探索.

解法２• （巨樹の耐久力、現在の経験値）を状態とした動的計画法.
14

問４ 巨樹の刻み手
解法１，２• （巨樹の耐久力、現在の経験値）を頂点（状態）とする.
• 現在の経験値で使用できる道具を使って、頂点を移動.
経験値
1234

56789…

0
12

耐久力

34:

D

dp[ne][nd] = min( dp[ne][nd], dp[e][d] + 1);

15

問４ 巨樹の刻み手
C++による解答例 （幅優先探索）
queue<pair<int, int> > Q;
C[0][0] = 0;
Q.push(make_pair(0, 0));while(!Q.empty()){
u = Q.front(); Q.pop();if ( u.first >= D ) return C[u.first][u.second];for ( int i = 0; i < N; i++ ){if ( I[i].r > u.second ) continue;
int nd = min(u.first + I[i].a, D);
int ne = min(u.second + I[i].e, MAX);
if ( C[nd][ne] == INF ){C[nd][ne] = C[u.first][u.second] + 1;
Q.push(make_pair(nd, ne));}}}
16

問４ 巨樹の刻み手
C++による解答例 （動的計画法）
dp[0][0] = 0;
for ( int d = 0; d <= D; d++ ){for ( int e = 0; e <= MAX; e++ ){for ( int k = 0; k < N; k++ ){if ( dp[e][d] == INFTY ) continue;
if ( I[k].r > e ) continue;
int ne = min(e + I[k].e, MAX);
int nd = min(d + I[k].a, D);
dp[ne][nd] = min(dp[ne][nd], dp[e][d] + 1);
}
}
}

17

問５ 無限急行
問題概要• 2𝑛 の倍数の番号の駅に停車する n 級快速がある．
• s から d へ移動するための最小の時間を求めよ．

-16 -15 -14 -13 -12 -11 -10 -9-8-7-6-5-4-3-2-1

012345678

910 11 12 13 14 15 1618

問５ 無限急行
問題概要• 2𝑛 の倍数の番号の駅に停車する n 級快速がある．
• s から d へ移動するための最小の時間を求めよ．

-16 -15 -14 -13 -12 -11 -10 -9-8-7-6-5

例：-4-3-2-10

1-8 → 72345678910 11 12 13 14 15 164ステップ
19

問５ 無限急行
解法１: 貪欲法によるアプローチ• 「目的地を通り過ぎないような最も高い級の電車に乗って１停車駅分進む」という戦略をひたすら繰り返す．

20

問５ 無限急行
解法１:証明の概略（１）• 「最初の移動が『目的地を通り過ぎないような最も遠くへの移動』であるような最短経路が少なくとも一つ存在する」ことを示せればよい．
S

1歩X?歩D そうでない最短経路を仮定し、矛盾を導く (背理法)．

21

問５ 無限急行
解法１:証明の概略（２）•Xで停車しないような経路を考る．

SYX

ZD

• このような経路はありえない．
• ある駅の “ランク” を、その駅に止まる最も級が高い急行の級数 とする– 補題: 駅 a, b, c が順番に並んでいて、 Rank(a) < Rank(b) > Rank(c) ならば、駅 aから c までは一度に行けない．
– 補題: 現在地から駅 X の間に、X よりも高いランクの駅は存在しない．

• 他に考慮すべき経路パターンはいろいろあるが、適切に場合分けして証明する．(ここでは最も複雑なケースについて解説)22

問５ 無限急行
C++による解答例
int solve(int s, int d){for ( int cnt = 0, cur = s ;;){
if ( cur == d ) return cnt;
int p = 1;
for ( int k = 1; cur + k <= d; k *= 2 ){if ( cur % k == 0 ){p = k;}}cnt++;
cur += p;}}23

問５ 無限急行
解法２： 無限の性質をうまく利用する• 路線図

0-4-6-7-60-4-5-4-2-3-2

40-10212434656724

問５ 無限急行
解法２： 無限の性質をうまく利用する• 補題: 最初の駅の番号が奇数ならば、最初の移動は必ず 0級快速で隣の駅に進む．
• 補題: 目的の駅の番号が奇数ならば、最後の移動は必ず 0級快速で直前の駅から進むことである．
• 補題: これらを除けば、0 級快速は一切使用しなくてよい．

25

問５ 無限急行
解法２： 無限の性質をうまく利用する• 0 級快速は必要ない．
• 0 級快速しか停まらない、奇数駅も必要ない．
0-4-6-40-20424626

問５ 無限急行
解法２： 無限の性質をうまく利用する• 1 級快速から 3 級快速までの路線図．

0-4-6-40-20424627

問５ 無限急行
解法２： 無限の性質をうまく利用する• 0 級快速から 2 級快速までの路線図．

0-2-3-20-102
123• 全ての駅の番号を 2 で割ると見覚えのある問題が現れる．
• 再帰的に解くことが可能．
28

問５ 無限急行
Cによる解答例/*** src から dst までの最短距離を求める*/
int solve(int src, int dst) {if (src == dst) return 0;
int answer = 0;
if (src % 2 != 0) { answer++; src++; }if (dst % 2 != 0) { answer++; dst--; }answer += solve(src / 2, dst / 2);
return answer;}※ src % 2 == 1 と書いてはいけない！ (-3) % 2 は -1 になる29

問６：微生物発電問題概要• M 匹の雄の微生物と W 匹の雌の微生物がいる．
• bm[i] と bw[i] が合体すると f(bm[i], bw[i])の電気エネルギーが得られる．
• 微生物の団体のエネルギーの最大値を求めよ．

講評

雄雌• 全ての組み合わせを試すと12! = 479,001,600通り→制限時間オーバー．
30

問６：微生物発電
解法• 雄（または雌）の合体の状態をビットで保持．
• 212 通り程度
• 例：Mが３のときは８通り• i 番目までの雌を使って「雄の合体の状態」になったときのエネルギーの最大値を動的計画法で計算．

31

問６：微生物発電
解法
雄の合体の状態
000001010011

100101110111

123

雌

4567

動的計画法で最大値を更新していく32

問６：微生物発電
C++による解答例
dp[0][0] = 0;
for ( int i = 0; i < M; i++ ){for ( int k = 0; k < (1<<W); k++ ){if ( dp[i][k] == -1 ) continue;
dp[i+1][k] = max(dp[i+1][k], dp[i][k]);for ( int j = 0; j < W; j++ ){if ( k & (1<<j) ) continue;
int ni = i+1;
int nj = (k | (1<<j));dp[ni][nj] = max(dp[ni][nj], dp[i][k] + f(bm, bw, i, j));}}}33

問7：古代遺跡の謎
問題概要• あみだくじの部品と、部品の連結を表す式が与えられる．
• 初期状態としてあみだくじの上部に1,2, … N の数が順番に振られている．
• 式の通りにシミュレーションした後の数の並びを表示するプログラムを作成しなさい．
• 部品や部品の列の繰り返しを含– 例： 1000A+9999999(3X+2Y)• 繰り返しの回数はとても多い場合がある．
34

問7：古代遺跡の謎
解法• 与えられた式を構文解析で読み取る．
• 変換の繰り返しは– 繰り返し自乗法、あるいは– 変換を繰り返すと元に戻るので、周期を求め、繰り返す数を周期で剰算．

35

問7：古代遺跡の謎
解法１：繰り返し自乗法• 部品を置換行列に変換．
• 現在の列を行列で表現し、置換行列を乗算することで部品による変換後の列を求める．

• 繰り返し自乗法を使用することで高速に変換後の列を求める．

36

問7：古代遺跡の謎
解法２：周期性を利用• 置換には周期性がある．
• 縦棒の数を表す整数Nの値が小さいため、何回か置換を繰り返すことで周期を求めることができる．
• 繰り返し回数をこの周期で剰算を取ることで小さくすることができる．

37

問８：壁問題概要• W*Hの長方形の領域がある．
• 領域内に水平または垂直な線分がいくつかある．

• 領域内のある２点が与えられるので、２点を端点とし、領域の長方形や線分の交点と交差しない曲線のうち、交差する線分の最小数を答えよ．

38

問８：壁解法• 線分が水平または垂直で、100個しかない．
→座標圧縮して２次元グリッドに落とす．
（最大で約400*400ぐらい）• 線分で囲われた各領域で深さ優先探索（ＤＦＳ）で塗りつぶして区別する．
• 各領域を頂点とし、隣り合った領域同士にコスト1の辺を張ったグラフを作る．
• このグラフで幅優先探索（BFS）を行い最短距離を求める．

39

問9 アルゴリズム検定試験
問題概要• ある試験を運営する最小の費用を求めたい.
• 入力:
–––

受験者の座標.
会場の費用、収容人数の上限、座標.
単位距離あたりのバス運営費用.

• 出力:
–

受験者が受験可能になるための最小の費用.

• 最適化するもの:–––

バスを走らせる距離D .
それぞれの会場について使用するかどうか.
人と会場の割り当て.

問9 アルゴリズム検定試験
解法：問題を分割、会場について考える• 使用する会場を決めると、会場の費用は一定• 会場は最大5個• 小さいので全探索： 25 = 32

問9 アルゴリズム検定試験
解法：割り当てについて考える• バスを走らせないとすると・・・最小費用流•••

受験者が会場に行く費用の合計を最小化.
会場はそれぞれ収容制限がある.
受験者はちょうど一つの会場に行かなければならない.
受験者会場

問9 アルゴリズム検定試験
解法：バスの運営距離ついて考える• 割り当て: Dについて、補助金の傾きが非減少– 重要な制約 ： F(i+2)-F(i+1)≧F(i+1)-F(i)– F(i):= 使用する会場を固定したとき、割り当てのうち移動補助金が最小となる金額• バスの費用: Dについて、傾きが一定

移動補助金

バス費用

合計

問9 アルゴリズム検定試験
解法：Ｄを決定する•

傾きが非減少– 傾きが負になる最大のDを二分法で探す．
• 下に凸– 極値を三分探索で探す．
• 二分法、三分法どちらでも適用可能

移動補助金

バス費用

合計

問9 アルゴリズム検定試験
計算量•使用する会場を決める–•

Dを決め打ちし、二分法する–•log 2 𝐷

最小費用流で最小の割り当て時の解を得る–•2𝑚

𝑁 × 𝑁 + 𝑀 × log 2 (𝑁 × 𝑀)

計算量–

1ケース3000万程度

問題１０ アカ・ベコ捕獲作戦
状況：• 節点(地点)と有向辺(道)のグラフが与えられる• 道は一方通行• ループはありえる(2→4→7→2 →‥)１求めるもの：• アジトから受渡し場所までに必ず通る地点• 受け渡し場所までの間に経由する地点の数が最も少ない地点

アジト

２３４６５７８• 必ず通る地点が受渡し場所しかない場合は受渡し場所
46

直接支配節による解法• 根rをもつ有向グラフの、節点w(=r) の直接支配節 idom(w) とは
 根rからwまでに必ず通る、w以外の節点
 wまでの間に経由する節点の数が最も少ない節点 アジト例）右のグラフの各節点の直接支配節
節点w

１ ２ ３ ４ ５ ６ ７ ８１

２３idom(w) ア ア ア ア ２ ４ ４ ア （アはアジト）• アジトを有向グラフの根としたとき、求めるものは ４
 受渡し場所の直接支配節がアジトでないときは直接支配節７６
 それ以外なら受け渡し場所• 最大サイズは節点N=100,000、辺M=300,000→ O(MN)よりは効率よく直接支配節を求める必要がある。

５８47

ある節点に到達するとき必ず通る地点を求める方法 O(NM)
必ず通る節点 ⇒ そこを封鎖すると到達できない節点 ⇒
封鎖して到達できない節点は封鎖した節点を必ず通る必要がある。
1を封鎖→どの節点にも到達可能。

4を封鎖→アジトから6や7へ到達できない。

アジト

１

２４６７

アジト

３......

１

５４８６

どの節点を受渡し場所にしても、1を通らない経路がある。

２

３５７

８

6か7が受渡し場所のとき、4は必ず通る。

受渡し場所wに到達するときに必ず通る節点が、idom(w)の候補。
候補の中で、そこから受渡し場所wまで他の候補を通らずに到達できるものがidom(w)。

48効率よく解く方法 O(M logN)• 節点wの直接支配節は、アジトを根とする全域木Ｔの、根からwまでの木に沿った経路Ｐw上にある。
• ただし、Ｐwから外れた後にwでＰwに合流する経路があるとき、その経路により迂回されるＰw 上の節点はidom(w)ではない。
（Ｐwから外れた後wで合流する経路がなければ、wのTでの親が idom(w) ）アジト

木Ｔ上の有向辺実線がアジトから４までのＴ上の経路Ｐ4

それ以外の有向辺実線の辺だけ残すと、全域木Ｔが得られる。

１２３アジト１４２４

５

アジトでＰ4から外れて４で合流⇒節点１は idom(4)ではない。
節点４の直接支配節はアジト

６７８49

半支配節
• 各節点wのidom(w)を求めるには、Ｐwから外れた後にwでＰwに合流する経路の始点を求めることが重要。
• そのような節点のうち、（全域木Ｔ上の辺だけを考えたときに）最も根に近いものをwの半支配節sdom(w) と呼ぶ。
（Ｐwから外れてwで合流する経路がなければ、wのTでの親がsdom(w) ）木Ｔ上の有向辺

節点w

アジト

それ以外の有向辺

１ ２ ３ ４ ５ ６ ７ ８sdom(w) ア ア ア ア ２ ４ ４ ７

実線の辺だけ残すと、 １全域木Ｔが得られる。

idom(w)
２ア ア ア ア ２ ４ ４ ア

３実線がアジトから８までのＴ上の経路Ｐ8
アジト
１ ４ ７２５８４５Ｐ8から外れて８で合流する経路の始点は７。

６７８

節点８の半支配節は７50

半支配節から直接支配節を求める方法• 根からsdom(w)の手前までの節点でＰwから外れ、sdom(w)からwまでの間の節点（sdom(w)とw以外）で合流する経路があるときは、sdom(w)はwの直接支配節ではない。
１ ２ ３ ４ ５ ６ ７ ８
実線がアジトから８までのＴ上の経路Ｐ8 節点w
アジト
１ ４ ７
２５８sdom(w) ア ア ア ア ２ ４ ４ ７idom(w)ア ア ア ア ２ ４ ４ ア

アジトでＰ8から外れて２で合流する経路がある。
⇒８の半支配節７を通らずに８に行ける経路がある。

節点８の直接支配節はアジト• 上記のような経路があるとき、その中で始点が最も根に近い経路のＰwとの合流点をuとすると、wの直接支配節はuの直接支配節。
• それ以外のときは、wの直接支配節はwの半支配節。
51

Lengauer-Tarjanのアルゴリズム O(MlogN)• 以上をまとめたものが Lengauer-Tarjanのアルゴリズム。
コンパイラが目的プログラムの最適化を行うときなどに使われる。
1. アジトを始点としてDFSを行い、アジトを根とする全域木Ｔを作る。
2. 根以外の全節点について半支配節を求める。
経路圧縮を行うと、O(MlogN) で求まる。
詳細は以下の原典を参照。
3. Ｔの先行順（preorder）で各節点を訪問し、半支配節から直接支配節を求める。
原典： A Fast Algorithm for Finding Dominators in a Flowgraph,
T. Lengauer and R. E.E Tarjan, ACM Transactions on Programming
Languages and Systems, Vol. 1, No. 1, Pages 121-141 (July 1979).
参考図書： 最新コンパイラ構成技法（翔泳社, 2009年） 19.2節
52サンプルコードfor (int i=1; i<=nNode; ++i) semi[i] = 0;n = 0; r = 1;
DFS(r);
label[0] = semi[0] = 0;

for (int i=2; i<=n; ++i) {int w = vertex[i];if (dom[w] != vertex[semi[w]])dom[w] = dom[dom[w]];}dom[r] = 0;

for (int i=n; i>=2; --i) {int w = vertex[i];ITER(v,pred[w]) {int u = EVAL(*v);
DFS: 節点にDFS順に番号を付ける
if (semi[u] < semi[w]) semi[w] = semi[u]; EVAL: 半支配節を求める手順(原典参照)}
LINK: 第2引数の先祖を第1引数にする
bucket[vertex[semi[w]]].push(w);
LINK(parent[w], w);
while (!bucket[parent[w]].empty()) {dom[i] が1: i番目の地点の答えはそれ自身
int v = bucket[parent[w]].front();
dom[i]が1以外: dom[i]の値が答え
bucket[parent[w]].pop();
int u = EVAL(v);dom[v] = (semi[u] < semi[v]) ? u : parent[w];}}53