ゆるふわ競プロオンサイト @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 がとても参考になります。
続きを読む【祝】DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選【通過】
今年の本選にはコード部門に加え「装置実装部門」というのがあるらしく
なにそれ?
と思って参戦してみた
www.discoverychannel.jp
11/23(金祝) 21:00-22:30
いつもよりちょっと短い90分
(コンテストページはこちら)
4問目間に合わず3完110位…(22:38:44に4問目AC。あと10分あれば!)
1位〜109位までのお客様の中に2020年卒予定の学生さんが10人以上いらっしゃいましたら予選通過。
→通過しました。1/19(土)の本選「装置実装部門」でお会いしましょう。*1