ゼオスTTのブログ

気が向いた時に、主にプログラミング関係の記事を書くつもり。しかし気が向かない。

CODE THANKS FESTIVAL 2017参加記

CODE THANKS FESTIVAL 2017に参加した。

参加権のある最後のCODE (THANKS) FESTIVAL。
2013~2016はCODE FESTIVALの方に出られていたが、年々上がる予選のレベルについていけず、最後の年はTHANKSへの参加となった。
最近はCODE FESTIVALやGCJのような大きなコンテスト以外ほぼ出ていない半引退状態、かつこれまでも割とギリギリで通っていた程度の実力だったため、妥当な結果と言える。

予選

予選A、B、C、ともに3完。
順位は、最も良かった予選Cでさえ327位。
この順位での予選突破はさすがにないだろうと諦めていたが、後日「CODE THANKS FESTIVALにぜひご参加いただきたく、ご連絡いたしました。」とのメールが届く。

予選Cでratingが1576まで上がったため、本戦で青コーダー(1600以上)になって年を越してやろうなどと考える。

前日

オンサイトコンテストの度に更新プログラムで冷や汗をかいていたので、今回は学習して前日に済ませる。
1年に2、3回しか起動しないためか、ものすごく時間がかかった。

(にもかかわらず、本戦終了後の帰り支度の際、「更新してシャットダウン」が表示されていた。なぜだ)

本戦

~開場

asa!

余裕を持って会場入りするため、早めに家を出る。

山手線が人身事故で運転見合わせになったり、ゆりかもめが揺れかもめだったりしたので、早めに家を出て正解だった(?)。

会場はテレコムセンター駅直結ということだったが、駅とセンターを結ぶ通路から中を覗くと警備員っぽい人が2人いて、入っていいのかよく分からなかったため引き返す。
無難に正面の入り口から入り、東棟14階を目指したが、エスカレーターでは1階~5階、エレベーターでは20階と21階にしか行けず、詰む。

吹き抜けの辺りにFPS感を覚えつつ、探索を続けること十数分。
結局、先ほど入るのをためらった場所に案内を見つけ、解決。
ほんと、早めに家を出て正解だった。

会場前のリフレッシュコーナーで開場を待つ。
しばらくすると、我らがアイドルちょくだいさんがやってくる。ちょくちょくー。
「実は、100点問題ではループは要求しないことになっている」といった裏話を聞く。

また、話題のtouristじゃんけんに挑戦するも、惨敗。

コンテスト前

交通費申請のフォームを埋める際、交通手段の選択肢に「私鉄」や「第三セクター鉄道」がなくて焦る。
調べてみると、文脈によってはそれらも「在来線」に含まれるらしい。
毎年、私鉄も領収書貰ってたわ・・・。

ratingは場内75位。
無難に75位以内を目指そうかとも思ったが、欲を出して50位以内を目指す。
その順位なら、きっと青コーダーになれる。

が、非常に残念なことに、

悲しい。。。

パーカーは1800点以上。
順番に100、200、300、300、400、500と解けば手に入る設定だが、500は今まで2問しか解いたことがないらしいため、不安を覚える。
また、ネットがかなり重く、任意の遷移に十数秒かかったり、たまに接続が切れたりしたため、それが原因でパーカーを逃すことだけはないよう祈る。

コンテスト

案の定、問題を開くのにも提出するのにも時間がかかり、辛かった。

最終的な順位は40位で、無事目標達成。

A - Time Penalty (100)

ループして最大値を求める。
あれ、100点問題ではループ出ないんじゃなかったの・・・。

B - Concatenated Palindrome (200)

|S|が小さいため、何も考えずに全探索。
substr() や reverse() が使いたかったが、C言語にそんなものはない。

C - Factory (300)

一目見てpriority_queue。が、C言語にそんなものはない。
ライブラリを貼り付けたが、なぜか正しく動かない。
どうやら、この前C89な部分をC99に置換機能で更新した際、バグを埋め込んでいたらしい。

D - Bus Tour (300)

典型的なGCD問。
Cでかなり苦しんだ(個人的な理由だけど)ため、Dがこんなに簡単でいいのか、と入念に確かめる。
しかし、このコンテストはペナルティがないので、さっさと出してしまう方が賢い選択だったに違いない。

E - Coin Authentication (400)

久々のインタラクティブ問。
Authenticationとか言われるとCTF感があるが、CODE THANKS FESTIVALも略すとCTFなので、あながち間違ってはいない。

少し考えて、コインの枚数を13^0, 13^1, 13^2, \cdotsのように決める(13進数で考える)と、重さの合計からw_iを逆算できることに気付く。
しかし、13^4 = 28561 > 10000のため、これでは1回の質問で4つしか重さを特定できず、10回で50個という要求は満たせない。
逆に、10回で50個特定するには1回で5個特定する必要があり、枚数の最大が10000 = 10^4であることから考えると、10進数で考えられれば解けることが分かる。

10^0の位が8、9、0、1、2の場合、10^0の位に対応するw_iはそれぞれ8、9、10、11、12と逆算できる。
また、10^1の位以降も、下の位からの繰り上がりに注意することで、同様に対応するw_iを逆算できる。
よって、10進数でも考えることができる。

解説では、重さの合計から8 \times (枚数の合計)を引き、5進数で考えるやり方が紹介されていた。なるほど賢い。
5進数であれば、枚数の最大が1000でも1回で5個特定できるし、10000なら1回で6個特定できるため合計9回で済む。
それにもかかわらずこの制約なのは、5進数以外の解法も許容するためだと思われる。

個人的に、今回の問題セットで最も楽しい問題だった。

F - Limited Xor Subset (500)

愚直なDPだとO(NK)となり間に合わない。

どーしろってんだとずっと悩んでいたが、制約a_1 + \ldots + a_N \le 10^5が妙に大きく表示されていることに気付く。
もしや状態数はそれほど多くならないのでは、とmapを使ってDPを書いた(C言語だとさすがに辛いのでC++を使用)ところ、なんとAC。

これにより1800点を達成したため、パーカーを獲得。
凍結後だったため、パーカー獲得を喜ぶツイートは解除後まで控えることにしたのだが、そのまま忘れて結局していない。

解説中に気付いたが、私のコードはaをソートしておらず、嘘解法だった・・・。
これで思い出したが、蟻本でO(|E|\log|V|)として紹介されているダイクストラ法のコードは実際にはO(|E|log|E|)で、毎回更新が起こるような入力に対しては、O(|E|log|V|)の実装よりはっきりと遅くなる(確認済み)。O(|E|\log|V|)O(|E|\log|E|)も同じでした。失礼しました(@btk15049さん、ご指摘ありがとうございます)。

G - Mixture Drug (600)

最大独立集合問題。
いかにも半分全列挙な制約だが、列挙した後どうするかが分からない。

いっこうに解ける気配がしないので、弁当を食べたり、凍結後の順位表を眺めて気になる人の応援をしたりする。

H - Union Sets (600)

こういう問題、解けるようになりたい。

コンテスト後

コネクションハントで「これまでに獲得したTシャツの数」を聞いて回る。
平均5、6枚くらいだろうと予想していたが、1枚(今回が初めて)や2、3枚といった回答がほとんどで、5、6枚はあまりいなかった。
予想と結果の乖離に、自分が着実に老害へ近づいていることを知る。
10枚や12枚との回答には安堵。
さすがにTシャツでベッドカバーを作ったというような人はいなかった。

懇親会では、ふーらくたるさんへの独自取材により、話し始めた瞬間、周囲が突如真空状態になり、発した声が聴衆の元に届くことが物理的に不可能になってしまったという、聞けば感動間違いなしの名スピーチの内容を聞くことに成功。
ふーらくたるさんが口を開くや否や、感動の嵐が巻き起こり、しばらく涙が滝のように流れ続け、それはもう、脱水症の危機を感じるほどだった。

帰宅

せっかく東京に来たからと、新橋で一泊。
翌日、ゆっくり観光などをしてから帰るつもりだったが、途中で寄った秋葉原で大きな買い物(3770Kを7700Kに更新!)をしてしまい、怖くなって早めに帰宅。

かくして、私のCODE THANKS FESTIVAL 2017は幕を閉じる。

感想

今年も最高に楽しかったです。
問題の難易度もちょうど自分に合ってたし、いろいろな人と交流することもできたし。

交流といえば、新しくできたコネクションハントは個人的にかなり良いコンテンツでした。
話のきっかけを提供してくれたおかげで、コミュニケーションが苦手な自分でも楽しく交流ができました。
ボードゲームもやりたかったなー)

人生最後のCODE (THANKS) FESTIVALが終わってしまったのは残念ですが、これからも競プロは続けていくと思います。老害として。

最後になりましたが、運営の皆さん、お話をしてくれた皆さん、ありがとうございました!