ICPC ひとり地区大会 NEERC 2011

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

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

問題PDF: http://neerc.ifmo.ru/past/2011/neerc-2011.pdf

I 問題がインタラクティブで LiveArchive はジャッジに対応していないので、あらかじめ手元ジャッジできるようにしておいた。（しかし普通にミスってて今回も手動ジャッジに手間取ってしまった）

AC Penalty A B C D E F G H I J K L
8 1204 5+0 41+0 167+0 264+1 63+0 - 231+0 - 216+0 - 137+3 -

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

本番順位表だと 11 位だった。9 完は 2 チームで、11 位は 8 完下位というところ。ひとりなのでペナルティで負けるのはしょうがないね。

問題概要（感想は下）

A

グリッド上に / \ で書かれた多角形があるので面積を求める。

B

0 〜 m-1 の整数を 01 列でエンコードする。 m ≦ 2n なる最小の n をとってくる。

エンコード先の 01 列は長さ n-1 か n のどちらかで、

  • 小さい数の方が 01 列が短い（または同じ長さ）
  • 小さい数の方が 01 列が辞書順で小さい

を満たすようにする。エンコード後のビット数を最小にせよ。具体的な 01 列も求めること。

m ≦ 10,000。

C

面倒に面倒を加えて面倒でアレンジした面倒な問題。説明する気が起きない。解法自体は簡単なので……。

D

n 個の文字列 s1, ..., sn が与えられる。以下の文字列を含む辞書を作る。

  • s1, ..., sn
  • si の空でない prefix と sj の空でない suffix を連結したもの（i = j でも良い）

辞書に含まれる文字列は何種類あるか。

n ≦ 105 で各文字列の長さは 40 以下。

E

雌雄の区別があるとある種の個体 1, ..., n がいる。どれが雄でどれが雌かも与えられる。

m 個の情報が時系列順に与えられる。各情報は

  • a, b から性別 s の子が生まれる。（a, b の性別は異なり、生まれた子の番号はまだ使われてない最小の番号）
  • a が死ぬ。

のいずれか。また、「個体 a の DNA 番号は x」という形式の情報が k 個与えられる。

子は雌親の DNA 番号をそのまま受け継ぐとしたとき、m 個の情報が与えられた後で生きている個体について

  • すべての DNA 番号が同じであるか
  • 異なる DNA 番号の個体がいるか
  • 与えられた情報からでは判定できないか

を求める。

n, m, k それぞれ 105 ぐらい。

F

時刻 t = 1, ..., n に点 (p[t], 0) から、(x[t], y[t]) を頂点とするような放物線を描いてミサイルが発射される。

m 個の航空機の情報が与えられる。各情報は、時刻 a から時刻 b の間に x 座標が x1 から x2 の間を飛ぶという形式。

それぞれの航空機について、飛んでいる時間に発射されるようなミサイルの軌道と交わらないためには高度いくつを飛ぶ必要があるかを求めよ。

n, m は 105 ぐらいだったと思う多分。

G

1 以上 n 以下の秘密の整数がある。

1回のクエリでは 1 以上 n 以下の整数 x を指定して、秘密の整数と x の最大公約数を知ることができる。

秘密の整数を特定するために最悪ケースで必要なクエリの回数を求めよ。

n は 104 以下。

H

2 点 p1, p2 と 2 直線 l1, l2 が与えられる。

直線 l であって、p1 を l に関して対称移動すると l1 上に動き、p2 を l に関して対称移動すると l2 上に動くようなものがあれば求めよ。

I

リアクティブ問。

n 要素の秘密の順列がある。

1 回のクエリでは n 要素の順列を指定して、秘密の順列との最大共通部分列の長さを知ることができる。

5n2 回以内のクエリで秘密の順列を特定せよ。

J

前進命令、右回転命令、左回転命令と関数定義、関数呼び出しからなるプログラムに従って動くロボットがいる。

ロボットが停止するまでの間に通った座標のうち |x| + |y| の最大値を求めよ。いくらでも大きくなる場合は Infinity と出力。

関数定義は 100 個以下。各関数の命令数は 100 以下。

K

n 頂点の木が与えられる。辺をいくつか追加して、以下の条件を満たすようにしたい。

  • 条件: どの辺を取り除いてもグラフが連結である。

最低いくつの辺を足す必要があるか？また、足す辺の具体例をひとつ出力せよ。

n は 105 以下。

L

読む気起きず。

感想など

A

良い A 問題。

B

n-1 ビットの列の個数を決めると可能かどうかすぐにわかる。

C

面倒。

D

trie を 2 個作って頑張る。（頑張るというほどでもない）

E

Union Find

F

頑張ってデータ構造する問題に見える。

ちゃんと考えてないけど解けない問題ではなさそう？（ただ時間はかかりそう）

G

クエリは結局素因数について尋ねている。

ある素因数を持ってるかどうかを聞いて、Yes と答えられた場合と No と答えられた場合、どちらがより悪いかを考えてみると、残りの素因数については No と答えられた場合の方が自由度が高いことがわかる。

よって秘密の整数が 1 のときが最悪ケースで、このときは n 以下のすべての素数について質問しなければならない。

しかし問題文にもある通り、n = 6 のとき 2, 3 はまとめて質問できるので、「n 以下の素数を、積が n 以下のグループに分ける。最小で何グループ必要か」を解けばよい。

でかい素数から順に考えていくと、小さい素数と貪欲にマッチさせていけばよいことがわかる。

H

定数入力の幾何は大変そう（先入観）

I

適当な順列の中で 1 の場所を動かしていくと、クエリの答えはなにか m と m - 1 になる。

このとき、返答が m になった時には最長共通部分列が 1 を含むことが言える（1 の場所を先頭から試していってクエリの返答が変わるとき何が起こっているか考えるとわかる）。

最長共通部分列が 1 を含んでいる状態で、2 を動かす。目標は、1 と 2 の位置関係を正しくして、「最長共通部分列が 1 と 2 を含んでいる」状態にすること。

ここで 2 通りの場合があって、まず 2 がはじめから最長共通部分列に入っている場合。この場合 2 を動かすと返答が m, m - 1 のどちらか（つまり同じか減るか）になる。このとき 2 は元の位置のままで良い。

2 が最長共通部分列に入っていないときは、2 を動かしていくとどこかで正しい位置関係になって返答が m + 1 になる。そこで 2 を止めるとよい。

これを 3, 4, ..., n と繰り返すと n2 回ぐらいのクエリで秘密の順列が復元できる。

J

向き d で (0, 0) から関数 Fi を実行したときの最終地点 (tx, ty) と、途中で通った座標の x + y, x - y, -x + y, -x - y の最大値を各 i, d に対して計算すればよさそう。

でもこれ問題文に何も書かれてないところを見ると答えがめちゃくちゃでかくなって多倍長が必要そうで怖かったので手をつけていない。

K

橋をなくせばよいが、そのためには葉を頑張って繋ぐ必要がある。

再帰でまず部分木について考えるが、このとき葉の個数の偶奇によって 1 個か 2 個の葉だけは余らせたまま終わらせるようにする。（そうしておいて後で適切に結ばないと、部分木へ向かう辺が橋になってしまう）

余らせた葉を結ぶときは、まず 2 個のものたちを繋いだあとに 1 個のものたちを繋いでいく。（余った 2 個の葉どうしを繋げると、またその部分木が孤立してしまう）

ただし子が 1 個しかない場合とか例外もあってかなりハマってしまった。

L

読む気が起きなかった。