Codeforces #523 div2 C

問題

数列a1, a2, ..., anが与えられて、そこからいくつかの要素を、順序を変えずに取り出した数列b1, b2, ..., bkについて考える。k>1かつ、1 <= i <= kなる任意のbiがiで割り切れるようなものの個数を10e9+7で割った値を求めよ。
1 <= n <= 100,000
1 <= ai <= 1,000,000

Problem - C - Codeforces

解く

ぱっと思いつくのが
dp[n+1][n+1]
dp[i][0] = 1;
dp[i][j] = dp[i-1][j] (if ai % j != 0)
dp[i][j] = dp[i-1][j] + dp[i-1][j-1] (if ai % j == 0)
みたいなdpで、最後にdp[n]を1番目からn番目まで足せばいいんですが、愚直に実装するともちろん時間が足りません。

そこでvector <map<int, int>> dp(n+1)を作って約数として出てくる部分だけ考えようとする。iごとにaiの約数を調べ、大きい方から順に更新していく。が、MLE。

ここでようやくDPを1次元に落とせることに気づき、map<int, int> dpでやろうとするが、今度は更新の順番を間違えていることに気づく。(降順に更新するのはわかっていたけど、約数のペアを同じタイミングで更新していた。ちゃんとvectorに放り込んでソートしましょう)

やっと通ると思って投げると、今度はTLE。
よく考えたら脳死でmapを使うとaiの約数のうちnより大きなものまで更新してしまっている。O(105 * √106)でギリ間に合わないんだろうかとか思いながら、ちゃんとvector dp(n+1)になおしてAC

めっちゃ時間かかってしまった。

CODE THANKS FESTIVAL 2018 参加記

一回生からちょくちょく手を出してた競プロをこの夏から真面目にやったら、THANKSに参加できてしまった人の参加記です。
(6月時点のレートが609で、現在レート1340)

予選

ここ数年の参加記を眺めていると、年々枠が減ってるみたいですね。
予選の回数も減っていてかなしい、、、

qualA

解けまへん。
やはり地力不足で、2完でした。333位。

qualB

前日のAGCで晴れて水色になりました。

f:id:mdyh2a380824:20181120042056p:plain
その時の記録
モチベも上がり、気合十分な状態でのqualBですが、、、

Dを解いたのが9人(!?)で、予選が3完早解きコンテストと化す。
しかし、まだまだ未熟な僕にとってはこれが幸いしました。普通のコンテストだったらたぶんTHANKS参加できてなかったです。
40分ちょいで3完、190位。

通過確定、ほぼ確定の人をみて、いいなーと思いつつ賞賛をおくる。
この時点ではまだ予選落ちたと思ってました。(もともと来年に向けて経験しとくくらいの気持ちで参加していた。)

通過

上位で通った人の通過報告から数週間遅れてメールが届きました。
僕の10~20番くらい下だったれなすが落ちてたので、ほんとにボーダーギリギリの通過でした。(彼は遅刻してなければ、、、!と悔やんでいた。)
qualBの通過人数は本選40名、THANKS40名なので100人ちょい繰り上がってます。すごい。

前日

朝の新幹線に乗って東京へ向かう。
KMC勢と合流して晩飯を食べる予定だったが、3時頃にホテルについてベッドに横になった結果なんとそのまま6時間寝てしまった(各位ごめんなさい)
ちょっとだけ問題を解いて寝る。

当日

寝坊せずちゃんと起きる。
10時40分ごろに会場に着いた。いろいろ手続きをして席につく。
会場の後ろの方にはお菓子や飲み物がたくさんあった。
コンテストが始まる12:00まで知り合いと喋ったり配られた弁当を食べたりしながら時間をつぶす。

コンテスト

コンテスト開始!
※ネタバレ注意

まずA問題を解く。(1:39)
ほんとにやるだけと言った感じの問題。chokudaiさん曰くDPでも解けるらしい。

B問題は、10^9やけど間に合うやろ!って感じで投げるとACした(6:31)
655msなのでまあ余裕だった。

C問題。死亡。
ソートして差を取るとこまではすぐ思いついたけど、それぞれの区間が出て来る回数の処理をバグらせる。結局30:00にAC

D問題
しょーもない誤読をしてWAを生やす。すぐ気づいてAC(37:50)

悲しいかな、この時点で解ける問題がなくなる。この後何もわからず、2時間半地蔵になってしまった。(一応Fを解こうとはしていた)

終了後

結果は4完87位。うーん。
やはりオンサイトに進める人はレベルが高いなあと感じた。次はパーカー獲得を目標にします。
懇親会ではビンゴとコミュ力の融合ゲームがあり、人数の多い京都大学が圧勝していた。(zakiとamanoさんおめでとうございます)
僕もなんだかんだビンゴしてレポートパッドをもらいました。計算用紙おいしい!

懇親会終了後は京大の人たちとお寿司を食べに行きました。amanoさんが認知してくれていたのが驚きだった。

感想

結果はあまり良くなかったけど、やり始めて実質4ヶ月くらいなので出れただけでもよしとします。
今週末はHTTF本選なのでそっちは1ページ目にはいるぞ!