Ark's Blog

引っ越しました→ https://blog.arkark.dev/

ようこそ

CODE THANKS FESTIVAL 2017 参加記

12/2にCODE THANKS FESTIVAL 2017に参加してきました。

f:id:ark4rk:20171203201334j:plain

www.recruit-jinji.jp

予選

  • 予選A: 用事があったので不参加
  • 予選B: AB解いて417位
  • 予選C: ABC解いて311位

あんまり芳しい結果は得られなかったけどTHANKSには通ったので嬉しかったです。

codefes本戦は去年行ったので今回で二度目です。

当日

会場はコワーキング・スペースMONOでした。

f:id:ark4rk:20171203201105j:plain:w200

コンテスト

f:id:ark4rk:20171203164906p:plain:w100

3時間コンテストで、パーカーボーダーが1800点以上でした。

A問題

やるだけ

B問題

愚直に小さい長さから回文の検査をする。

ここまでは順調だったけどCで悲劇が起きた。

C問題

「ある機械でプレゼントを 1 個作るたびにその機械のみが劣化して」の部分で「劣化がすべての機械で起きる」と勘違いして、a_i+(s_i-1)b_iではなくa_i+(s-1) b_i (siに依存しない)で考察。 priority queueでいけることはすぐ気づいたけど、ずっとこの誤読に気づかなくて60分くらいロスした。これかなり痛い。

ここまでで\frac{1}{3}も時間を使ってしまったのでこの時点でかなり焦ってた。

D問題

見た瞬間gcdっぽいなあと思ったけど、考察したらやっぱりgcdだった。

でもgcdに気づきにくいテストケースだったと思う。

E問題

インタラクティブな問題は出るとか全く予想してなかったので、面食らった。最初、本物と偽物で重さの偶奇が違うなあと思って、偶奇の処理で攻めるのかなとか考えてた。

しばらく考察してたら、「コインの種類は5種類、投げられるクエリの最大数は10回、袋の最大数は50個」という条件から、これ5進数的に処理すればいけるんじゃない?と気付き実装したら通った。

このとき、残り時間40分くらい、パーカーボーダーまであと1問という厳しい状況に置かれてた。

F問題

見て、これはdpだと直感した。けどここでまた誤読を発動した。

制約の a_1 + \cdots + a_N \leq 10^5 a_1 , \cdots , a_N \leq 10^5と勘違い。どうやってもO(NK)のdpしか思いつかなくてむりむりってなってた。

一旦、諦めてGへ

G問題

制約のN\leq 40を見て、半分全列挙っぽいなぁとか考えてたけど、マージどうやるんだ????で詰み。時間も迫ってたのでHへ

H問題

おっこれはクエリ先読みUnionFindかな?と思ったけど、問題難易度700なのでそれはないと思い、素直に問題文をちゃんと読んだ。

永続化すればいけるのでは??とか考えたけどライブラリを持ってなかったし実装の仕方もよく知らなかったので、別の方針とか考えてたらどんどん時間が経過していった。

良い解法が思いつかなかったのでFへ

F問題(再び)

ここで誤読してたことに気づく。は?という感じだった。(この時点で残り5分くらい(やばい(やばい

咄嗟に、この制約だと値が重複する確率がかなり高そうだし、dpをHashSetで管理すれば行けるやろ~~~~とありえん急いでコード書いて投げた。

f:id:ark4rk:20171203180408p:plain

通った。

残り20秒でした。

結果

なんとかパーカーをゲットできました。やった~。

f:id:ark4rk:20171203180653p:plain

順位は56位で、パーカーボーダーの人になりました。

解説

コンテスト後、chokudaiさんによる解説が始まりました。 適当に提出したFと解けなかったGとHは特にしっかり聞いた。

F問題

うん。やっぱり提出したコードは嘘解法でした。

2^{16}, 2^{15}, 2^{14}, \cdots, 2^1, 2^0, 2^0, 2^0, \cdotsの順でa_iの入力が来てたら早い段階でハッシュが貯まるので、TLEしちゃう。事前にソートしとけば、解説にある考察によりTLEしないはず。

追記(12/9): 今回の誤読をしていてもがんばって解く解法があったみたいです。すごい → Code Thanks Festival 2017 F Limited Xor Subset 解説 | 東京工業大学デジタル創作同好会traP

G問題

想定解法の一つは半分全列挙+bitDPでした。マージの仕方とかうまいなぁ。bitDPで前計算というのもなかなか。

半分全列挙はナップサック問題でしか出会ったことがなかったので、まだ身に付いてない感があるなぁ・・・

帰宅したあと実装した。

H問題

想定解法の一つは「UnionFindの併合処理の過程でできる森から、LCAをダブリングで求め併合されたタイミングを得る」というものでした。なるほどな~~~。

あと、chokudaiさんが「Quick Findなるものもあるよ」みたいなことをおっしゃってたので後で調べてみる。初めて聞いた。

懇親会&コネクションハント

解説後は懇親会でした。あと、コネクションハントという、「一つ質問を決めて、みんなからの答えを集めよう」みたいなイベントも並行で行われました。

コネクションハントで尋ねられた質問で個人的に気に入ったのは「あなたは何界のtouristですか?」と「好きなセグ木は?」ですね。

初めて会った人とも色々話せたし楽しかったです。

感想

かなり競プロのモチベーションが上がりました。 やっぱり競プロたのしい。

運営の方々、ありがとうございました。 来年も参加したいです。