AtCoder Beginner Contest 020

 D問題、100点解答に2分足らず…。悔しすぎる。

結果

 300/401 48:43 80位相当


 開始時刻 2017/08/03 19:39:00 提出履歴

A: クイズ - AtCoder Beginner Contest 020 | AtCoder

 1:22(AC)
 {“ABC”, “chokudai”}みたいな配列を作って、Q-1でアクセスする。

B: 足し算 - AtCoder Beginner Contest 020 | AtCoder

 3:24(AC)
 10n倍だなんだと考えるのが面倒くさかったので、入力(数値)→変換(文字列)→結合→変換(数値)でいった。

C: 壁抜け - AtCoder Beginner Contest 020 | AtCoder

 48:43(AC)
 これは本当にABCのC問題なんですかね…。でも解けたのでよかった。
 xを適当にこれって決めると、あとはSとG間の最短経路長問題なので、ダイクストラ法かなんか使ってxが条件を満たすかどうかは判定できる。
 で、xがある閾値X以下ならば常に成り立つし、逆にXより大きければ成り立たないのはほぼ自明。ということで二分探索でxを決めていく。こうすると10*10格子グラフのダイクストラlogT(T=109で30)回で答えが出るので、十分高速に解が出せる。

D: LCM Rush - AtCoder Beginner Contest 020 | AtCoder

 86:14(WA)108:02(WA)110:07(WA)112:29(WA)118:04(WA)
 (→120:32(WA)121:11(WA, 100/101))
 本当に悔しい。あと2分…。
 とりあえずmod Kで場合分けして表を書くと上手くいきそうだったので、まずは適当に列挙する。例えば、K=6で列挙すると、下の表みたいになる。便宜上、0は6にしてます。

m(mod 6) +0 +6 +12 +18 公差 gcd(m, K)
1 6 42 78 114 36 1
2 6 24 42 60 18 2
3 6 18 30 42 12 3
4 12 30 48 66 18 2
5 30 66 102 138 36 1
6 6 12 18 24 6 6

 ついでに答えまで書いてしまったようなものだけど、要はmodで場合分けするといい性質が見えてくる。m(mod 6)とすれば、初項は単純にLCM(m,K)を計算、交差はK2/GCD(m,K)、項数は(N-m)/K+1で求められる(ちなみに、交差がK2/GCD(m,K)なのはLCM(i,K)がi*K/GCD(i,K)だから当然といえば当然)。こうなると、各modに対してその和を出すのはすごく簡単。(初項+末項)*項数/2で求められる。あとは各modに対してその総和を計算して足せばAC!…のはずだった。
 なぜかWAが出るので色々試した。例えばオーバーフローが起きてるんじゃないかと思って、MODを細分化したり、割り算をするのが怖いので2の逆元をかけたり。実際はそのどれでもなかった。
 WAの原因はN-m<0の時の処理。このままやると初項が存在しない時の処理が疎かなので、そこをどうにかする。簡単に、N-m<0の時は処理をスキップすればいい。こんな簡単なミスで落とすと本当に悔しいなぁ。
 多分だけど、101点回答はKの約数に対してだけ処理をすればいいんだと思う。だけどこっちはどうすればいいのかよくわからないのでパスで。多分包除原理とか使う。

感想

 悔しい結果だったけど、でも手応えは感じた。着実に解ける問題を増やしていきたい。特に、同じミスはしたくないね。