ICPC 2023 Asia Yokohama Regional 参加記 (LuzhiledFanClub zawatin)

前置き

zawatin.hatenablog.com

これは嘘でした。問題解いた時の復習記事以外でははてなブログを使おうと思います。

ICPC 2023 Asia Yokohama Regionalに参加しました。とても貴重かつ楽しい経験をさせていただきました。大会に関わったすべての人に感謝を申させていただきます。ありがとうございました。

自分が作題に関わったHUPC2023*1や、自分が在籍している大学で開催されるパソコン甲子園などの参加記を読むのが存外楽しく、(大会・イベント運営に関わった皆さんへの恩返しも兼ねて)今回自分も参加記を書いてみようと思いました。本当はJAG2023夏合宿の参加記も書く予定でしたが、day3のコンテストの成績があまりにも酷く、萎えてしまったので書きませんでした。参加記というより日記・行動記録を細かくしましたみたいな文章になってしまいましたが、お付き合いいただけると幸いです。

day1

移動

睡眠周期が崩壊してしまい、睡眠に失敗、徹夜。8時にチームメイトと合流。電車->新幹線と乗り継いで東京駅に向かう。脳内で https://onlinejudge.u-aizu.ac.jp/problems/2237 と https://onlinejudge.u-aizu.ac.jp/problems/2642 を考察しました。前者は解けたつもりになり(bitDPがうんたら....)、後者は O(N^{2}) から落とせませんでした。新幹線で隣の席の人が在籍している大学の教授らしき人だったのですが、確証がつかめないの&コミュ障&単純にマナーに欠けた怖いムーブをしていたので関わりたくないのトリプルコンボで挨拶は控えました。

東京駅->横浜駅->日本大通り駅と移動します。乗り換えが大変。人が沢山いて息苦しい。来年の自分、もしくは後輩へのメッセージも兼ねて移動方法を残しておきます。

東京駅からは東海道線というものに乗ります。9・10番ホームで薄いオレンジ色の円が目印です。同名の新幹線もありますが、そっちは違うらしい。

  • 横浜駅と新横浜駅は違う駅らしいです。新横浜駅へ誘導する競プロerがいたら闇討ちを図っている可能性があります(?)

横浜駅からはみなとみらい線というものに乗り日本大通り駅へ向かいます。運賃230円。とりあえず横浜駅から地下の方へ向かうとみなとみらい線があります。横浜ベイスターズの野球選手が壁紙となっているエスカレータが特徴的でした(来年もあるかな？)

移動中の電車で酔ってしまった。酔い止めを事前に飲んでおいたが、睡眠不足は乗り物と相性が悪い。川崎から横浜までが長くて長くて苦しかった。

昼ご飯はファミマですませた。サンドイッチ。公園で大道芸を眺めながらいただきました。始めて大道芸を生で見たのですが、水晶は重力を無視する凄い物体であることを知りました。高校の物理の先生はそんなこと教えてくれなかった....。

受付・リハーサル・チーム自己紹介

こっから英語でのコミュニケーションが始まりました。聞かれたことに名詞1語で答える。意思表示はMay I ....でok。相手も日本人だから多少英語で下手こいても大丈夫なはず。モニターから流れている。ICPCのムービーではtouristがちらっと出演しているのが見えました。JetBrainの広告が心臓に悪い*2。

私達のチームは角に割り当てられました。換気口やドアに近く、そこから風が入り込んでくるのがちょっと寒い。チームメイトの一人は「運営席にめちゃくちゃ近くて見られている感が気になる」とぼやいていました。実際本番になるとそれは全く気にならなかったので良かったです(めっちゃ集中できた)。右と後ろのチームが強豪で肩身が狭い。

憧れだったICPCTシャツを着ました。モチベーション爆上がり

後でホテルで撮った

リハーサルでは普段の練習環境との違いやDOMjudgeの仕様を確認しました。

  • どのくらいコンパイル時計算をしたらCEになるか
  • 再帰の深さの上限はどのくらいか
  • コンパイルオプションはどのようなものが使えるか

特に普段の練習環境との違いについて

  • C++20が使える(これは元々公開されていた情報ですが)
  • 実行時エラーの原因特定に役立つコンパイルオプションが利用できる

が分かったのが大きかったです。本番でもウキウキでstd::set<T>::containsを使いました。

リハーサルの後半は時間が余ったのでタイピングの練習に当てました。自分はmod素数下での二項係数のライブラリの写経をしてみました。10分くらいかかりました。やっぱり始めてのキーボードだと時間がかかりますね。写経の時にライブラリの書かれた紙をディスプレイの上に置いて首を動かさず写経していたのですが、これが結構グレーな行為だったらしく、リハーサル終了後禁止になってしまいました。チームメイト曰く僕がそれをしている時に隣で運営がこれってアウトじゃねみたいな審議していたようです。 後ろのAMATSUKAZEチームも同じことをしていたらしい。A列大丈夫か.....?

チーム自己紹介は初っ端でした。特に一芸を考えていなかったので、秒文章を考えて、deeplに翻訳を映しながらそれを読み上げました。声がマイクに入ってなかったかもしれない。

  • Luzhiledを尊敬しています
  • Luzhiledを倒して俺達が真のLuzhiledになります

と言いました。来年はLuzhiledに頼らずともキャラが立つ3人でありたいね。

夜

ホテルに移動 *3。夕食はバーガーキングでテイクアウトを取りました。ホテルの自室で食事。サイドメニューのシーザーサラダにフォークの類がついておらず、コンビニに行って箸を買う気力も無かったのでインド式食事をリスペクトしました。汚い。

移動中にみつけた、うっとりと書かれた広告。何がうっとりなんだろう

横浜までの移動で考察した問題を実装しました。サンプルが全然揃わない。考察が思いっきり間違っていることに気づく。あんまり粘着すると今日ABCを休む意味が無くなるので、そうそうに切り上げました。

21:00時に就寝

Day2

朝

4:40に起床。身支度を軽く進めてから頭の体操をする。

前々から https://onlinejudge.u-aizu.ac.jp/problems/1612 の実装を進めていて、この時も良いアイデアが思いついたので実装。サンプルが合わない。２つの重なっている立方体がお互いに隠している表面積の合計を求めるパートが上手く計算できない。そこがうまくできればACを取れると確信しているが....。CEを投げて今回も放置。

昨日解けなかった問題を再考察。どこが間違っているのかを言語化する所まではできたが、直そうとすると計算量が悪化してしまう。改善方法を考えていると6:30になっており、身支度の続きをすることにした。

朝食はまたファミマ。お腹が空いていたのでがっつり親子丼とサラダを食べました。

移動。

  • ABC330のdifficultyを確認しました。F問題が青diff。気になるが、後でまとめて走ることにして今は問題を開かないことにした。
  • 自分の本大会での目標を再確認
    • プレイ面: イライラしない。チームの空気を良くする。一問以上考察で貢献する
    • 成績面: 夏合宿で同部屋だった人達のチームに勝つ。ところで夏合宿で同部屋だった人達のチーム名がわかりません。困った。

8:40分あたりにregisterを済ませる。チームメイトと雑談したり初手の戦略の確認などをした。

チームについて

LuzhiledFanClub

Luzhiledの後輩三人組

zawatin: 僕。AtC青。考察が下手くそだが、それをカバーするように実装や問題文読解を担当し、チームに貢献しているように二人を錯覚させるのが得意

Abeshi: AtC青。チーム唯一のYokohama経験者。普段は構築、パズルを担当。国内予選は彼にキャリーしてもらった。

nono00: AtC青。構文解析の鬼。僕の迷走を止めてくれる。vimの扱いに長けている

aizu_d

国内予選でaizu_a枠である私達とaizu_b(japanese_goblin), aizu_c(aizu_ubic)を倒し逆転、大学一位枠を獲得したドラマのあるチーム。去年はei13333333333333というチーム名でICPC Yokohamaに参加していたようです。

コンテスト

入場してからの行動はメモをとっておらず記憶から引っ張りだしたものを書き連ねています(携帯の電源を切っていたため)。うろ覚えの所も多く、立ち回りなどもしかしたら違ったかもしれないです。

以後は問題のネタバレを多々含みます。

nono君がPCのセットアップをしている間にA問題を読みます。　

dfsをすれば良さそうです。サンプル1が8になる理由がわからない。

とりあえず読解にミスがあったとしても修正が簡単そうなので実装を開始。nono君にサンプル1の解が8になる理由を考えてもらいました。

実装が終了。サンプルが揃う。サンプル1の解が8になる理由を聞き、読解にミスはなさそうなのを確認

提出-> AC(0:10)

一番最易と評価されているA問題でさえABC-DE程度の難易度があったので、今後の問題に戦っていけるか不安になりました。

他に解かれている問題が無いか順位表を確認(ありませんでした)。10位くらいだったので、そこそこ早解きできたんだなと安堵。

nono「Dが構文解析っぽそう😀」

Abeshi「B考えています」

K問題を読みます。

最近幾何を集中的に対策していたので、ちょっと考えてみる。

ぱっとはわからない。1024とインタラクティブが二分探索を連想させるが、そんな単純でも無いだろう。

円と線分の関係について以下の5通りがある

  • 円と線分がまったく交差しない
  • 円が線分を内包している
  • 線分が円を貫通している
  • 円が線分のちょうど片方を内包している(x 2)

円の上にのっている線分の長さの情報だけでは上1つ以外は判別できない。よくわからないなぁ

nono「D構文解析では無かった😢FでACが出ているので読みます」

Abeshi「B考えています」

J問題を読みます。

ぱっとは何も思い浮かばない。パスの場合で解けるならHLDをすれば良さそう -> パスでもわからんが.....

I問題を読みます

不可能枠乙。マジで何もわからん。

ぼく1「水って書いてあるしフローやろ」

ぼく2「どう流すねんカス」

Abeshi「Bで遅延セグ木がほしいです」

Bの問題概要を軽く聞く。

ぼく(本音) (こんな序盤から遅延セグ木生やす作業するのいやだなぁ)

ぼく「とりあえずもうちょっと考察詰めてほしいかも」*4

nono「現時点で結構ACでているし、遅延セグ木が必要になるとは思えない」

ぼく(本音) (ナイス同調)

H問題を読みます

ぼく１「Assignmentって書いてあるしフローやろ」

ぼく２「二人に分けるってのがなんかフローくさい」

でも結局具体的なsomethingは何も得られそうに無い。これもパス

Abeshi「B遅延セグ木無しで解けそう」

nono「解法聞きました。大丈夫そうです。複雑じゃないのでzawa君実装お願いします。僕はFをやります。」

ぼく「了解です」

Abeshi君から何を実装してほしいか聞くが、何もわからんかった。

ぼく「わかんね〜😭」

nono「じゃあ僕やります」

無能故暇になった。

nono君が後ちょっとでFを詰めきれるとのことで、解法共有の時に備えてFの問題文を読むことにした

わかんね〜。盤面全部状態として持ってないとできないように見えるが、うまく反転回数だけで O(1) とかで差分を計算できたりするのだろうか

D問題でACが出ているのを確認。nono君がすでに読んでいるので丁寧には読まない

区間dpとかでできそう。繰り返しはローリングハッシュとかを用いれば良いだろうか

G問題を読みます。

Abeshi君とかが得意そう。一回の操作で少なくとも \lfloor \frac{1}{6}N \rfloor 枚減少することは分かっており、かなり少ない操作回数で残り1枚になることが予想できる。今まで読んだ中ではかなり解きやすそうな問題に感じた。

nono君とAbeshi君が必死にBを頑張っている。僕はDの考察に戻ることにした

文字列の長さが小さいので、ローリングハッシュを使わず愚直に繰り返しにできるか判定すれば良いと考えた。区間dpを考えて

  • ２つの独立な区間に分け、それぞれをいい感じに折りたたんで最小化したものを連結する
  • 区間全部を(できるなら)繰り返し表現にして、繰り返し表現の中身を最小化する
  • 何も変更しない

の3通りを考えれば良さそうだ。問題文をもう一回眺めて、繰り返し回数が9回までしか許容されていないことを知る。計算量も大丈夫。とりあえず解けたということにする。dpの復元がちょっと苦手なので実装時間の見積もりは長めにとった

ぼく「D解けました。20分くらいでできそう」

nono「Bバグらせているので変わっても良いですよ」

Dの解法をnono君に軽く共有し、実装を開始する

Bの実装と並列していて、PCに触れない時間があった。その間にC問題を読む

回転して一致するものは同型！みたいなやつはポリアの数え上げ定理を用いるのだろう。名前しか知らん。困ったな。

D問題の実装を終えるが、サンプルに対してSegmentation Fault、かなり小さい文字列を入力に与えても実行時エラー。printデバッグしたりして色々修正したりするが全然実行時エラーが取れない。困った。

すごく不快な気分になってしまい、明確にイライラしてしまう。2人、すみませんでした........

Bのサンプルが揃う -> 投げる -> WA

nono「WAの理由わからん、B一旦捨てませんか？」

Abeshi「正当性の証明はできたつもりなんだけど」

ぼく「正当性証明できているならもうちょっと粘ってほしいな」 <- スーパー自画自賛になるが、この発言がかなりナイスだった

nono「じゃあAbeshi君にお願いします。ぼくはF行きます」

D問題のデバッグが全然終わらない。苦しい。要求されていることはシンプルなのに、上手くできない自分への苛立ちが止まらない。一旦全部書き直したいという気持ちになる。

Abeshi「Bの実装ミス見つけました」

修正-> submit -> AC(1:31)

ありがとう。僕もこれに続いてDを倒さなければいけないとプレッシャーを感じる

Abeshi君にGIKのどれかをやると良いと伝えた。順位表も考慮して、Kを選択したようだ。概要だけ渡す

ちょうどnono君もFが解けたらしい。実装想定時間が短いので、解法の共有はせずにDと並列することにする。

Dは全部書き直すことにした。

Dを5分くらいで全部書き直す。またバグる。絶望。ここで交代した時点でFの実装が終わる

F投げる -> WA

ドンマイや... 3人揃って苦しい時間が連続している

Dがようやくバグが取れる(書き直したほうがバグが取りやすかった。それはそうか) -> そのままサンプルと自分で作ったケースが揃う

D投げる -> AC(2:17)

ノーペナと言いたい所だが、デバッグで1~2ペナ分はかけてしまっている。嬉しさや安堵よりも2人への申し訳無さを感じていた。

Abeshi君がKの解法を建てつつあるようだ。早すぎる。流石。「三分探索の強化版みたいなやつ書けますか？」みたいな質問が来た。多分黄金分割探索のことだろうが、書いたことは無いと返答した。nono君も書いたことが無いようだ。

FのWAを解消することを最優先として、nono君から解法を聞く。差分の計算が O(1)でわかるらしい。自分が噛み砕いて理解するのは非常に時間がかかるので*5 とりあえずコーナーっぽそうな N = 1は大丈夫かと聞いてみる。nono君が「ｱｯw」とか言いながら N = 1のケースを実行してみると出力が「1 -> 2 -> 3 -> 4 -> ....」ってなってて草生えた。

そこだけ直してresub -> AC(2:27)

実装キューを消化しきったので、3人揃って昼ご飯休憩を取ることにした。普段は散歩とかするが、今回は禁止されている。豚カツが美味しい！

自分が読んだ問題を2人に共有、Abeshi君はKを続投して僕とnono君がどうするかを話しあった。

順位表と問題の見た目などから、 EとGをやることにした。

E問題を読みます。Eだけたまたま読んでなかった。

Nが小さい上にTLが超長い。集合を全部なめる何か目をつけながら考察をしてみる。

問題を読み切ったあたりでAbeshi君がKの考察を詰めきったようだ。nono君が相談・実装に着手する

ジャガビー、ラムネ、メロンパン、明太子おにぎりを喰らいながら考察を進める

M = 1の時は 2\times \binom{N}{3} \times (N - 3)! が解になることがわかる。 M \ge 2の時でもそのように二項係数などでの計算に帰着すると予想をした。

まずは包除原理を考えてみた。全ての条件を満たす -> 少なくとも一つの条件に違反したらout

ウンウン考えた後、ふと冷静になって M \in O(N^{3}) であるから包除原理を適用するのはあまり得策でないと結論づける。

箱根駅伝dpなどに思いを馳せる。これもよくわからない。

知っているテクニックを全探索をするのをやめたいと考え*6、愚直解を立てようと思い至った。bitDPで O(M\times 2^{N})でできることを確認する。

これは明らかにTLEするが、 M が大きい時に解がどのようになるかを考えた。サンプル2のように (a, b, c)と (b, a, c)が両立していたら解は必ず0になる。そのような「両立していたら解が0になるペア」が発生しないように条件の集合を構築した時、その最大サイズはいくつになるだろうか

両端を固定して残り22個を bとして指定する -> 両端を固定してまた20個 bとして指定する -> ..... とするのが最大で、これが 22 + 20 + 18 + 16 + .... + 2 = 136 だ！ (後でも触れますがこれは嘘です)

だからこういう自明に解が0になる条件のペアを検出して、そのようなペアが無い場合にのみbitDPすれば o(N^{2} \times 2^{N}) になると結論づけた。これをAbeshi君に共有。賛同を得たので実装に入る(K問題と並列になる)

10分かからず書き終わるが、サンプルが揃わない。その間にKがテストランナーを通過したので提出 -> RE (おそらくassert(query_time <= 1024))

解法をもう一度確認するとのことで、コードを印刷してEのデバッグに着手

デバッグ中に考察の立式のミスを発見、考察結果自体に支障は無いが心配になる(考察自体は大嘘なんですけど....)

サンプルが揃う -> 投げる -> AC (4:03) *7

心配が全部吹き飛んで気持ちよくなる

その後すぐにKの改善コードがテストランナー通過

Ksub -> AC (4:05)

残り1時間、一問が限界だと判断し、全員つっぱでGに行くことにした。操作回数が最大何回になるのかを計算するコードを書いてほしいとnono君に頼まれる。書くと60回前後であることが分かった。

これは良い考察の手がかりだ。nono君とAbeshi君の議論が加速する。自分がいくつか嘘を言って*8二人に指摘されるということをしたので、自分はそうそうに考察から離脱してmodintを書くことにした。

modintを書き終わる頃には大まかな方針が決定していた。自分も再び考察に参加する。

結局以下のように結論づけて実装を開始した

  • 操作回数は60回程度
  • dp[i][j] : 残りi枚カードが存在して、残したいカードは左からj番目に存在する状態から操作を始めた時、残したいカードが残る確率
  • 一回の操作で iが \lfloor \frac{1}{6}i \rfloorか \lceil \frac{1}{6}i \rceil減少する。この差は高々1しか無い
  • だから、参照する iの数は少ない
  • 同様の議論で、参照する jの数も少ない
  • 計算回数が 60\times 60\times N程度で終わると見積もることができる

3人でGに着手して20分くらいでこの結論に到達したと思う。(特に考察が苦手な寒色にとっては)一人だったらこのスピードで考察は出せない。チーム戦の「考察時間は3倍」という魅力が発揮されていたと思う。

nono君とAbeshi君が後ろからつついてくれたのもあり、実装が早めに終わる。一個二個のデバッグでサンプルが揃った

  • mod素数の乗法逆元を \text{pow}(x, MOD - 2)では無く \text{mul}(x, MOD - 2)と書いていた。引退

最大ケースも割と早く終わることを確認。提出 -> TLE

ファイル書き出しで最大ケースを計測すると、6秒くらいかかっていることが分かった。考察はそのまま実装を改善すれば通ると判断

  • ラムダ再帰をやめて普通の再帰に書き直す
  • mapをunordered_mapにする
  • pair<int, int> をint * INF + intみたいなlong long型で表現することにする

これでもう一回最大ケースを試す -> 3秒

提出 -> AC(4:49)

3人でハイタッチを決める

残り10分はJを考察したり、コードを持ち帰り用のディレクトリに移したりした。Jが解けることも無く、タイムアップ

after contest

りあんさんの参加者表 https://riantkb.github.io/icpc_standing_colorizer/から横浜勢の実力帯を考えると、私達は最下位すらありえたので、かなりの大健闘と言えるでしょう。前向きな気持ちでコンテスト終了後は行動できた。

解説

B: 平均を整数で扱う典型があった。ひさしぶりに見た気もするしABCに最近でてた気もする

C: 直線が交差しないを括弧列に言い換えるの賢いなぁ。思いつきそうにない

E: 高速ゼータ変換が想定解。家でもう一度考え直すことにする

F: 簡単枠には見えないが....

G: Wolframが出てきた時は笑った。

H: フローということだけあってたらしい。

I: 天才か？有理数を(分母, 分子)として二次元平面にプロットするという発想が出そうに無い

J: 解説で O(N^{2})までは理解した。マトロイドには疎く....

K: これも天才だなぁ。結局三分探索は使わなかったらしい。通してくれたAbeshi君nono君に感謝

YesNo (順位表確定)

  • 3Yesを獲得して16チーム抜きました。いえい。

  • 後1チーム抜いてれば企業賞だったようです。自分のDの実装がもっと早ければ......

  • 複数チーム出場していた大学もありますが、特に東大・東工大・京都・早稲田大学にはどのチームにも負けました。上位勢との実力差を痛感。

  • aizu_dに勝ちました。これで自信もってa枠を名乗れます(?)

懇親会

乗り物酔いを憂いて少し抑えめに食べた。魚介類(あさり、えび)を久しぶりに食べた。幸せや。

コミュ障が酷くて他大学の人とはしゃべることができなかった。せめて夏合宿同部屋の人たちに挨拶しようとも思ったが、会話自体への不安が募り断念

Iの解法について、典型だったりするのか、どういう考察を経ると解法にたどり着けるのか暖色の人に聞こうと思っていたが、それも断念した。Twitterアイコンぶら下げている人もいたりしてフレンドリーっぽそうな人もいたなかで勇気が出せなかったのは反省

KLabさんから技術同人誌を頂いた。まだ読んでいない。期末試験終わったら読ませていただきます。

帰り

一番長かったのが郡山->会津の電車の出発時間を待つでさすがにげんなりしてしまった。

移動中にEを考えていたが、自分の考察の誤りに気づいた。一個順列を定めてそこから \binom{N}{3}個の条件を抜き出すことができる。これは明らかに解が0では無い。よって M \in O(N^{3})でかつ自明に解が0でない条件の集合が存在する。

反省

実装担当なのにDの実装に時間をかけすぎてしまった。どうすればこういうのを無くせるのだろう。

Dのバグ取りでイライラ＆ヘラヘラしてしまった。序盤のチームの空気を悪くしてしまった。

大きなタイムロスになりるうかつな提案をいくつか考えなしにしてしまった。今回は運が良かったのもありタイムロスになることはおそらく無かった。

Gはチーム戦の醍醐味が出たと思う。3人で考えたラスト1時間は本当に楽しかった。

結果には普通に満足している。来年はもっと良い結果をとらないといけないというプレッシャーもすでに感じている

???「来年は全員黄色で出られるといいね」

今後の展望

幾何・文字列・フロー・データ構造などの写経が絡み実装量が増えてしまうような分野を訓練していくつもりです。キーエンスコンの飛び賞賞金でコンピュータ・ジオメトリを購入しまして、今はそれを進めています。(第一章の演習問題が早速解けない。ﾀｽｹﾃｰ)。

  • 今回のコンテストだったら、Hの考察・実装、Jの実装を担当できるくらいには上達したい。

普段問題を開いて解く場所はAtCoder, CodeforcesよりAOJを優先しようかなと思っています。AOJ-ICPCを埋めるモチベが高いし、PCK、JOIの問題も解きたい。

数ヶ月後には興味が移り変わって全く違うことをしているかもしれませんが、少なくとも競プロはやっているといいな

来年ちゃんとICPCに打ち込めるよう、卒業研究や単位取得、は早めに.....

おわりに

長くなりました。ここまで読んでくれてありがとうございます。進路の違いなどもあってFanClubの3人で挑むICPCは来年でラストだと思います(なんなら今年がラストの可能性もある)

来年はもっと良い結果を残せるよう日々精進して参ります。繰り返しになりますが、大会の運営に関わった皆さん、同じContestantだった皆さん、チームメイトのnono君・Abeshi君。実質チームメイトのLuzhiled先輩。非常に貴重な経験をさせていただきました。ありがとうざいました。

*1:HUPC2023-day3 AFHL

*2:ﾀﾞﾝﾀﾞｶﾀﾞﾀﾞｶｶ ﾀﾞﾝﾀﾞｶﾀｶｶ ﾊﾟｶﾊﾟｶﾊﾟｶﾊﾟｶﾊﾟｶﾊﾟｶﾊﾟｶﾊﾟｶﾊﾟｶってパーカッションが急に爆音で鳴る

*3:電車に乗らないといけないくらい距離がある。憂鬱

*4:Bの想定がセグ木だったら大戦犯でした。雑にこう返答するの本当は良くなかったと反省している

*5:なんならB問題でそれをやらかしている

*6:問題の考察をせずにテクニックを総当りするのはABCでしか通用したためしが無いので

*7:考察がミスっているので O(N^{3} \times 2^{N})になっているのですが、なぜか通りました。気分で書いたif (dp[bit] == 0) continueがめっちゃいい感じに Mが大きい時に枝刈りしてくれたのかも

*8:残りカード枚数が5枚以下だと確率の計算に無限等比級数が出現するとか言った気がする