Arc's Laboratory

プログラミングとかの研究室

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を「与える」と上手く行ったので解説。

f:id:arcslab:20180312160947p:plain
ARC091-D_解説

表は、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分で二問解けました。

最大パフォ更新。最近は調子がいい。