Xmas Contest 2010
Commentary

Xmas Contest 2010 – Commentary2

はじめに
Xmas Contest 2010 は昼の部, 夜の部を合わせて 98 人と, 直前の告知だったにもかかわらず多くの方にご参加いただけて感謝しています. もし問題を楽しんでいただけたなら幸いです. コンテストの存在を広めてくださった皆さまも, どうもありがとうございました.

結果
昼の部, 夜の部を合わせた最終順位表です.
名前ABCDEFG

H

得点

1

rng 58

100

100

100

0

—

100

100

100

600

2

pes

100

100

100

100

—

10—

100

510

3

semiexp

100

100

100

50

—

—

10100

460

4

JAPLJ

100

100

10050

—

10—

100

460

5.shiomori

100

100

10050

—

10—

100

460

6((i(i(i(iwi)i)i)i))

100

100

10050———

100450

7

mirac

100

100

10050———

1004508

Takashi Tayama

100

100

100300——100430

9emk

100

100

100300—0100

430

10nai

100

100

100

30

———100430

順位

rng 58 さんが 6 問正解で 1 位となりました. おめでとうございます. 2 位には 5 問正解の pes さん, そして以降 4 問正解の方々が続く, という結果になりました.
正解者の少なかった, 問題 D, E, F, G で高得点を獲得した方々を紹介します.
問題

名前得点D

pes

100

D

tsukuno70

E

gusmachine90

Eqnighy60

Frng 58100G

rng 58100

Gomeometo

100

難しい問題に挑戦していただきありがとうございます.
各問題ごとの得点の分布は次のようになりました.Xmas Contest 2010 – Commentary

3得点ABCDEFGH1004880

2610124390000010018000400000700211000060

33

100100050

001

8000

6400

1

700001

30

400

8000

320

300

10001

1000

420

3

120

73

19

3

72236

各問題コメント
問題ごとの, 出題意図, ジャッジの感想, などなどです. 解法の詳しい解説は別ファイルを参照してください.

Problem A: Christmas Trees
うさぎさんとねこさんとくまさんときつねさんが登場しました. また, Metr さんも登場しました.
問題そのものは簡単めな算数. ですがしっかりとトラップを 40 点分用意しました.
サンプルは c ̸= d を満たしつつできるだけ強くしようという意図で, mod 7 (= a + b) でいろいろな値になるようにしておきましたが, そこまで強くもなかったようで, 序盤は WA で 30 点になってしまった方が多かったです.
計算量による部分点も一応用意しておきましたが, 狙っている方はほとんどいなかったようです.
最初の正解は semiexp さん (9 分 26 秒) でした.

Problem B: Simple Parsing
問題冒頭の某国の問題も, 某世界大会のあれよりはずいぶん平和……, という話はおいといて, B から構文解
析です.
問題文をよく読むと偶奇だけを答えればよいので難しくない問題であることがわかります. 丁寧に構文解析するのもそんなに大変ではない程度で, 奇数の個数を調べている人も構文解析をしている人もそこそこの割合でいました.
結果を見ると最も簡単な問題になったようです. 誤答としては, 文字列を 32 ビット整数に変換してしまったことによるトラブルなどが多少ありました.
最初の正解は ((i(i(i(iwi)i)i)i)) さん (5 分 17 秒) でした.

Xmas Contest 2010 – Commentary

4Problem C: Connect The Decoration
1 問くらいは問題文に余計なストーリーが多いのを出そうという意図でこの問題文を書いてみましたが, 読みにくいだけでなく, 題意が曖昧 (木を作るのか一列に並べていくのか) になってしまっていました. その辺はもう少し丁寧に書いてもよかったなあ, と反省.
さて, si = 1 を「すごくお気に入り」と考えていると見られる誤答がたくさん提出されてしまいました. 問
題文を書くとき, 「すごくお気に入り」ばかりであることをどう表現しようかなと思っているうちに書き方が浮かんだため, 0 と 1 が直感に反しますがそれもありだろうと思って決定しました. ここまでならよかったのですが, 手で作ったサンプルの 1 つ目が si をどちらで解釈しても通るものに偶然なったがために, もう 1 つのサンプルもそんな感じにしてしまおう, となりトラップが完成しました. 問題 A 以上にはまると大変だったかもしれません.
問題が正しく読めると, 最小 Steiner 木問題ですが, 最小全域木の問題です. 個人的には, 最小全域木はプロ
グラミングコンテストでは「たまに」出題される印象で, いかに最小全域木っぽくない見かけにするかが問題の巧さではないかと思っています. 解法は単純ですが, 最小 Steiner 木問題を知っていてそう認識してしまうとかえって気づきにくい, というところもあったかもしれません.
最初の正解は mirac さん (54 分 51 秒) でした.

Problem D: Presents↑に DP と書いてあるように, 動的計画法の問題でした.
「疲れ度が x2 y 」によって状態数が抑えられる DP を作ろう, と思っていろいろ問題を考えているうちに,計算量が面白い感じの問題ができたので出題しました. 実は今回の問題セットの中でこれが一番気に入っています.
しかし計算量の見積もりは大半のケースではかなり緩い評価であり, 嘘解法で何人かに通されてしまうだろうな, という予想をしていました. 実際にはそのようなことはなく, 唯一正解の pes さんの解法は想定解法通りでした. その他の方は, 買うプレゼントの個数の上限を 1000 や 10000 程度に設定した 30 点や 50 点の部分点が多かったです.
最初の正解は pes さん (3 時間 20 分 33 秒) でした.

Problem E: Donuts「誰も提出してくれなかったらどうしよう」と思っていましたが, 9 人の方に提出していただき, 2 人の方が正の得点を獲得し, 安心しました.
一応最終防衛問題のつもりでの出題で, 数値積分で部分点は取れるような感じにしました. しかし極座標の数値積分によって高精度で解けることを想定していなかったので, 提出を見ていてなるほどという感じでした.
数値積分解の場合の TLE は見た目以上に厳しかったと思います.
ジャッジデータは Java の BigDecimal を用いて精度の高い解を作って用意しておきました. BigDecimal の三角関数やら平方根やらを自前で実装するのは結構心が折れる作業でした.
正解者なし. 最高得点は gusmachine さん (3 時間 0 分 29 秒) でした.

Xmas Contest 2010 – Commentary

5Problem F: Christmas Magic
いわゆるフロー枠です. 1 週間前の某コンテストで最小費用流の問題を見たときに「ネタが被った！ 大変だ！！」と思って急遽問題 G を増やしたという経緯があります.
慣れている人にとっては, “行から列へのフロー” という構造が見えてしまえばさほど大変ではないですが,流量下限つきのような問題であるため実装時に混乱しがちです.
この問題は, 出力チェッカ作成にとても苦労しました. 私が Perl で書き, imos さんに PHP で書き直してもらう, ということを行いましたが, チェックに 64 ビット整数が必要→ PHP で多倍長整数が必要→実装, ととても大変な作業を imos さんに任せてしまいました. また採点にも時間がかかり, うまく行くか心配なところでした. 結果的には目立った問題は生じずよかったです.
最初の正解は rng 58 さん (3 時間 22 分 47 秒) でした.

Problem G: Strange Sequence
いかにもな感じの問題文と 0 しかないサンプル出力. テストケース分の 0 を出力するコードを提出した方が多かったですが, 残念ながら解は存在します.
数列の部分和の条件に言い換えるのが本質で, それに気づけばちょっとした実験とちょっとした数論とちょっとした数え上げで解くことができます. また, サンプルが弱いので, 全探索などを書いて手元でテストするとよいでしょう.
最初の正解は rng 58 さん (52 分 26 秒) でした.

Problem H: Read Me
お詫び

昼の部の最初の段階でジャッジデータに誤りがありました. リジャッジによる混乱を招いてしまって申し訳ありません.
問題 D が当初の予定より難しくなり, 問題 G が追加され, これでは簡単な問題が少ないのでは, と思ってコンテスト 3 日前くらいに思いついた問題です. 実装するだけなので, 他の問題を考えたい方は気分転換にでも,という意図でした. 最後の問題がこれだと知っているのと知らないとでは割と違うかなと考え, ちゃんと読んでもらえそうな問題タイトルにしました.
罠としては, テストケース数をちゃんと調べたか, という点がありました. ひっかかってしまった方も結構いたようです.
ちなみにジャッジデータには実際の問題 A 〜 G の入力データすべて (+α) が用いられています.
最初の正解は tozangezan さん (54 分 36 秒) でした.

運営
■ジャッジ

imos, hos

■企画・問題作成■連絡先hos

質問, 意見, 苦情等ありましたら hos0cyclyrical3141 _at_ hotmail.co.jp までどうぞ.