Codeforces Round #812 (Div. 2)

　Dまで四完。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round #812 (Div. 2) Dまで
B max(A[0]...A[x-1])>A[x]<max(A[x+1]...A[n])というxがあったらダメ
C 大きい方から決める
D 1～4の四人対戦は「? 1 3」を先に投げると二回で勝者が分かる。ただPyPyだと制限時間が厳しい。unratedだし他言語に書き換えたくないし、と投げてたらPyPy2で通った

— titia (@titia_til) August 6, 2022

E. Cross Swapping

　解説AC。面白い問題だったが、最初の一手にさえ気付いてなかったので、何も言えない。

　まず、

・A[i][j]はA[j][i]としか入れ替わらない

　と気付くのが重要。（コンテスト中散々実験したのに気付かなかったのはひどかった。何故……）

　だが、A[i][j]とA[j][i]を入れ替えたいとき、iとjのどちらを用いてswapすれば良いか分からない。また、入れ替えたくない時、iとj両方使わないのか、もしくは使うのかが分からない。

　これは、グラフの問題になる。

　左上から貪欲に、A[i][j]とA[j][i]の大小に従って、iとjでswapする/しないが一致する場合は0の、一致しない場合は1が書かれた辺を張っていく。そして、iとjがループしてしまいそうなときは、辺を張らないようにする。なぜなら、ループができたら結果が決まらなくなるため。左上から貪欲に決めているので、前に決めたことを優先した方が良い。

　こうして決めた後、木それぞれについてswapする、しないを割り振っていけばOK。