ABC232 参加記録 - geam1113’s diary

コンテスト中AC:A〜E

C - Graph Isomorphism
D - Weak Takahashi
E - Rook Path

C - Graph Isomorphism

順列全探索の問題です。

Pのあり得る組み合わせは最大で8!通りで、順列全探索で十分間に合います。

逆にNが8くらいまでなら順列全探索を疑うと良いかもしれません。

グラフは、実装の簡便さから隣接リストでなく、以下のように隣接行列で持っておいた方が良いと思います。

$G[i][j]=\{0,1\}$

1ならi,jに辺がある。

高橋くんと青木くんのおもちゃが表すグラフをそれぞれ $G_1,\ G_2$ とすると、おもちゃが同じ形であるための条件は、

・i < jであるすべての(i, j)の組みについて、 $G_1 [i][j]$ と $G_2 [P_i][P_j]$ が等しい

となり、条件を満たすPの順列が１つでも存在すればYesとなります。

なお、 $G_1$ に辺がなく、 $G_2$ に辺がある場合どうなるか問題文に記載が無く、一見わかりませんでした。しかし、このような組が存在すれば、辺の数が同数であるという条件から、この逆パターンが必ず存在し、結局問題文の条件を満たさないことがわかりました。

計算量は、 $O(N!N^2)$ です。

提出コード

D - Weak Takahashi

グリッド上を右又は下にのみ移動する場合のDPは典型かと思います。

$dp[i][j]:=$ マス(i,j)までに移動した時に訪れたマスの最大値

と定義すると、

初期値は、マス(1,1)のみ1で、後は0です。

マス(i,j)にはマス(i-1,j)またはマス(i,j-1)から移動できる(遷移元となる)ので、遷移は、

$dp[i][j]\leftarrow max(dp[i-1][j],\ dp[i][j-1])+1$
です。この遷移を基に左上から順に行うことで、各マスの最大値を決定できます。

なお、

・マス(i,j)が壁なら無視

・遷移元のマスがグリッドをはみ出す場合や、壁の場合は、無視

ようにします。

今回、気をつけないといけないのが、辿りつけないマスが存在することです。

これは、

・遷移元となるマスのdpの値が0なら無視

することで、dpの値が0なら壁であるか、到達できないマスであることが保証されます。

提出コード

E - Rook Path

実際に小さいケースでシミュレーションしてみると、以下の事実に気づきました。

・以下のマスは同値としてグルーピングできる。

a. ルークがいる初期マス $(x_1,\ y_1)$

b. 初期マスと同じ列のマス

c. 初期マスと同じ行のマス

d. それ以外

i回目の移動が終わった時の各グループにルークがいる方法を $a_i,\ b_i,\ c_i,\ d_i$ とするとi+1回目の移動後の方法を以下の通り計算できます。

$a_{i+1}\leftarrow b_i\times H + c_i\times W$

$b_{i+1}\leftarrow a + b_i\times (H-2) + d_i\times (W-1)$

$c_{i+1}\leftarrow a + c_i\times (W-2) + d_i\times (H-1)$

$b_{i+1}\leftarrow d_i\times (H+W-4) + b_i+c_i$

これらの式は、実際にグリッドを書いてみて、自分を除く同一の行と列にa,b,c,dが何個含まれるか考えると導けます。

$a_0 = 1, b_0 = c_0 = d_0 = 0$ とし、K回これを計算した後、 $(x_2,\ y_2)$ がどのグループに属するかに応じて値を出力すればよいです。

同値をグルーピングするというのは、逆に考えると、

同一の計算方法をとることができるマスをグルーピングするとa,b,c,dの4つのグループに分けられ、これらは同一の計算方法であるため同値となる。

とも言えそうです。

提出コード