UTPC 2011

A - プログラミングコンテスト

Time Limit: 1 sec / Memory Limit: 292 MB

時は 20XX 年，世界は G○○gle 社の支配によるディストピアである．現在，人々の娯楽はプログラミングコンテストに限られている．例えば，週末に家族で T○pC○der アリーナを訪れるというのはとてもよく見られる光景である．しかし，それは光の世界のプログラミングコンテストの姿に過ぎない．一方で，G○○gle と反抗勢力がぶつかり合う闇の世界では，命をかけたプログラミングコンテストが行われている．

自分も久しぶりにプログラミングコンテストに参加してみよう．足慣らしに，まずは，プログラミングコンテストの結果を処理するプログラムでも書いてみることにしよう．

問題

M 人の参加者が居て N 問の問題から成るプログラミングコンテストを考える．各参加者に関して，各問題を解いているか解いていないかが与えられるので，最も多く問題を解いている人が解いた問題数を出力するプログラムを作成せよ．

入力

入力の最初の行は 2 つの整数 M, N を含む．これは，参加者数と問題数を表す．

続く M 行には，各参加者が各問題を解いているか解いていないかが与えられる．これらの行のうちの i 行目は N 個の 0 か 1 の数字a_i, 1, a_i, 2, …, a_i, N が書かれている．a_i, j は以下のような意味を持つ．

a_i, j が 0 の時，参加者 i は問題 j を解いていない．
a_i, j が 1 の時，参加者 i は問題 j を解いている．

出力

最も多く問題を解いている人が解いた問題数を出力せよ．

制約

1 ≤ M ≤ 20
1 ≤ N ≤ 20

入出力例

入出力例 1

入力例 1:

入力例 1 に対する出力例:

参加者 1 は 2 問（問題 1, 3)，参加者 2 は 3 問（問題 1, 2, 3），参加者 3 は 1 問（問題 4）を解いている．最も多く問題をといているのは参加者 2 で，その問題数は 3 であり，3 が正しい出力である．

入出力例 2

入力例 2:

入力例 2 に対する出力例:

全ての参加者が 4 問全てを解いている．最も多く問題を解いている参加者というのは参加者全員であり，その問題数は 4 である．

入出力例 3

入力例 3:

1 1
0

入力例 3 に対する出力例:

Problemsetter: 秋葉拓哉

Source Name

UTPC 2011

B - (iwi)

Time Limit: 1 sec / Memory Limit: 292 MB

20XX 年の今，G○○gle 社の世界的な支配により，人々のコミュニケーションは限られており，例えば，自由に人と情報をやりとりすることは基本的に許されていない．特に，過去にプログラミングコンテストで名を馳せた強豪たちは，危険と判断され，お互いバラバラにされ，密かに注意深く監視されているという．

自分も，そんな一人であった，ような気がする．しかし実は，自分は記憶を失ってしまっているのだ．自分が何と名乗っていたか，それすらも思い出せない． 'i' とか 'w' とか括弧とかを使っていた気がするが，それっぽいものを書きだしてみても，しっくりこない．そういえば，今思い出したことには，左右に線対称だった気がするのだ．

問題

'i', 'w', '(', ')' からなる文字列が与えられた時，一部の文字を他の文字に置き換えて，'i', 'w', '(', ')' からなる左右に線対称な文字列にしたい．文字の追加や削除は許さず，1 文字を別の 1 文字に変える操作のみを行うことにする．少なくとも何文字置き換えなければならないかを出力するプログラムを作成せよ．

ここで用いる左右に線対称の定義は，以下とする．

以下の文字列は左右に線対称．

空文字列

"i"

"w"

文字列 x が左右に線対称のとき，以下の文字列も左右に線対称．

"i" x "i"

"w" x "w"

"(" x ")"

")" x "("

以上のもののみが左右に線対称．

ここで，"i" x "i" とは "i" と x と "i" を連結したものを表す．他のものも同様である．

入力

入力は 'i', 'w', '(', ')' からなる 1 つの文字列である．

出力

置き換えなければならない文字数を表す整数を出力せよ．

制約

入力の文字列の長さは 10 以下である．

入出力例

入出力例 1

入力例 1:

(iwi)

入力例 1 に対する出力例:

入力例 1 では文字列がはじめから左右に線対称である．

入出力例 2

入力例 2:

ii(((((ww

入力例 2 に対する出力例:

入力例 2 では例えば ww((i))ww 等に変更すればよい．

Problemsetter: 秋葉拓哉

Source Name

UTPC 2011

C - [[iwi]]

Time Limit: 1 sec / Memory Limit: 292 MB

そうだ，僕のハンドルネームは (iwi) だ．僕は確かに昔にプログラミングコンテストに参加していた．そして，多くの仲間と楽しい時間を過ごした．

確か，仲間たちは全員，美少女だったような気がする．プログラミングコンテストの世界は，僕のハーレムだったような気がする． G○○gle は，僕のハーレムを奪ったのだ，そうに違いない．昔の仲間の手がかりをつかむためにも，やはりプログラミングコンテストに出なければならない．

G○○gle Code Jam に参加登録することにしよう．今度の ID には，丸括弧以外の括弧も検討に入れてみよう．

問題

'i', 'w', '(', ')', '{', '}', '[', ']' からなる文字列が与えられた時，その部分列をとって，線対称な文字列を作りたい．最大で何文字の文字列を作ることができるかを計算するプログラムを作成せよ．

与えられる文字列は， "iwi" という文字列を一度含み，それ以外の部分には 'i' と 'w' を含まない．より形式的には，与えられる文字列は s "iwi" t （s と "iwi" と t を連結したもの）という形で表すことができ， s と t は '(', ')', '{', '}', '[', ']' からなる文字列である． s や t が 0 文字である可能性もある．

作る文字列は，与えられる文字列の部分列をとって作る．部分列とは，元の文字列からいくつかの文字を取り出し，それらを，元の文字列に含まれる順番で繋げたものである．取り出す文字たちは必ずしも元の文字列で連続していなくても良い．

また，作る文字列も，与えられる文字列と同様に，"iwi" という文字列を一度含み，それ以外の部分には 'i' と 'w' は含まないようにしたい．

ここで用いる左右に線対称の定義は，以下とする．

以下の文字列は左右に線対称．

空文字列

"i"

"w"

文字列 x が左右に線対称のとき，以下の文字列も左右に線対称．

"i" x "i"

"w" x "w"

"(" x ")"

")" x "("

"{" x "}"

"}" x "{"

"[" x "]"

"]" x "["

以上のもののみが左右に線対称．

入力

入力は 'i', 'w', '(', ')', '{', '}', '[', ']' からなり上記の条件を満たす文字列である．

出力

上記の条件を満たし作ることのできる文字列の長さの最大値を出力せよ．

制約

入力の文字列の長さは 15 以下である．

入出力例

入出力例 1

入力例 1:

[[[iwi[[[

入力例 1 に対する出力例:

"iwi" という文字列しか作ることができない．

入出力例 2

入力例 2:

[{)iwi(]}

入力例 2 に対する出力例:

"[)iwi(]" や "{)iwi(}" など 7 文字の文字列を作ることができる．

Problemsetter: 秋葉拓哉

Source Name

UTPC 2011

D - 停止問題

Time Limit: 1 sec / Memory Limit: 292 MB

G○○gle Code Jam は G○○gle 社が年に 1 度開催するコンテストである．優勝者は G○○gle への入社を許される，世界最高峰のコンテストだ．しかし勿論，それ以外の参加者は帰らぬ者となる．

G○○gle Code Jam では自分の好きなプログラミング言語や処理系を使うことができる．僕は Defunge という自らが開発したプログラミング言語で参加することにした．この言語を使えば，計算困難な問題はおろか，判定不能な問題ですら解決できる気がしている．

問題

与えられるプログラムが停止するかを判定するプログラムを作成せよ．与えられるプログラムは，以下で説明するプログラミング言語 Defunge で記述されている．

Defunge のプログラムの命令は 1 文字であり，1 次元の列ではなく 2 次元の格子状に並んでいる．下図は，Defrunge のプログラムの例である:

6>--v.
.^--_@

Defunge の言語仕様は以下のようになっている．

Defunge のプログラムは、左上のマスから右向きで開始する．（左上のマスの命令が最初に実行される．）
命令によって進む向きが上下左右に変更されることがある．
端に達したら反対側の端へジャンプする．
メモリは 0 から 15 までの 1 つの整数を記憶することができる．
メモリにははじめ 0 が記憶されている．

Defunge の命令は以下の通りである．

'<' … 実行の向きを左にする．
'>' … 実行の向きを右にする．
'^' … 実行の向きを上にする．
'v' … 実行の向きを下にする．
'_' … メモリの値が 0 ならば実行の向きを右に，そうでなければ左にする．
'|' … メモリの値が 0 ならば実行の向きを下に，そうでなければ上にする．
'?' … 実行の向きが上下左右のいずれかにランダムに等確率で変更される．
'.' … 何もしない．
'@' … プログラムの実行を停止する．
'0' - '9' … メモリの値を指定の数値にする．
'+' … メモリの値に 1 を加える，ただし値が 15 だった場合 0 にする．
'-' … メモリの値から 1 を引く，ただし値が 0 だった場合 15 にする．

入力

入力の最初の行は 2 つの整数 R, C を含む．

続く R 行はプログラムを表す。それぞれ C 文字の文字列を含む。

出力

プログラムが停止する可能性がある場合は YES と出力せよ．

そうでないとき，NO と出力せよ．

制約

1 ≤ R ≤ 20
1 ≤ C ≤ 20

入出力例

入出力例 1

入力例 1:

2 6
6>--v.
.^--_@

入力例 1 に対する出力:

YES

入出力例 2

入力例 2:

2 6
5>--v.
.^--_@

入力例 2 に対する出力:

NO

入出力例 3

入力例 3:

2 6
.>--v.
.^--?@

入力例 3 に対する出力:

YES

補足

Defunge は Befunge と類似している． Befunge の理解は Defunge の理解を助けるかもしれないが，異なる点も多いため，注意せよ．

http://ja.wikipedia.org/wiki/Befunge

Problemsetter: 秋葉拓哉

Source Name

UTPC 2011

E - ファーストアクセプタンス

Time Limit: 1 sec / Memory Limit: 292 MB

プログラミングコンテストでは，各問題に関して，その問題を最初に正解した人の名前や正解時間が，ファーストアクセプタンス（最初の正解）として解説等でしばしば言及される．

久しぶりにプログラミングコンテストに参加するとはいえ，予選で落ちるとは到底思えない．ならば，最初のうちは，多少高いスコアを取ることを目指すよりも，ファーストアクセプタンスを多く獲得し，存在をアピールしたほうが良いのではないか．

自分の実力を持ってすれば，各問題を見た瞬間に，その問題を自分が何分で解くことができるかと，その問題が開始後何分で自分以外の参加者によって最初に解かれるかがわかる．

これらの情報を用いて，どの程度ファーストアクセプタンスを獲得できるかを計算するプログラムを作っておこう．

問題

N 問の問題から成るプログラミングコンテストを考える．問題 i を自分が解くには A_i 秒の時間がかかり，また，問題 i は開始後 B_i 秒で自分以外の参加者によって最初に解かれるとする．

自分が問題を解く順番は自由に決められるが， 1 つの問題を解き始めたら，解き終えるまでその問題をやるものとする．問題を解き終え次の問題に取りかかる際などの，問題を解いている時間以外の時間は十分小さいと考え，無視して考えることにする．また，全ての問題は終了までに 1 人以上の自分以外の参加者によって解かれるものと考える．

自分以外の参加者によって最初に解かれるよりも早く，あるいは同時に問題 i を自分が解きおえた時，問題 i のファーストアクセプタンスを獲得できる．すなわち，問題 i を自分が開始後 t_i 秒に解き終えたとしたとき， t_i ≤ B_i であれば，問題 i のファーストアクセプタンスを獲得できる．

最大で何個の問題に関してファーストアクセプタンスが獲得できるかを計算するプログラムを作成せよ．

入力

入力の最初の行は 1 つの整数 N を含む．

続く N 行には，各問題に関する情報が与えられる．これらの行のうちの i 行目には 2 個の数字 A_i, B_i が書かれている．

出力

最大で獲得することのできるファーストアクセプタンスの数を出力せよ．

制約

1 ≤ N ≤ 1000
1 ≤ A_i ≤ 10⁶ (1 ≤ i ≤ N)
1 ≤ B_i ≤ 10⁶ (1 ≤ i ≤ N)

部分点

この問題の判定には，20 点分のテストケースのグループが設定されている．このグループに含まれるテストケースの入力は以下を満たす．

1 ≤ N ≤ 16

入出力例

入出力例 1

入力例 1:

入力例 1 に対する出力例:

入出力例 2

入力例 2:

入力例 2 に対する出力例:

Problemsetter: 秋葉拓哉

Source Name

F - 全域木

Time Limit: 1 sec / Memory Limit: 292 MB

この問題は正しく採点されていないという報告を受けています。

今，G○○gle Code Jam の地区大会が始まろうとしている．左の席に座っている男の ID は wata と言うらしい．東京大学時代の記憶に，似たような ID の仲間が居た覚えがある．しかし，僕の仲間は一人残さず美少女だったはずだ．

僕の記憶の中の wata は，マトロイドが好きだった．特に，マトロイド交差が大好きで，様々なマトロイド達を交差させることに一種の興奮すら覚えると言う少し変わった奴だった．

マトロイドの理論の力を使えば，与えられたグラフ上で辺を共有しない複数の全域木を求めることはとても簡単な問題だと言っていた気がする．しかし，特別なグラフに関しては，マトロイドのアルゴリズムを直接に適用するよりも高速なアルゴリズムがあるのではないか？

問題

N 個の頂点からなる完全グラフにおいて，辺を共有しない全域木を K 個作成せよ．

完全グラフとは，全ての相異なる 2 頂点間に 1 本の辺を持つグラフである．下図は，4 頂点の完全グラフの例である．

4 頂点の完全グラフ．

全域木とは，元のグラフの全ての頂点と一部の辺からなる木のことである．木とは，連結かつ閉路を持たないグラフのことである．下図は，4 頂点の完全グラフにおける，辺を共有しない 2 つの全域木である．

4 頂点の完全グラフの全域木の例．

4 頂点の完全グラフの全域木であり，前の例と辺を共有しないもの．

入力

入力は 1 行からなり， 2 つの整数 N, K が書かれている．

出力

条件を満たす K 個の全域木を作ることができない時，-1 とだけ出力せよ．

条件を満たす K 個の全域木を作ることができる時， K 個の全域木を改行で区切り出力せよ． 1 つの全域木は N - 1 行で表される．その i 行目には，その全域木の辺 i が結ぶ 2 つの頂点を表す 2 つの整数をスペースで区切り出力する．ここで，頂点は 1 から N までの整数で表すものとする．

制約

2 ≤ N ≤ 10000
1 ≤ K ≤ 100

部分点

この問題の判定には，20 点分のテストケースのグループが設定されている．このグループに含まれるテストケースの入力は以下を満たす．

1 ≤ N ≤ 8

入出力例

入出力例 1

入力例 1:

4 2

入力例 1 に対する出力の例:

この入出力例は問題文中の図と対応している．

入出力例 2

入力例 2:

4 3

入力例 2 に対する出力の例:

-1

Problemsetter: 秋葉拓哉

Source Name

G - プログラミングコンテストチャレンジブック

Time Limit: 1 sec / Memory Limit: 292 MB

今，G○○gle Code Jam の地区大会が始まろうとしている．前の席に座っている男の ID は omeometo と言うらしい．後ろの席に座っている男の ID は jellies と言うらしい．東京大学時代の記憶に，似たような ID の仲間が居た覚えがあるが，僕の仲間は一人残さず美少女だったはずだ．

彼らは，机の上に蟻のイラストが掛かれた本を持っている．あれはもしや…プログラミングコンテストのアルゴリズムを最初に網羅し，今では発売禁止となった伝説の本，「プログラミングコンテストチャレンジブック」ではないか？僕は，omeometo がトイレに行ったのを見計らい，少し拝借して，読んでみることにした．

https://img.atcoder.jp/utpc2011/triangle_fig_pcbook.jpg

プログラミングコンテストチャレンジブック

…しかし，僕は一瞬で本を読み終えてしまった．拍子抜けだ．簡単すぎる．少し古い本だからといって，こんな内容でよく売る気になったものだ．

例えば，最初の三角形の問題．これは，簡単すぎてお話にならない．自分だったら，こうする．

問題

N 本の直線状の棒がある．棒 i の長さは a_i である．あなたは，それらの棒から 6 本を選び，それらの 3 本ずつで，2 個の三角形を作ろうと考えている． 3 本の棒はそれぞれ三角形の辺として用い，2 つの棒が触れる位置は棒の端点のみとする．つまり，棒の一部を三角形の辺として使うことは許されず，必ず棒全体を辺としなければならない．また，棒の太さは考えず，三角形は正の面積を持たなければならないものとする．

2 個の三角形の周長の和の最大値を求めよ．ただし，2 個の三角形を作ることができない際には 0 を答えとせよ．

入力

入力の最初の行には整数 N が書かれている．続く N 行の i 行目には 1 つの整数 a_i が書かれている．

出力

答えの整数を出力せよ．

制約

1 ≤ N ≤ 10⁵
1 ≤ a_i ≤ 10¹⁵

部分点

この問題の判定には，20 点分のテストケースのグループが設定されている．このグループに含まれるテストケースの入力は以下を満たす．

1 ≤ N ≤ 100

入出力例

入力例:

入力例に対する出力:

Problemsetter: 秋葉拓哉

Source Name

H - キャッシュ戦略

Time Limit: 2 sec / Memory Limit: 292 MB

今，G○○gle Code Jam の地区大会が始まろうとしている．斜め右前の席に座っている男の ID は lyrically と言うらしい．東京大学時代の記憶に，似たような ID の仲間が居た覚えがあるが，僕の仲間は一人残さず美少女だったはずだ．

僕の記憶の中の lyrically は，アルゴリズムの力や実装の力もさながら，気合で問題に正解することにも定評があった．例えば，計算量が多少悪いプログラムでも，上手な実装をすることで高速にし，正解とするようなことも得意としていた．

プログラムを高速にする上で，非常に大切になってくるのが，キャッシュメモリとの親和性である．

問題

ブロック毎に読み込みのコストが異なるメモリを考える．起こる全てのメモリアクセスがあらかじめ分かった状態での，フルアソシアティブのキャッシュメモリでの最善なキャッシュ戦略を求めたい．以下，平易な言葉で説明する．

M 個の箱と，N 個のボールがある．ボールには 1 から N までの番号が付いており，各ボール i には重さ w_i が決まっている．また，長さ K の数列 a₁, a₂, …, a_K が与えられる．各 a_j は 1 ≤ a_j ≤ N を満たす整数である．

はじめは全ての箱は空である． j = 1, 2, …, K の順に，以下を行いたい．

ボール a_j が入っている箱があれば，何もしない．
- この操作にかかるコストは 0 である．
ボール a_j が入っている箱がなければ，いずれかの箱にボール a_j を入れる．
- ボールを箱に入れる際，もし既にその箱に入っているボールがあれば，そのボールは外に出す．
- この操作にかかるコストは w_{a_j} である．（コストは，入れる箱や取り出すボール等にはよらない．）

コストの和の最小値を計算するプログラムを作成せよ．

入力

入力の最初の行は 3 つの整数 M, N, K を含む．

続く N 行の i 行目には整数 w_i が書かれている．

続く K 行の j 行目には整数 a_j が書かれている．

出力

コストの和の最小値を出力せよ．

制約

1 ≤ M ≤ 10
1 ≤ N ≤ 10⁴
1 ≤ K ≤ 10⁴
1 ≤ w_i ≤ 10⁴
1 ≤ a_j ≤ N

部分点

この問題の判定には，20 点分のテストケースのグループが設定されている．このグループに含まれるテストケースの入力は以下を満たす．

1 ≤ M ≤ 3
1 ≤ N ≤ 10
1 ≤ K ≤ 10³

入出力例

入力例 1

入力例 1:

入力例 1 に対する出力例:

入力例 2

入力例 2:

入力例 2 に対する出力例:

Problemsetter: 秋葉拓哉

Source Name

I - ビット演算

Time Limit: 1 sec / Memory Limit: 292 MB

この問題は正しく採点されていないという報告を受けています。

いよいよ G○○gle Code Jam の世界大会が始まろうとしている．前では P○tr, t○mek, SnapDrag○n をはじめとする， G○○gle の誇る最強のコーダー達が睨みを利かせている．妙な動きを見せれば，命はないだろう．目をつむり，コンテスト開始をじっと待つ．

…妙だ，コンテストが始まらない．目を開けてみると…なんということだ．部屋の全ての人間が，倒れている．いや違う，全てではない．一人の男，wata を除いてだ．

wata: 「やっと話せるぞ．久しぶりだな，(iwi)」
(iwi): 「…お前は何者だ？俺の知る wata は幼なじみ系美少女のはずが…」
wata: 「まだそんな妄想に取り憑かれているのか!! 思い出せ!! 受け止めろ!! 彼はもうこの世界には居ないんだ!!」

はっ…!! 僕は全てを思い出していた．僕は世界で最初にプログラミングコンテストで人を殺めたのだ．そして，僕が殺したのは他でもなく，最も仲の良かった友人の一人，kita_masa であった．

kita_masa は自らをビット演算の達人と言い，あらゆる関数はビット演算で記述できると言う，少し変わった奴だった．そういえば今，ビット演算を用いて作成したい関数があるが， kita_masa にそれをお願いすることはできない．そこで，kita_masa の代わりになるプログラムを作成することにした．

問題

N 個の整数の組 (x_i, y_i) が与えられる．全ての組に対して y_i = f(x_i) なる関数 f を制約の下で作ることを考える．

関数 f は，C 言語のソースコードとして以下のように表現できるものとする:

uint32_t f(uint32_t x) {
  return 式;
}

ここで，uint32_t は 32 ビット符号無し整数を表す．また，式は以下の BNF で表現できるものとする:

<expr> ::= "x"
         | <num>
         | "(~" <expr> ")"
         | "(" <expr> <op2> <expr> ")"
<op2> ::= "&" | "|" | "^" | "+" | "-" | "*"

<num> は 32 ビット符号無し整数で表現できる非負の整数を 10 進数で自然に (leading-zero 等を持たず) 表現したものとする．

このような関数の式を出力するプログラムを作成せよ．

入力

入力の最初の行は 1 つの整数 N を含む．

続く N 行の i 行目は 2 つの整数 x_i, y_i を含む．

出力

条件を満たす式を出力せよ．

制約

1 ≤ N ≤ 8
0 ≤ x_i, y_i < 256
式は必ず，上記の BNF に従う書式で出力せよ．例え C 言語の表現として妥当であったとしても，空白や改行の挿入や括弧の削除などはしてはならない．
出力は 100000 文字を越えてはならない．
条件を満たす関数 f が常に存在するような入力が与えられる．

部分点

この問題の判定には，20 点分のテストケースのグループが設定されている．このグループに含まれるテストケースの入力は以下を満たす．

'+', '-', '*' を用いないような正しい出力が存在する

入出力例

入力例1:

入力例 1 に対する出力の例:

(x&3)

入力例2:

入力例 2 に対する出力の例:

(x&(x-1))

良く知られる最右の 1 ビットをオフにする操作である．

Problemsetter: 秋葉拓哉

Source Name

J - 乱択平衡分二分探索木

Time Limit: 5 sec / Memory Limit: 292 MB

この問題は正しく採点されていないという報告を受けています。

ところで，G○○gle Code Jam の地区大会で右の席に座っていた男の ID は rng_58 と言うらしい．東京大学時代の記憶に，似たような ID の仲間が居た覚えがあるが，僕の仲間は一人残さず美少女だったはずだ．彼女はいわゆる無表情不思議系キャラだったような気がする．

ということは，彼は知らない男だ．rng とは何の略だろう．おそらく Random Number Generator に違いない．乱択アルゴリズムを得意とするのだろう．

ところで，乱数を用いた平衡二分探索木である Treap は， 2011 年頃のプログラミングコンテストではしばしば用いられていたようだが， 20XX 年の今では，あまり使用されていない．

当時 Treap は実装が平易であるという理由により Splay 木や Scapegoat 木と並んでよく使われていた． 20XX 年の今，命をかけたプログラミングコンテストが日常的に行われるこの世界では，実装が多少平易になるというような甘い根拠での選択は到底考えられない．皆，少しでもプログラムが高速になるよう考えているし，世界大会出場者ともなれば，Left-leaning 赤黒木程度なら十数秒で記述できるのが当然だ．

例えば，Treap が赤黒木よりも遅くなってしまうのは，高さの定数倍が効いてくるからであると言われている．ここは，落ち着いてそれを数値的に考察することにより，精神の安定を取り戻そう．

問題

キーを実数とする Treap に N 個のランダムな要素を挿入した際に，高さが h (h = 0, 1, …, N - 1) となる確率を求めよ．以下，より詳しく説明する．

Treap とは乱数を用いた平衡二分探索木である．各ノードは，キーの他に，優先度という値を持つ．ここでは，キーと優先度は 0 から 1 までの実数値とする． Treap では，以下の 2 つの条件が常に保たれる．

キーに関する条件

各ノードに関して，左の子以下のノードは自分より小さなキーを持つ

各ノードに関して，右の子以下のノードは自分より大きなキーを持つ

優先度に関する条件

各ノードに関して，子のノードは自分より小さな優先度を持つ

下図は，Treap の例である．各ノードの，上部にキーが，下部に優先度が書かれている．

//img.atcoder.jp/utpc2011/treap_fig1.png

7 つのノードからなる Treap の例．

挿入の操作は，以下のように行われる．挿入するキーを x とおく．

挿入する新しいノードの優先度 p を 0 から 1 までの一様分布よりランダムに決定する．
通常の二分探索木と同様に，まずは優先度を無視し新しいノードを挿入する．
優先度の条件を満たすように，新しいノードを上に持ち上げるような回転操作を必要なだけ繰り返す．

木の回転操作に関しては，補足の節に詳しく記述したので，参考にせよ．

下図は，先ほどの例にキーとして 0.5，優先度として 0.7 を持つ頂点を挿入した過程の例である．

//img.atcoder.jp/utpc2011/treap_fig2.png

まずは優先度が無視され，ノードが挿入される．

//img.atcoder.jp/utpc2011/treap_fig3.png

回転を行い新しいノードが上へ行く．

//img.atcoder.jp/utpc2011/treap_fig4.png

さらに回転を行うと，優先度の条件が満たされるので，挿入は終了する．

空の Treap に N 個のキーを，やはり 0 から 1 までの一様分布よりランダムに選び挿入してゆくとする．最終的に高さが h となる確率を，各 h = 0, 1, …, N - 1 について求めよ．なお，実数は十分な精度を持って扱われるとし，例えば 2 つのノードの優先度が等しくなる確率は 0 としてよい．また，高さとは，根のノードから各ノードに至るために通らなければならない辺の本数の最大値である．

入力

1 つの整数 N が書かれている．

出力

出力は N 行から成る． i 行目に高さが i - 1 となる確率を出力せよ．値は小数点以下何桁表示しても構わない．

制約

1 ≤ N ≤ 3 × 10⁴
出力する値は 10^- 5 以下の誤差を含んでいても構わない．

入出力例

入力例 1:

入力例 1 に対する出力例:

1.0

入力例 2:

入力例 2 に対する出力例:

0.0000000000
1.0000000000

補足

木の回転操作には，右回転と左回転がある．右回転とは，以下の 2 つの図の 1 つめの状態を 2 つめの状態にする操作であり，左回転とは，以下の 2 つの図の 2 つめの状態を 1 つめの状態にする操作である．

//img.atcoder.jp/utpc2011/treap_fig_rot1.png

右回転をする前，または左回転をした後

//img.atcoder.jp/utpc2011/treap_fig_rot2.png

右回転をした後，または左回転をする前

Treap においては，持ち上げたいノードがその親ノードの左の子であった場合，持ち上げたいノードを上図の P とするような右回転を適用し，持ち上げたいノードがその親ノードの右の子であった場合，持ち上げたいノードを上図の Q とするような左回転を適用する．

木の回転操作について，より詳しくは，例えば以下を参照せよ．

http://ja.wikipedia.org/wiki/%E6%9C%A8%E3%81%AE%E5%9B%9E%E8%BB%A2

Treap について，より詳しくは，例えば以下を参照せよ．

Problemsetter: 秋葉拓哉

Source Name

K - 巡回セールスマン問題

Time Limit: 5 sec / Memory Limit: 292 MB

この問題は正しく採点されていないという報告を受けています。

2011 年のあの頃，まだプログラミングコンテストはとても平和であり，我々はルールを精読せずに気軽にコンテストに参加していた．しかし，そこに G○○gle の陰謀は迫っていた．ある日，G○○gle によって秘密裏に買収されていた T○pC○der のコンテストは，人知れずうちにルールが改変されており，命がけのプログラミングコンテストとなっていた．そして僕は，そこで，何も知らず，まっ先に kita_masa のプログラムのオーバーフローを突いたのだ…．

(iwi): 「うう…ああ…」
wata: 「今やるべきことは自分を攻めることではない．チャンスを無駄にする気か？」

…そういえば，今こいつは，部屋に居る全ての人間を一瞬にして倒していた．どうなっているんだ？

wata: 「まず，知っているかもしれないが， G○○gle は NP 完全問題を含む多くの計算困難と言われてきた問題に対する多項式時間の効率的なアルゴリズムを持っている．P vs NP 問題を解決したが，敢えてそれを秘匿することによってここまで成長したのだ．」
(iwi): 「もしやとは思っていたが，やはりか…．しかし，お前は今，G○○gle の人間を一瞬にして倒した．もしやお前も…？」
wata: 「残念ながら違う．しかし…お前なら，分かるはずだろう？」

…なるほど!! そういうことか．彼は大学時代，指数時間のアルゴリズムを高速にすることに興味を持っていた．例え指数時間であっても，指数の底が極めて小さければ，現実的なインスタンスに対して十分に高速な可能性がある．

wata: 「そういうことだ．例えば，今僕は，巡回セールスマン問題の O^*(1.0001ⁿ) 時間のアルゴリズムを完成させようとしている．」

凄まじい，想像以上だ…．

wata: 「完成させるにあたって，グラフアルゴリズムに詳しいお前の力が必要だ．手を貸してくれるな？」
(iwi): 「ああ，勿論だ．まかせろ!!」

問題

グラフが与えられる．グラフはN 個の頂点を持ち，頂点には 1 から N の番号が付いている．また，グラフは M 個の辺を持ち，辺は有向 (一方通行) で，それぞれ距離が決まっている．

頂点 1 から出発し，頂点 2, 3, …, N をこの順番に訪れ，頂点 1 へ戻る経路を考える．ここで，「この順番に訪れる」というのは，経路に含まれる頂点の部分列に 2, 3, …, N が含まれるということである．つまり，スタート地点の頂点 1 から頂点 2 への移動は，直接の移動であっても，他の頂点を経由した移動であってもよく，次の頂点 2 から頂点 3への移動，さらにその次の頂点 3 から頂点 4への移動等に関しても同様である．同じ頂点や同じ辺を 2 度通っても構わない．

グラフが与えられた時，頂点 1 から出発し頂点 2, 3, …, N をこの順番に訪れ頂点 1 へ戻る経路のうち，最短のものの長さを出力するプログラムを作成せよ．経路の長さとは，経路に含まれる辺の距離の和である．複数回含まれる辺に関しては，含まれる回数の分だけ距離を加えよ．

入力

入力の最初の行は 2 つの整数 N, M を含む．これは，グラフの頂点数と辺数を表す．

続く M 行は，辺の情報を表す．これらの行のうちの i 行目は 3 つの整数 a_i, b_i, c_i が書かれており，辺 i は頂点 a_i から頂点 b_i を結び，その距離は c_i であることを表す．

出力

条件を満たす経路のうち最短のものの長さを出力せよ．ただし，条件を満たす経路が存在しない場合は，-1 を出力せよ．

制約

2 ≤ N ≤ 10⁵
0 ≤ M ≤ N + 500
1 ≤ a_i, b_i ≤ N，a_i ≠ b_i
1 ≤ c_i ≤ 10³

入出力例

入出力例 1

入力例 1:

入力例 1 に対する出力の例:

入出力例 2

入力例 2:

入力例 2 に対する出力の例:

Problemsetter: 秋葉拓哉

Source Name

L - L番目の数字

Time Limit: 3 sec / Memory Limit: 292 MB

反乱を嗅ぎつけた多くの G○○gle のコーダーが我々を取り押さえにやってきた．かなりの数だ．その中には，東京大学時代に僕らを優しく指導してくれた先輩たちも多く見受けられる．残念ながら，今では敵同士だ．

wata: 「予想以上の数だ…」
(iwi): 「ああ，我々が超高速指数時間アルゴリズムを持っているからと言って，それは彼らにようやく並んだに過ぎない．この数では…」
？？: 「心配要らない！君たち，アルゴリズムをこっちに渡すんだ！」

声がした窓の外を見ると，G○○gle の建物に向きあう集団がいた．黒の生地に赤で I，緑で ○，黄色で M と書かれた T シャツ … 彼らは I○M か！？そして奇妙なことに，彼らは，向かってくる G○○gle のコーダー達を，キーボードに触れることなく倒していた．どうなっている？

(iwi): 「…！ついに Wats○n 2 は完成したのか！」
wata: 「どういうことだ？」

2011 年，I○M は彼らの高い技術力を活用し，自然言語で出題されたクイズに高速かつ正確に応答するシステムである Wats○n を完成させ，クイズ番組にてクイズ王と呼ばれてきた人間たちに勝利した．そして 20XX 年の今，Wats○n は，プログラミングコンテストの問題に対し解答のプログラムを作成するシステムとして生まれ変わったのだ．

I○M の登場により，我々を取り囲む人数が減ってゆく．

wata: 「チャンスだ！半分は任せられるか？」
(iwi): 「もちろんだ！」

僕は，妄想と決別したことにより，全てを思い出していた．当然，当時の知識や経験は，今から見ればレベルが低すぎて役に立たない．しかし，一番大切なものを思い出すことができた．それは，プログラミングコンテストを愛する気持ちである．問題を開く瞬間のワクワク感，サンプルが通った瞬間の盛り上がり，ステータスが更新される瞬間の緊張，勝利の瞬間の喜び．

(iwi): 「必ず kita_masa の復讐を果たし，この狂った世界を終わらせる！」

そして，僕は自信の 1 題を繰り出す．これは，東京大学時代の自分が愛した問題「K 番目の数字」を独自のテクニックにより一般化かつ大規模化した問題である．

問題

グラフが与えられる．

N 個の頂点があり，頂点に 1 から N の番号が付いている．
これらの頂点は，N - 1 本の辺によりツリー状に接続されている．
各頂点 v には数字 a_v が定まっている．

下図は，与えられるグラフの例である．各頂点には上部に頂点の番号が，下部にその頂点に定められた数字 (a_v) が書かれている．

与えられるグラフの例

次に，Q 個の以下のようなクエリが与えられる．

各クエリ q には，頂点 v_q, w_q と整数 l_q が指定される．
頂点 v_q から頂点 w_q への経路に含まれる頂点の数字のうち l_q 番目に小さいものを求めよ．
- 経路は単純なもののみを考える．単純な経路とは，同じ頂点を二度通らない経路のことである．グラフがツリー状であることから，単純な経路は一意である．
- 経路には両端点（すなわち頂点 v_q, w_q）を含むものとする．

例えば，上図のグラフが与えられている時， (v_q, w_q, l_q) = (1, 6, 3) なるクエリ q に対する答えは 7 である．これは，頂点 1 から頂点 6 への経路には頂点 1, 3, 4, 6 が含まれており，それらに定まった数字 2, 5, 8, 7 の 3 番目めに小さな数字は 7 であることによる．

グラフとクエリを受け取り，結果を出力するプログラムを作成せよ．

入力

入力の最初の行は 2 つの整数 N, Q を含む．これは，頂点数とクエリの数を表す．

続く N 行は，各頂点の持つ数字を表す．これらの行のうちの v 行目は 1 つの整数 x_v が書かれており，これは頂点 v の持つ数字を表す．

続く N - 1 行は，辺の情報を表す．これらの行のうちの e 行目は 2 つの整数 a_e, b_e が書かれており，これらは辺 e が結ぶ 2 つの頂点を表す．

続く Q 行は，クエリの情報を表す．これらの行のうちの q 行目は 3 つの整数 v_q, w_q, l_q が書かれており，これらはクエリ q の情報を表す．

出力

出力は Q 行からなる．q 行目にクエリ q の答えを出力せよ．

入力に関する制約

1 ≤ N, Q ≤ 10⁵
1 ≤ x_v ≤ 10⁹
1 ≤ a_e, b_e ≤ N
1 ≤ v_q, w_q ≤ N
頂点 v_q から頂点 w_q への経路には l_q 個以上の頂点が存在する．

入出力例

入力例:

入力例に対する出力:

Problemsetter: 秋葉拓哉