全国統一プログラミング王決定戦 本戦
atcoder.jp
主催/日本経済新聞社 共催/AtCoder 協賛/TRI-AD,CISCO
2/17(日) @東京ドームホテル 大宴会場「天空」
予選500位に入ったので決勝大会後のイベント&懇親パーティーに呼ばれて参加してきました。
問題文は最初公開されていなかったのだけれど、本戦終盤頃にPDFで公開されたのでKindleに入れてちびちび考えていました。*1
chokudai社長 + PFNの秋葉さん西川さんのトークショーの後、上位3名によるエキシビション(20分8問のコンテスト形式+chokudai氏の実況)があって凄く面白かったし刺激的でした。
8問全完した準急さんのキー入力はめちゃ速いです。
500人懇親パーティーは美味しい食事+色々な人と話せて楽しかったです。
というわけで、本戦+エキシビションの問題を見ていこうと思います。
*1:本番ではネットワークトラブル回避のため問題文が紙で配られたそうです。
ゆるふわ競プロオンサイト @FORCIA
forcia.connpass.com
2/9(土) 14:00-
FORCIAさんで開催されたオンサイトのゆるふわコンテストに参加。
(over28枠に空きが1つ出たのを知って前日に登録)
最初404が出てコンテストがなかなか始められず(CTF?)、HackerRankでコンテスト開催経験のある人が呼ばれて対応に当たっていた…
そして15分遅れて(URLを変更して)コンテスト開始。
100-200-300-400-500-600-700-800 という配点と問題の体感難易度が大きくずれていた気がする。
4完(+部分点)で27位とかそのくらい。
Programming Problems and Competitions :: HackerRank
コンテストだけ出て懇親会は(ピザonlyであることが知られているので)帰るつもりだったけど、皆さんと色々話してて結局懇親会の最後(19:00)まで滞在。(お菓子と飲み物があって助かった)
FORCIAさん@matsu7874さんどうもありがとうございました。
Educational DP Contest / DP まとめコンテスト〈EDPC〉補習篇(T,U,V,W,X,Y,Z)
コンテスト後に読んだ問題たち。ここで出てくるテクニックもこの機会にぜひ身につけておきたい。
参考:
www.hamayanhamayan.com
kyopro-friends.hatenablog.com
↑競プロフレンズさんてチームで戦ってるの?それって規約的にどうなの?*1
〜
*1:嘘ですこないだDDCC Finalで御本人拝見しました
〈説明用メモ〉O(3^N)について本気出して考えてみた
個ある何かの0個以上から成る集合をビットの整数で表すことにする。
このとき、集合に含まれる要素が個なら全部でビット立っている 。
(__builtin_popcount(S) == k
)
この集合の部分集合をすべて列挙しようとすると、空集合も含め通りある。
集合Sとしてありうる全てのパターンについてこれを列挙することを考えると、
個から個選ぶ組み合わせが通りで、そのそれぞれについて通りの部分集合があるので全部で 通りについて考えることになる。
ここで驚くべきことは、任意の非負整数について
$$ \sum_{k=0}^{n}{_nC_k\cdot2^k}=3^n $$
が成り立つということである。
各ビットについて
- でもでも立っている
- でのみ立っている
- でもでも立っていない
の3通りの状態がありうるのだから自明ではある。
bitDP回りでよくという数が出てくるのはそのためである。
実際の回し方については
ビットによる部分集合の列挙 - SRM diary(Sigmar) - TopCoder部
の解説がわかりやすい。
意地悪な制約の問題では計算量 では間に合わず、 に下げる工夫が求められたりする。
高速ゼータ変換/高速メビウス変換 - naoya_t@hatenablog
の出番である。
Educational DP Contest / DP まとめコンテスト〈EDPC〉
1/6(日)20:00-25:00
始まった時点で家に帰る途中で20:14に参戦。
途中30分弱離席したけれど結局最後までやってて全26問中16完で172位
フル参加できてたら+1〜2問ってところか。
終わってから残りの問題にもひと通り目を通したけれどまだ習ってないテクが必要な問題がある。ぜひ今回持って帰りたい。
→ Educational DP Contest / DP まとめコンテスト〈EDPC〉補習篇(T,U,V,W,X,Y,Z) - naoya_t@hatenablog
ABC 114 Cを桁DPでも解いてみた
「桁DPで解きたくなる誘惑に負けず全探索で解くべき問題」ABC 114 Cを、後学のために桁DPでも解いてみたメモ。
(本番では3,5,7のみで出来た9桁までの数を全列挙しました)
桁DPのアイデアと実装については桁DP入門 - pekempey's blog がとても参考になります。
続きを読む