hogecoder

tsutaj 競技プログラミングの記録

TCO19 Round3A Med: WaitingForBusAgain

問題概要

原文 → TopCoder Statistics - Problem Statement

 N 種類のバスがあり、 i 番目のバスは  f_i 分おきに停留所に到着することがわかっている。

それぞれのバスについて、来る間隔だけはわかっているがどのタイミングからその間隔で来るかは一様にランダムである。より具体的に言えば、 i 番目のバスについてある一様乱数  x (0 \leq x \lt f_i) があって、時刻  x, x+f_i, x+2f_i, \ldots, x+kf_i ( k は整数) に停留所に到着する。これらの乱数はそれぞれのバスについて独立に定まる。

このとき、次に停留所に到着するバスのインデックスの期待値を求めよ。

解説

本番出たときは全くわからなかった。

Codeforces のブログに Writer が簡潔に解説を書いている ので、それの前半だけ読んでまたやってみた。

最も頻繁に来るもの、つまり  f_i が最も小さいものに着目し、これを  f_{\min} とする。バスは  f_{\min} 分以内に必ずなにか来るので、長さ  f_{\min} のスリットの中にバスがどのように来るかを考えればよい。

まず、各バスについて  f_{\min} 以内に到着する確率は  \frac{ f_{\min} }{ f_{i} } である。また、 f_{\min} 以内に到着するという条件のもとで考えたときに、( 0 \leq t \lt f_{\min} の範囲で) 時刻  t に来る確率がどのようになるかを考えたとき、これは  t の値によらず一様な確率を持つ。このことから、 f_{\min} 以内に到着するバスが  x 台存在するとき、そのうちのどれが最初に到着するかについて、すべて確率  \frac{1}{x} である。

これらを考察すると、 dp[i][j] :=  i 番目のバスまで見て、そのうち  j 台のバスが  f_{\min} 以内に到着するときの期待値 という DP ができる。期待値のテーブルと確率のテーブルを両方持つ必要がある。

ソースコード

struct WaitingForBusAgain {
    double expectedBus(vector<int> f) {
        int N = f.size();
        int mi = *min_element(f.begin(), f.end());

        vector< vector<double> > dp(N+1, vector<double>(N+1));
        vector< vector<double> > prob(N+1, vector<double>(N+1));
        prob[0][0] = 1.0;
        for(int i=0; i<N; i++) {
            double p = 1.0 * mi / f[i];
            for(int j=0; j<=i; j++) {
                if(prob[i][j] == 0) continue;
                
                // slit の中に入れる
                prob[i+1][j+1] += prob[i][j] * p;
                dp[i+1][j+1] += dp[i][j] * p * j / (j+1) + prob[i][j] * p * i / (j+1);

                // slit の中に入れない
                prob[i+1][j  ] += prob[i][j] * (1 - p);
                dp[i+1][j  ] += dp[i][j] * (1 - p);
            }
        }

        double ans = 0.0;
        for(int i=0; i<=N; i++) {
            ans += dp[N][i];
        }
        return ans;
    }
};

最初の言い換えがすべてな気はする、おもしろいね。

HUPC 2019 参加記

HUPC 開催の経緯

これまで自分が RUPC や ACPC などの他大学の競技プログラミング合宿に参加してきて、自分も合宿を主催して他大学の (特に北海道の) 競技プログラマと楽しみたいという思いがあって、開催することにしました。やると決めたからにはたくさん頑張ろうということで、実際いろいろ頑張りました。

実際に日程を決めるときはちょっとだけ難航しました。というのもすでに他の合宿やコンテストの予定が入っていたり、冬は交通機関の乱れが心配であったりと、なかなかいい日程がありませんでした。せめて 3 連休にできたらいいよねということで、7 月の 3 連休を取ることにしました *1

運営としてやったこと

4 月

まず先述の通り、開催するということと具体的な日程を決定しました。また当時 Twitter アカウントがなく広報するにあたって不便だったので、サークルの Twitter アカウントを作ることにしました。

Day1 は北大勢で作問することになっていたのですが、Day2 は有志で作問してくれる方を募集しなければならなかったので、募集しました。最終的に自分含め 5 人で作問してくれることになり、非常に心強かったです。作問してくれた 4 人 (drken, idsigma, tempura0224, tubuann) の皆さん、ありがとうございました。

5 月

会場の予約をしました。当初学内の教室などで開催できたら良いなと思っていたのですが、弊学はケチなので休日に教室を学生に貸し出していなかったので、外部の貸室を利用することにしました。後でまた書きますが、スポンサーのフィックスターズ様が会場費をサポートしてくださったので、大変助かりました。

会場が決定したので定員や懇親会会場を決定することができて、ATND を公開したり懇親会会場を仮予約したりしました *2

この時期にフィックスターズ様と連絡を取り、スポンサーとしての参加交渉を行いました。快諾してくださりありがとうございました。

6 月

会場は下見ができたので、プロジェクターの動作確認 *3 やネットワークの確認をしたりしました。

作問作業が本格化して、この解法は落としたいとかを考えて制約を変えたりなどの試行錯誤をしました。

7 月

ATND の登録を締め切って懇親会の人数を確定させました。あと懇親会後に AGC が入ったので時間をずらす必要があって、そのへんをお店に再度連絡しました。

直前になってお菓子や飲み物、ウエットティッシュなど必要なものを購入しました。この辺で仕事を分散しはじめていて、名札を rsk0315 君に作ってもらったり、買い出しをみんなでしたりしました。協力してくれてありがとう。

あとは受付表を作ったり会計をしたり問題文を印刷したりなど細かいことをいろいろやりました。

合宿当日の流れ

Day0

てんぷらくんが家に泊まりにきました。一緒にジンギスカンを食べました。

Day2 どれくらい解かれるかな〜、あんま解かれへんやろ〜、みたいな話をしてた気がする。

Day1

いろいろ荷物を運びながら会場に向かいました。あまりにも荷物が多かったのでてんぷらくんにお菓子と飲み物を持たせてしまってもうしわけない

会場とコンビニが近かったので飲み物を買い足したりとか、色々準備をしていたら受付の時間になって、続々と参加者が到着してきました。

最初に自己紹介とスポンサーセッションがあり、その後チーム分けをしてコンテストです。

北大セットでは A と G の Writer と F の原案魔改造、G の問題文、C・D・E・G のデータセット、全問題の Tester を担当しました。G は前々から出そうと思っていたテクだったので出せてよかったです。後で Twitter みたら参考にした論文の著者から言及されていてびっくりしました。

その後は懇親会でした。写真撮影を店員にお願いしたのですが、わざわざ扉を取り外して撮影してくれてサービス力を感じました。

Day2

コンテスト時間が早いので早起きします。ねむい

チーム分けをして、Day2 コンテスト開始です。序盤から ushitapunichiakun が爆速で問題を通していて荒らしか?とか言ってました (失礼)

Day1 より全体的に少し難しめかな、と想定したセットでしたが、最終的にオンサイト 1 位が 6 完でオンラインで全完が 2 チームあったので、かなりいい難易度バランスだったのかなと思いました。

ちなみに自分が Writer をした問題はセットのバランスの都合上なくなりました。Tester は全問題やりましたが、忙しすぎて AC 確認くらいしかできなくてすみませんでした・・・ (後半は他のスタッフに頼りっぱなしでした)

夕食はすしをたくさんたべました。

総括

おそらく前例のない、北海道での大学主催合宿を思い切ってやってみました。もちろん不安でした。人が十分に集まるかどうかもわからないし、最悪北大のオフ会みたいになるかもしれないと思っていました。

しかし終わってみれば総勢 35 人が参加してくださり、北大以外の北海道勢や道外の競技プログラマも多く参加してくれました。本当にありがとうございます。

準備は大変でしたが合宿当日はすごく楽しくて、あっという間に終わってしまいました。いろんな人に楽しかったと言ってもらえて嬉しかったです。

また問題セットも概ね好評という印象で、とても良かったです。同時に 2 つのセットを運営するのはかなり大変でしたが最終的になんとかなってよかったです。

来年には社会人になるので来年以降に合宿が開催されるかはわかりませんが、もし開催されてスケジュール的に行けそうならぜひ参加したいと思います。

さいごに、北海道でも競プロ合宿が開けることが証明できてよかったです。実際に合宿に来てくれた皆さん、オンラインで問題を解いてくれたみなさん、Day2 の問題セットを用意してくれた皆さん、スポンサーになってくださったフィックスターズ様、運営してくれた北大勢、その他合宿に関わってくれた方々に感謝して参加記のむすびといたします。

*1:これでも ICPC 国内予選が被りかけたので、そこは反省点です

*2:その時点では参加人数が確定していないので、適当にこれくらい来るかなあと見積もった人数で予約しました

*3:動作確認したんですが、当日は動かなかった・・・

ACM-ICPC 国内予選 2019

ICPC の国内予選に参加しました。今年も four-t として rsk0315, TAB, tsutaj のチームで出ました。

f:id:tsutaj:20190713015212p:plain

弊学からは 7 チーム出て、全チーム 3 完でした。昨年に引き続き今年も 2 チーム通過している見込みで、ひとまずは安心です。しかしもう少しがんばりたかったなあというのもあります・・・。

コンテスト

早解き芸人を担当しているので開始直後に A を読みます。というのは嘘で、問題文を見ずに include とか main とかを書いていて、印刷された問題文が来ないのをいいことに「問題概要読んで伝えて!」と rsk0315 君に頼みます。言われたとおりに実装したので結局一度も問題文を読まないまま書いてサンプルが合ってそのまま AC しました。チームプレーですね。

B は rsk0315 君が、C は TAB 君が考察と実装をしていたので、任せて D を読みます。dp[i 番目のカウンタまで見て][直前のカウンタの操作から j 回分借りてくる] := 操作回数最小 みたいな方針が立ちますが、まずサンプルが合いません。グダグダしてたら B と C が通っていました。

よく考えると D のサンプルを手で試し間違えていたので少し考察すると、とりあえずこうかなぁみたいなのが生えるので書くとサンプルが合いました。しかしテストケースは通りません。

ここからは実質何も出来ませんでした。j 回分借りてくるのは M 未満ではなく 2M 未満で考えたほうがいいのかなと思いつつ、それでも合わず。悔しかったです。

反省

序盤は特に反省することはありません。しいて言えば A の FA を 17 秒差で逃しました。

後ろの問題を時間かけてでもいいから通すくらいの実力が欲しくて、解説を見ずに粘り強く考えて通すみたいな練習をすべきなんですかね・・・ギリギリ通せるか通せないかくらいの問題をたくさんやりたいです。

何はともあれ次の大会に駒を進めることは出来たので、アジア地区までにもう少しがんばりたいと思います。