コンテスト中AC:A,B

A - Permutation Grid

nの制約上、実際に構築することはできません。
このことから、 $(r_i,c_i)$ の組みによって一意に定まるような法則性がありそうだと予測します。

白黒がどのように決定するか試して見ると、例えばn = 5では、

$R_5,C_5$ の行と列を全て黒で塗る
$R_1,C_1$ の行と列のまだ塗られていないマスを白で塗る
$R_4,C_4$ の行と列のまだ塗られていないマスを黒で塗る
$R_2,C_2$ の行と列のまだ塗られていないマスを白で塗る
$R_3,C_3$ の行と列のまだ塗られていないマスを黒で塗る

となります。
よく考えてみると、この決定順序は $R_i,C_i$ の順列の並び方によらず同じです。加えて、ある１つの順列で決定した塗り方について、行や列を交換して別の順列にしても条件を満たします。

よって、ある一例で色の塗り方を確認すれば十分です。

ここでは、 $R_i,C_i$ がそれぞれ昇順に並んでいるとして、n = 2〜6まで列挙してみます。
0が白、1が黒です。

01  001  0001  00001  000001
11  011  0011  00011  000011
    111  0111  00111  000111
         1111  01111  001111
               11111  011111
                      111111

こうすると、階段状に塗られることがわかります。
ここで、以下のような法則があると予想できます。

マス $(r_i,c_i)$ について、 $c_i \leq N-r_i$ ならそのマスは白、そうでなければ、黒

これがいずれのnについても成り立つことを数学的に証明はできませんでしたが、おそらく成り立つだろうという予測しました。実際、これでACしました。
提出コード

B - Shift and Reverse

2つの操作を突き詰めると、右または左への巡回シフトのみが可能です。
操作によって、昇順に並び替えることが可能という条件から、数列 $P=\lbrace p_1,p_2,\cdots ,p_n\rbrace$ は、

$\{ 1,2,\cdots ,n\}$
$\lbrace n,n-1,\cdots ,1\rbrace$

のいずれかをいくらか巡回シフトした数列だとわかります。
よって、最小な操作回数としてあり得るもの以下に限定されます。

Pが昇順の巡回シフトである場合
- 1が先頭に来るまで、先頭を末尾に移動する
- ひっくり返して、1が末尾にくるまで先頭を末尾に移動させる。そして、再度ひっくり返す
Pが降順の巡回シフトである場合
- ひっくり返して、1が先頭に来るまで先頭を末尾に移動させる
- 1が末尾に来るまで先頭を末尾に移動させてから、ひっくり返す

よって、Pが元々昇順であったか、降順であったかに応じて、上記の小さい方を出力すれば良いです。

昇順の判定は、最初に1があるインデックスをposとして、
$i = 0,1,\cdots N-1$ であるすべての $i$ ついて、
$p_{(pos+i)\ mod\ N} \lt p_{(pos+i+1)\ mod\ N}$ が成り立つかどうかで判定できます。