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

読む気起きず。

続きを読む

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 ≦ 105 で、座標はでかい。

F

やるだけ。

G

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

H

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

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

n ≦ 105 で、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 は 105 以下で、質問は 100 回までやっていい。

J

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

K

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

続きを読む

ICPC ひとり地区大会 2013 杭州

ひとりで地区大会練習をした。(LiveArchiveで)

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

問題PDF: http://acm.zjut.edu.cn/regional2013/Problems.pdf

AC Penalty A B C D E F G H I J K
7 977 56+3 144+0 9+0 - - 211+1 +1 176+0 68+0 233+0 -

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

本番順位表だと 6 位だった。 G が分かって書けたが WA で悲しい。

以下、問題について。

続きを読む

帰ってきたお誕生日コンテスト 解説・講評

コンテストサイト: http://kcs.miz-miz.biz/contest/1009/

参加してくださった皆様、ありがとうございました。皆様の貴重な時間をこのようなコンテストに割いて下さったこと、感謝してもしきれません。

このコンテストは発案から開催までの準備期間が 10 日しかなかったので様々なところがガバガバなのは許してください!!!何でもはしません!!!!!!

というわけで、出題された全 26 問の解説・講評です!

続きを読む

2014年の目標改

今年の年始に立てた目標(IIDX SP皆伝、DDR DP足龍)を早くも達成してしまったので、目標を引き上げておきます。

IIDX

SP☆12未難3以下

冥、卑弥呼、灼熱を意識していますが、今年中にこれら 3 つに匹敵する譜面が現れた場合は目標を緩めます。

DDR

DP足紙

どうせ目標ということなら足神でも良いかな、と思いましたが、VOL 160 にはポゼ激(足17)とかロンドンA鬼(足17)をフルコンかほぼフルコンしないといけないらしいので、さすがに実現性が低すぎると感じて足紙にしました。

IIDX SP 振り返り

本日 beatmania IIDX 21 SPADA において悲願のSP皆伝合格を達成しました。そこで、一旦これまでの段位認定歴を振り返ってみます。

2012年
  • (Lincle)
  • 5級(2/27)
  • 4級(2/27)
  • 3級(3/1)
  • 2級(3/6)
  • 1級(3/14)
  • 初段(3/15)
  • 二段(4/5)
  • 三段(4/6)
  • 四段(4/10)
  • 五段(4/12)
  • 六段(4/19)
  • 七段(6/3)
  • 八段(6/20)
  • 九段(9/17)
  • (9/25 tricoro稼働開始)
  • 八段(9/25)
  • (12/5 九段・十段解禁)
  • 九段(12/16)
2013年
  • 十段(1/31)
  • (11/13 SPADA稼働開始)
  • 八段(11/13)
2014年
  • (2/19 九段・十段解禁)
  • 九段(2/20)
  • 十段(2/20)
  • (3/26 皆伝解禁)
  • 皆伝(3/27)

まとめると、

  • Lincle 後半ぐらいから IIDX を始め、稼働終了直前に SP 九段をとる。
  • tricoro では十段解禁から 2 ヶ月後には SP 十段をとり、その後稼働終了まで十段。
  • SPADA にて皆伝解禁翌日に皆伝を受け、幸い1発で合格。

でした。