第17回日本情報オリンピック　予選２

2017年12月11日
情報オリンピック日本委員会

解説

すべての0が書かれているマスに止まるようなコマの進み方は，ゲームクリアするサイコロの目の出方のうち出目の最大値が最小になるもののひとつである． このとき，出目の最大値は，1の書かれているマスが最大でk個連続しているとすると，k+1である．これがJOI 君が購入すべきサイコロの面の数である．

kを求めるのは，O(N^2)個の区間それぞれについて，0が書かれているマスが含まれているかを高々O(N)で判定することでO(N^3)でできる． A_0=0, A_(N+1)=0として，A_i=0となるiを小さい順にならべたとき，隣接する二つの差の最大値がkであることに注意すると，O(N)でkを求めることもできる．