ABC225 参加記録 - geam1113’s diary

コンテスト中AC:A〜D

以下の3条件を満たす必要があります。

・最後の行を除くすべての数について、自分の下の数が、自分の数+7

・最後の列を除くすべての数について、自分の右隣の数が、自分の数+1

・すべての行について、要素の数を7で割った余りが{1, 2, 3, 4, 5, 6, 0}の連続する部分列と一致する

1,2番目は自明だと思うので、3番目の条件について説明します。

上二つの条件だけだと、以下のケースでもOK判定が出てしまいます。

B = {6, 7, 8, 9}

本来並ぶはずのない、8, 9が入ってきているためです。これを回避する手段が3番目の条件です。

Aの行はすべて7で割った余りが{1, 2, 3, 4, 5, 6, 0}となっており、これが満たされている必要があります。逆にこれが満たされていれば、本来並ぶはずのない数字が並んでいることはありません。上記のケースでは、7で割った余りは{6, 0, 1, 2}となります。

3番目の条件は、具体的には、 $B_{i,j} (1 \leq i \leq N,\ 1 \leq j \leq M-1)$ について、

(1) $1 \leq B_{i,j}\ mod\ 7\ \leq 5$ の時

$(B_{i,j}\ mod\ 7) + 1 = B_{i+1,j}\ mod\ 7$ ならOK

そうでないならNG

(2) $B_{i,j}\ mod\ 7 = 6$ の時

$B_{i+1,j}\ mod\ 7 = 0$ ならOK

そうでないならNG

(3) $B_{i,j}\ mod\ 7\ = 0$ の時

常にNG

となります。

3番目の条件が無くて4WAを出したので、公式解説のやり方の方が間違いがないですね。

この問題を見て、heap領域のデータ管理方法を思い出しました（双方向連結リストのような感じ）。

自分の前部に連結している電車と後部に連結している電車をそれぞれ、 $fd,\ bk$ に記録します。連結していない場合は-1にしておきます。

すると、各クエリは以下のようになります。

・1 x y

$bk[x] \leftarrow y$

$fd[y] \leftarrow x$

・2 x y

$bk[x] \leftarrow -1$

$fd[y] \leftarrow -1$

・3 x

xから $fd$ を順に辿って、-1となるまで出力リストの先頭に加える

xから $bk$ を順に辿って、-1となるまで出力リストの末尾に加える

出力リストを出力する。

クエリの3つめは、C++だとdequeで実現できます。

これがない場合でも、一旦xから先頭まで $fd$ で辿ってから、先頭から末尾まで $bk$ で辿っていけば問題ないと思います。