KUPC2014

7月5日にKUPC2014がありました.
僕は第一回のKUPC2011にはコンテスタントとして参加して(参加記d:id:sune2:20110807:1312714641),
その後の2012,2013には運営側として携わりました.
今年は運営の取りまとめ役として携わり,思い入れも強いので記事を書こうと思います.

準備

準備は3月くらいから始めました.
結構余裕があったはずですがやっぱり直前は忙しかったです.

本番

今年も京都と東京の2つのオンサイト会場を用意しました.
ATNDによると京都が36人,東京が50人(満員)の参加があり,大盛況となりました.
昨年は京都19人,東京22人だったようなので,かなり増えたことになります.
AtCoderでの参加者も300人超えで,早めに宣伝したことや,競技者人口が増加した?こと等によるのかなあと思います.

問題

全問についてコメントをします.

A. マッサージチェア

京大の情報学研究科の人たちがよくいる総合研究7号館にはマッサージチェアがあります(使ったことない).
どうもそれが壊れているらしくて,それをネタにしたA問題を作ると言っていたのですが,できた問題では壊れていませんでした.

B. 数当てゲーム

B相当の問題がなくて,リアクティブもDarkroomの1問しかなかったので簡単なリアクティブを目指して作ったのがこれです.
KUPCは色々な言語で参加してくれる方々がいますが,例を書いたC/C++以外の言語での解答でflushを忘れてTLEになっているものがそこそこあって,申し訳ない気持ちになりました.

C. 占い

元々は等号制約がなくて,N,M<=10^18でした.
この場合(僕はわかりませんでしたが)N+M-gcd(N,M)が答えになるのですが,それだけだと寂しいという事で
等号制約をつけてこのポジションに落ち着きました.

D. ハミング

ハミング距離といえば0-0,0-1,1-0,1-1をカウントしてどうにかするというのが主流でこれもそういうものです.
割と好きな問題です.

E. 何しちゃおっかな?

普通2x4しか思いつかないですよね….
タイリングというものをもっと知ってみたいなーと思いました.

F. テレパシー

割と普通の木DP?
最初自分が使ったINFが小さくてやられました.
Tの辺を自分で決められるという問題は解けるのでしょうか.

G. Darkroom

元々の想定解法はウロボロスの蛇(http://poj.org/problem?id=1392) を使う解法で,
これを愚直に使うと2logN回くらい,頑張って使うと2loglogN回くらいになるというものでした.
この問題がクエリ数4回で解けるというのはなかなか衝撃的です.

H. 自転車走

自分で作ったからか,結構簡単だと思っていたのですが,想像以上に解かれなくて驚きました.
結構WAやTLEが多く,AC率も悪かったようです.
適当に嘘解法っぽいものを信じて投げたら通ります.

I. Rain

最小費用流をする前にあらかじめ小さいグラフを構築する必要があると思ったのですがそんなことありませんでした.
ライブラリ以外のコード量は殆ど無いです.

J. カード

dp[i][j] = i 日目までに j 枚カードを持っているときの 所持ポイントのMAX
が全く思いつかなかったです.
実は,昇順にポイントを使うことにすると,毎日Pポイント貰うという制約がはずれるので,
dp[i][j] = i 日目までに j 枚カードを持っているときに必要なポイントのMIN
というDPを使って解くこともできます(解説はこれ).

K. 弱点

初め見た時,すぐにSA,LCPはわかったのですが,最大長方形をとって中に何種類の文字列に起因する接尾辞が入っているのかを調べるパートで少しつまりました.
Mを文字列の長さの合計とすると,setをマージしていく方法でO(M log^2 M)なのですが,実はNが大きければLCPをそんなに大きくできないことから,適当でも通ってしまったりします.
Wavelet何とかを使うと区間内のdistinctな値の数が効率的に求められるようですが知りません.

L. べき乗数

少し解説の補足をします.
まず,xがyより非常に大きいならo^..^o^x > o^..^o^yが,各oに2,3,5,7の何を入れても成り立つ,というのが大事です(oの数は両辺一緒).
L以上のべき乗数をp1^...^pm^xと表した時,その大小関係は
(m, x, pm, … , p1)
の辞書順によって決まると言っています.
まずmですが,これは2^LがHより非常に大きいことによります.
2^LがHより非常に大きいことにより,例えば,2^2^2^2^L > 7^7^7^H が成り立ちます.
これより,x,pm,...,p1がなんであろうと,mが大きい方が大きいということが言えるのです.
次にxですが,これはxがそれぞれ非常に異なるので,その後の列がなんであろうとやっぱりそれらも非常に異なることになります.
pmが入ったあとも,pm^xはそれぞれ非常に異なるので同様のことが言え,以下同様となります.

このような辞書順の比較に帰着したかったので,あのような性質を持つLとHを見つける訳ですね.
ちなみにLとHはべき乗数を小さいものから順にヒープを使って生成していくと見つけることができます.

難しいです….

まとめ

難易度調整がうまくいったか不安ですが,全ての問題が解かれ全完が出ないという基準は達成されたのでよかったです.
参加して頂いた皆さんありがとうございました.