naoya_t@hatenablog

いわゆるチラシノウラであります

全国統一プログラミング王決定戦 本戦

atcoder.jp
主催/日本経済新聞社 共催/AtCoder 協賛/TRI-AD,CISCO
2/17(日) @東京ドームホテル 大宴会場「天空」
f:id:n4_t:20190217151752j:plain

予選500位に入ったので決勝大会後のイベント&懇親パーティーに呼ばれて参加してきました。
f:id:n4_t:20190218181009j:plain
問題文は最初公開されていなかったのだけれど、本戦終盤頃にPDFで公開されたのでKindleに入れてちびちび考えていました。*1

chokudai社長 + PFNの秋葉さん西川さんのトークショーの後、上位3名によるエキシビション(20分8問のコンテスト形式+chokudai氏の実況)があって凄く面白かったし刺激的でした。
8問全完した準急さんのキー入力はめちゃ速いです。

500人懇親パーティーは美味しい食事+色々な人と話せて楽しかったです。
f:id:n4_t:20190217194643j:plain:w400
というわけで、本戦+エキシビションの問題を見ていこうと思います。

*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)について本気出して考えてみた

n個ある何かの0個以上から成る集合Snビットの整数で表すことにする。
このとき、集合に含まれる要素がk個なら全部でkビット立っている 。
__builtin_popcount(S) == k

この集合Sの部分集合Tをすべて列挙しようとすると、空集合も含め2^k通りある。
集合Sとしてありうる全てのパターンについてこれを列挙することを考えると、
n個からk個選ぶ組み合わせが_nC_k通りで、そのそれぞれについて2^k通りの部分集合があるので全部で \displaystyle\sum_{k=0}^{n}{_nC_k\cdot2^k} 通りについて考えることになる。

ここで驚くべきことは、任意の非負整数nについて
$$ \sum_{k=0}^{n}{_nC_k\cdot2^k}=3^n $$
が成り立つということである。

各ビットについて

  • SでもTでも立っている
  • Sでのみ立っている
  • SでもTでも立っていない

の3通りの状態がありうるのだから自明ではある。
bitDP回りでよくO(3^N)という数が出てくるのはそのためである。

実際の回し方については
ビットによる部分集合の列挙 - SRM diary(Sigmar) - TopCoder部
の解説がわかりやすい。

意地悪な制約の問題では計算量 O(3^N) では間に合わず、O(N2^N) に下げる工夫が求められたりする。
高速ゼータ変換/高速メビウス変換 - 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 がとても参考になります。

続きを読む