aizuzia

[UVa] The first contest of the new season

ICPC

nobが引退して、yukも用事があって来られないというので、全く新しいチーム編成で出てみました。
今日のチームメイトは後輩Mと後輩K。コンテスト名からしてきっとそんなに難しくないだろうし、教育しながらのんびりやりますか、と。

以下参加記録。

開始

問題文の印刷に手間取ってしまった。とりあえず読もう。
瞬殺できそうなのが見つからない。Statistics見てみよう・・・Dか。

Problem D: No Problem!

簡単だ。
とりあえず後輩2人に説明。後輩Kに書いてもらおう。
すぐ出来た。問題文の読み落としとかは無いか？
終了条件は -1 ではなく負の数だ。修正。
Submit。つつがなくAccepted。

他の問題をいろいろ読んでみる。
Hは偏角の小さい順につないでいけばいいのかな？でもコーナーケースがいろいろありそうで厄介だ。
さっき解いたDを除くと、解かれてる問題はEぐらいしかない。こっち考えよう。

Problem E: Teams

N人の中から何人か選び、さらにその中からキャプテンを1人選んでチームにする。何通りのチームが出来るか？
何人か選ぶ組み合わせは 2^N 通り。そこにキャプテンを選ぶ組み合わせが掛かる。
「コンビネーションですよね」と後輩K。そのとーり。
Nは 10^9 。パスカルの三角形とか書いてらんない。どうしよう。
解いてる人は結構多い。そんなに難しくないはず。
・・・。

発想の逆転。まずキャプテンを選んで、そこに適当に何人かくっつけてチームを作ろう。
キャプテンの選び方が N 通り。そこに N-1 人の中から適当に選んでくっつける組み合わせを掛ける。
N * 2^(N-1)だ。簡単だ。Sampleも合った。

実装は後輩Mにやらせてみよう。
a^N を O(logN) で計算する方法を後ろから教えつつトリオプログラミング。
出来た。Submit。Accepted。

次に解かれているのはAかF。
Aは一応思いついたけど、O(N^3 * K)なので間違いなくTLEだ。せめて K を log(K) にしないと。
・・・うまくいかない。Fいってみよう。

Problem F: Reverse Prime

Reverse Primeを普通に全列挙して素因数の個数を数えて、あとはなんとかTreeでどうにかするっぽい。
なんとかTreeって何だよ。Union-find Treeしか持ってないよ。
・・・ひらめいた。どうにかなりそうだ。
これは後輩に書かせるにはちょっとしんどいかな。自分で書こう。

「素因数の個数を数える」ってどこかで見たことがある。UVaの884だ。
エラトステネスの篩をちょっと改良すると 1 から N までの約数の個数が一気に求まる。
884のランキングを見るに、私のプログラムは十分早いはず。アレはちょっと汚い手を使ったけど。

前処理だけで手元の環境で6秒。TLは1秒。これはちょっとキツくないか？
とりあえず20分犠牲にして送ってみよう。・・・TLEだ！
・・・もしかして普通に素数で割ってった方が速いのか？
・・・3秒。速いよ。送ってみたら待望のWA！
でも0.5秒も使ってる。大丈夫だろうか・・・。まぁいいや、続き書いちゃえ。

Reverse Primeの総数はおよそ 80,000個。これを頭から $\sqrt{80000}$ 個・・・300個でいいや、ずつ区切ってグループ分けする。
各グループごとに残っているReverse Primeの数と素因数の個数の総和を管理しておく。O(sqrt(n))。

ソースコードがどんどん汚くなっていく。後輩の顔が引きつる。
Sample出てきた。Submit。これデバッグしたくないなぁ・・・。
一発(3回目だけど)Accepted。よかったよかった。

次はAかな？
結構重い問題セットだ。後輩にはちょっと厳しい。

Problem A: Lights inside a 3D Grid

ライト一つ一つについて点灯する確率を求めて全部足す。
1回の操作で反転する確率は式を立てて適当に求めるとして、K回の操作後に点灯している確率はどう求めようか。
DPだとまず間に合わない。せめて log(K) でないと。
「困ったらグラフに落とせ」って偉い人が言ってたので落としてみる。わかった。あからさまに遷移行列作って K 乗ですねこれ。
後輩に説明しつつも自分で書く。

できた。けど答えが合わない。
後輩フル稼働で行列のあたりをチェック。ごろごろバグが出てきたので片っ端からつぶす。
でもまだ合わない。

・・・もしかして1回の操作で反転する確率が間違ってる？
式を立てずにループ回して数えてみよう。
Sample出てきた！こっちが間違ってる。確かにこの式じゃ求まらないよね。
適当に式を立てまくってみる。うまくいかない。

自分の計算力の無さに絶望し始める。nobカムバック。
後輩と共に頑張るも、結局解けず終了。3問。残念。

後輩Mとコーチと一緒にラーメン食って帰ってきました。