t8m8-mem8

競プロとか、学んだことを書いていきます。

競プロ&CTFを同時にする!YEHD2015を開催した。

先日、Year End's HackDay 2015 というイベントを開催した。

YEHD2015は競プロとCTFを同時に行って得点を競うコンテストで、たくさんの方が参加してくれた。
運営委員長兼サーバ担当は3846masaくん、CTF担当はkkrntくん、競プロ担当は僕だった。

ルールはざっくりこんな感じ。

  • 競プロとCTFの問題が一気にでるから好きな順番で解く。
  • 5時間で競プロとCTFの合計得点が最も高い人が優勝。
  • 個人で参加しても、3人までのチームを組んでもok。
  • 各問題ごとにFirst Acceptの人にはその問題の得点が1割増しで与えられる。

競プロの問題は計11問で、今回の作問はすべて僕が行った(テスターもいなかった)。
作問は1人でやるべきではないけれど、サークル内で競プロをやっているのが僕だけだったので許してください><(みんな競プロやろう)。
作った問題は↓に置いてある(Mathjaxが効かないのでTeX記法になっているところは読みづらいかも)。

github.com

普段競プロのみをしている人、普段CTFのみをしている人、どちらもしている人、どちらもしていない人、というように来てくれる方の経験がバラバラだったので問題の難易度をどうするかだいぶ悩んだ。
問題の半分いかないくらいから解いた人数が2人とかになってしまったので、簡単な問題(ABCのAやBくらい)をもっと増やしたほうがよかったかなーって思ってる。


問題

Problem A: クリスマス

全員が解けるような問題として出題した。
{\lceil \frac{N}{M} \rceil}を出力してくれれば通る。

Problem B: Cryptographic Message

ヴィジュネル暗号を復号するプログラムを作ってね、という問題。
問題に与えられている定義どおりに文字列を辿りながら変換していくと解が求まる。

当日は暗号化されたPDFのみを与えて、解読しないと問題文が読めないようにしていた。
中身をエディタとかで見て、末尾のほうにある文字列をBase64としてデコードすると問題文が現れる。

Problem C: 優勝者

連想配列などの文字列に数値を対応付けられるデータ構造を使ってカウントしていけば良い。

Problem D: ナイト

わいわい話し合いながら考えてもらえるといいかなと思って出題した問題(残念ながらほとんどの人がチームではなく個人でやっていたのでそうはならなかった)。
実は{N \geq 5}{N \times N}のマスではナイトは各マスを1度しか訪れずに全てのマスに訪れることができる。
{N = 4}のときは16手ですべてのマスに訪れることができ、{N = 2,3}のときはどうしてもたどり着けないマスが存在する。
Knight's tourとかを聞いたことのある人は瞬殺だったかもしれない。

Problem E: 1cm = 1cm

{a=30,b=24}を例にして説明する。
其々を素因数分解すると、{a=2 \cdot 3 \cdot 5, b=2^{3} \cdot 3 }となる。
{lcm(x,y)=lcm(a,b)=2^{3} \cdot 3^{1} \cdot 5^{1}}となる{(x,y)}を求めれば良いとわかるので、
{x=2^{sx} \cdot 3^{tx} \cdot 5^{ux}}, {y=2^{sy} \cdot 3^{ty} \cdot 5^{uy}}と表した時に、{max(sx,sy)=3 \land max(tx,ty)=1 \land max(ux,uy)=1}を満たすような{(x,y)}の個数が解となる。
{(sx,sy)=(3,0),(3,1),(3,2),(3,3),(2,3),(1,3),(0,3)}の7通り。
{(tx,ty)=(1,0),(1,1),(0,1)}の3通り。
{(ux,uy)=(1,0),(1,1),(0,1)}の3通りとなるので、{7 \times 3 \times 3 = 63}通りとなる。
あとはこれを実装すればok。

Problem F: 友利奈緒

CTF勢から友利奈緒問を作れという圧力を受けた気がしたので作った問題。
木を全探索をすれば通る。

これもPDFが渡されて、そのままだと問題文が読めないようになっていた。
読めない部分をコピーしてエディタとかに貼り付けると読めるようになる。

Problem G: RGB-Query

画像の特徴色抽出をするコードを書いている時に思いついた問題。
累積和と包除原理を使う、のはずがよく考えたら与えられたものを素直に持っておけば愚直にやって通ってしまう...。制約をもっと厳しくするべきだったと反省。

Problem H: 逆転時計

元ネタはハリーポッターのtime turner(逆転時計)。
情報学を学ぶグレンジャーが留年の危機なので研究費で逆転時計を買ってもらう話。
二分探索+貪欲って感じの問題のつもりでいたら、これも貪欲だけで良いことを指摘されてしまった。区間スケジューリングを知っていれば解ける。

Problem I: ナイト再び

隣接行列を作ってM乗すると解が求まる。繰り返し二乗法を使わないと落ちる。

Problem J: 気まぐれ勇者

終了後の投票では競プロで一番好評だった問題。
想定解法は逆向きにダイクストラ。これは制約を緩くしてあるので、他にもいろいろやりようがあると思う。

Problem K: Non-decreasing Sequence of Longest Increasing Subsequence

ソート過程の最長増加部分列(LIS)の長さを求めていく問題。
愚直に毎回LISを求めようとすると、O(NlogN)のDPでも間に合わない。
まず一回、O(NlogN)のDPでソート前のLISを求める。
このDPは蟻本に載っているように、
dp[i]:=長さがi+1であるような増加部分列における最終要素の最小値
とする。
ソート途中、ソートを行った後半部分は増加列になっているので、(前半部分の非ソート済みのLISの長さ)+(後半部分のソート済みの列の長さ)が各ステップで求めるべきLISの長さになる。

非ソート済みの数の中での最大値(そのステップでソート済みにする数)をxとすると、xを越えない最大の数をDPテーブルから二分探索することで、その値が見つかったインデックス+1が非ソート済みの列でのLISの長さとなる。


反省

  • 解読しないと競プロの問題が読めなかったりと、同時開催ならではの問題もいれることができて良かった。
  • 競プロとCTFの合計得点を同じにしようとしたのは失敗だった。競プロの1問1問に対する得点が大きいので、競プロができる人が無双する感じになってしまった。
  • たくさんの問題を作るのは良い経験になった。
  • もっと良い問題を作れるように精進したい。

おわり

参加してくれた皆さんありがとうございました。
運営の皆さんお疲れ様でした。


他の運営者の記事

3846masa.hatenablog.jp

kkrnt.hatenablog.com