Codechef SnackDown 2019 Round 1A

@bknshnと組んで出ました。後半3問を担当しました。

Dが難しかったのでE, Fを先に書きます。

E - Chef and Periodic Sequence

https://www.codechef.com/SNCK1A19/problems/PERIODIC

もともとこれがFでしたよねー、いつの間にか順番が変わっていました。明らかにFより簡単だったのでびっくりしてました。

まあ、数字が一つでもあると、1のインデックス(負としてもよい)が決まります。そうすると、1のインデックスの間隔は周期の倍数になるはずなので、 1のインデックス同士の間隔のGCDを取ります(1のインデックスが一つしかない場合は周期infで大丈夫)。これが最大周期です。あとは、順に見ていって矛盾してないかをチェックすればおkです。

F - Chefland and Average Distance

https://www.codechef.com/SNCK1A19/problems/AVGMAT/

マンハッタン距離を見たら45度回すのは基本ですね〜と言って回します。そうすると、各1について、そこからマンハッタン距離がdの1の個数は、 [x-d, x+d], [y-d, y+d]の正方形の辺上の1の個数です。これは、行と列について1の数の累積和を事前にとっておくとO(1)で求まります。よって計算量はO(NM(N+M))です。

まあ、しかし定数倍がけっこう重い(45度回転させるときに600x600を確保する必要がある)ので、わりとギリギリでした。まあ、回転後に明らかにもとのグリッドを含まない領域の計算を 飛ばすとかなりの定数倍改善になるかもしれませんが、実装難易度はめちゃめちゃ上がると思います。

D - Chef and Strange Addition

https://www.codechef.com/SNCK1A19/problems/CHEFADD

部分点解法としては、popcount(a) bit立っているc以下の数をすべて列挙して、チェックすればいいです。

満点解法はDPっぽいです。

f:id:xuzijian629:20181022131554p:plain