AtCoder Beginner Contest (ABC) 090 / AtCoder Regular Contest (ARC) 091 レビュー
AtCoder Beginner Contest (ABC) 090 / AtCoder Regular Contest (ARC) 091 の個人的解法解説とレビューです。
今回はABC/ARCのC問題＆D問題のみとなります。
問題はこちらのAtCoder公式からどうぞ。
C - Flip,Flip, and Flip......
とりあえず解いてみる
最大のカード枚数は10^18。全部シミュレートしてると間に合わない。
実際に操作してみる。
カードの置かれているマスの四隅は4回操作される。最終的には表になる。
カードの置かれているマスの辺上（四隅を除く）は6回操作される。最終的には表になりる。
その他のマスは9回操作される。最終的には裏になる。
ということで、カードの枚数-辺上（四隅含む）にあるカードの枚数、つまりN*M-(2*N+2*M-4)を出力すれば良さげ。
……ほんとかな？
カード1枚だけ、つまりN=1 && M=1の状況だとどうなるだろうか。「四隅」「辺」が定義されないので、答えが変わってきそうな気がする。同様に、N=1 && M≠1の場合も「四隅」が定義されないのでマズそう。
コーナーケースがありそうなので、順に調べていく。
N=1 && M=1 のとき(「四隅」「辺」の定義が不可能)
1回操作されるので、1枚だけ裏になる。上記の式に当てはめてみると……そのまま使えそう。
N=1 || M≠1 のとき(「四隅」の定義が不可能)
端の2枚は2回操作される。最終的には表。
その他は3回操作される。最終的には裏。
つまり、M-2を出力すれば良い。上の式に当てはめてみると……1*M-(2*1+2*M-4)=-M+2になってしまう。
修正する
コーナーケースがあるので、以下のように修正。
if(N==1 && M!=1){ //コーナーケース
cout<<M-2<<endl;
}else{
cout<<N*M-2*N-2*M+$<<endl;
}
自分のソースコードだと無駄な条件分岐が……。
こんな感じで解けた。計算量はO(1)。
D - Remainder Reminder
とりあえず解いてみる
愚直解は「1<=a,b<=Nを満たす組(a,b)に対して、a%b>=Kであるかを確かめる」と言った感じだろうか。計算量はO(N^2)。Nは最大10^5なので間に合わない。
せめてO(N)ぐらいには落としたいところ。ということで、「組の一方の値が与えられたとき
、有り得るもう一方の値の個数をO(1)で求める」アルゴリズムを作ってみる(これなら、「与える一方の値」を1からNまで動かして和を取ることでO(1*N)で解ける)。
計算量を削っていこう
bを「与える」と上手く行ったので解説。
表は、N=10の設定で「aをbで割った余り」を示している。余りがK=2以上のところには色が塗ってある。
値には、長さbの周期が見られることが分かる（表の赤線を参照）。
また、b>Kを満たすbについてのみ考えれば良いことが分かる。
表の中で「周期」がいくつ見られるかを「sequence」に記載した。この値はマス数/周期の長さ、すなわち(1+N)/bで求められる。
「周期」に含まれるマスの中で、余りがK以上のマスがいくつ有るかを「sequenceによるanswer」とした。この値はsequenceの値*一周期に存在する余りK以上のマスの数、すなわちsequence*(b-K)で求められる。
また、「周期」に含まれないマスの中で、余りがK以上のマスがいくつ有るかを「remain」とした。この値は周期に含まれないマスの数-K、すなわち(1+N-sequence*b)-Kで求められる（負数になることがあるので、その場合は0扱い）。
以上の計算をすることで、「bの値が与えられたとき
、有り得るaの値の個数をO(1)で求める」ことができた。bをK+1からNまで動かして和をとれば、O(N)で解ける。
K=0のときがコーナーケース。この場合はN*Nを出力しておく。
まとめ
考察回&コーナーケース回避回だったなぁという印象。1WA吐きましたが、50分で二問解けました。
よっしゃよっしゃ
— Arc@競プロ (@arcslab123) March 11, 2018
rate 899->986(Highest)
perf 1453(Highest) pic.twitter.com/EiznrbLePT
最大パフォ更新。最近は調子がいい。
