ICPC ひとり地区大会 NEERC 2013

ひとりで地区大会練習をした。（LiveArchiveで）

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

問題PDF: http://neerc.ifmo.ru/information/problems.pdf

注意1: 最後の方になって気づいたけど LiveArchive は I 問題のジャッジに対応していない。

注意2: 問題PDFの方では1ファイル1ケースだが、LiveArchive では複数ケースになっている。

注意3: K 問題は本来は 2 行目に整数列を空白区切りで出力で、順番を問わない Special Judge であるが、LiveArchive では普通の diff ジャッジになっており、昇順に出力＆改行区切りでなければらなない。

以上の理由から LiveArchive でやるのはオススメしません。（特に K がひどすぎて、意味不明だったのでこれで 1 時間も潰した）

というか普通に難易度のバランスがあまり良くなかった気がする……。

AC	Penalty	A	B	C	D	E	F	G	H	I	J	K
7	1043	87+0	107+1	-	-	-	25+0	-	143+0	288+0	48+2	225+3

（"-" は提出なし、"+n" は n 回誤答を提出、"m+n" は n 回誤答を提出した後に m 分の提出で AC）

本番順位表だと 11 位だった。

LiveArchive のクソジャッジのせいで K で1時間弱無駄にさせられてキレそう。あと1時間あってももう1問解けたとはあまり思えないけど。

それと、I は最後に頑張って書いていて、いざ提出しようと思ったら未対応だったので公式からデータとチェック用プログラムを落としてきて手動ジャッジしました（使い方が難しくてジャッジ終了時にはとっくに5時間は終わっていたけど、書き終えた時間に提出した扱いにしている）。これで WA とかだったら LiveArchive を恨む種がまたひとつ増えるところだった。

問題概要（感想は下）

A

面倒そうなジグソーパズルを解く。

B

チケットが抽選で販売される。買いたい人は、先に支払い方法を決める。

支払い方法は ICPC カードを使うか、それ以外かの 2 種類ある。

抽選方法は、「ICPC カードを使う人の重み 2、それ以外の人の重み 1 として、まだ当選していない人をランダムに選んで当選させる」という操作を n 回繰り返す。

いま、自分を除いて、ICPC カードを使う人が a 人と、それ以外の人が b 人いる。

自分が ICPC カードで支払う場合とそうでない場合の両方について、当選する確率を求めよ。

n ≦ 3000 ぐらいで a, b はでかい。

C

どの辺も高々 1 つの単純なサイクルに含まれるようなグラフ G = (V, E) が与えられる。

全単射 f: V → V であって、任意の u, v に対して {u, v} ∈ E ならば {f(u), f(v)} ∈ E が成り立つようなものの個数を求めよ。

ただし個数はとても大きくなるので、素因数分解した形で出力すること。

頂点数は 5 万ぐらい。5 万個ぐらいの辺素なパスが与えられ、それによってグラフの辺が示される。各辺素なパスは高々 1000 頂点からなる。

D

文字列集合 S が与えられる。

辺に文字のついた根付き木であって、S に属するすべての文字列が「ある頂点から葉の方向に向かって降りていくパス（葉まで辿り着く必要はない）」に現れるようなもののうち、頂点数が最小のものを求めよ。

頂点数の最小値だけではなく、実際の根付き木を出力する。

文字列の個数 ≦ 50 で、各文字列の長さは 10 以下。

E

凸 n 角形が与えられる。

辺が x, y 軸に平行な長方形で、与えられた多角形の中に収まるようなもののうち、面積最大のものを求めよ。

面積の最大値だけではなく、実際の長方形の座標を出力する。

n ≦ 10⁵ で、座標はでかい。

F

やるだけ。

G

説明するのが面倒……（PDFの図を見るとすぐにわかる）

H

n 要素の整数列 A が与えられる。

A の連続する部分列のうち、その総 XOR と総 AND が等しいものは何通りあるか。

n ≦ 10⁵ で、A[i] は 31 ビット。

I

リアクティブ問。

時刻 0 で座標 x0 にいて、速度 q で等速直線運動する点がある。

0 ≦ x0 ≦ p と 0 ≦ q ≦ v であることはわかっているが、x0, q の値は分からない。

質問 check(L, R) をすると、現在の時刻で点が [L, R] の範囲にあるかどうかが Yes/No で返され、時刻が 1 進む。

ある時刻での点の座標を特定できたらそれを答えて終了。

p, v は 10⁵ 以下で、質問は 100 回までやっていい。

J

twitter のログみたいなのから最長の会話（メンション列）を求める。

K

変なゲームの最後の1手のうち必ず勝てるものを選ぶ。（説明が面倒）

感想など

A

面倒なだけ。

B

簡単な DP。

C

無理だと思う。

D

これも手に負えなさそう。

E

あんまり綺麗に解ける気がしないなあ……。

横幅を決めたら縦幅は 3 分探索できそうだけど、横幅も 3 分探索できるのかなあ。

F

やるだけ。

G

普通に難しそうだけど、上位チームは解いていた。

H

総 XOR の方は部分和をとっておく。

始点を決めれば範囲の AND は 32 通りぐらいしか値をとらない。

始点と総 AND が固定されていると、XOR の部分和から特定の値のものを探すだけになる。

I

Yes/No で返ってくるから 1 回の質問で 1 ビット得られて、p, v は合わせても 34 ビットぐらいしかない。

100 回も質問できるから適当な二分探索みたいなのでいけそう、と思って書いたらジャッジに対応してなくてびっくりした。

WA ったら二分探索をサボらずもっとちゃんと二分にしようと考えていたけど、手動ジャッジのせいで5時間が終わってしまい、これで WA だったらどうしようとヒヤヒヤしていた。

J

やるだけ。

K

ちょっと考えるだけ。LiveArchive ふざけんな。