ABC407-D を Python で解いた

この回は不参加だったので昨日バーチャルコンテストでやってみました。D 問題が解けなかったので後から頑張って AC しました。記事に整理します。

ところで、最近（ABC411まで）の D 問題はいきなり難しくなった気がします。この回も難しかったのでここから一気に難化したのでしょうか。diffculty の値も高いです。ただ ABC406 以前は緑 diff の D 問題もそこそこ解けていたので相性の要因も大きいのかもしれませんが……これが続くとまずいのでなんとかしたいところです。

考察

全てのマスの 0, 1 を総当たりしても 2 の 20 乗しかないので総当たりができそうです。
その場合、方針として2つ考えられます。
(1) 0, 1 の総当たりで配置を作ってみてから、ドミノを用いてその配置を作れるかどうか検証する。
(2) ドミノを実際にはめていって作れる形を全て列挙していく。

(1) は過去問でいうと ABC219-E ですね。
https://atcoder.jp/contests/abc219/tasks/abc219_e
この方針でやってみて結局解けませんでした。
後で ChatGPT に聞いてみたら二部グラフとして考えてマッチングをして……みたいに言ってコードも出してくれたんですが、難してどうにも理解出来なさそうだったのでとりあえず諦めました。

(2) は公式解説が縦と横の二重ループでマスを1つずつ見ながら、さらにその中で作れる可能性のある配置の配列をループで回すという見たこともない形をしており、僕の理解を超えていたのでとりあえず諦めました。

再帰関数を使って探索できないか考えてみます。また、公式解説にならって

• 何も置かない
• 横向きにドミノを置く
• 縦向きにドミノを置く

という場合分けをしていきます。この考え方は ABC196-D でもありました。
https://atcoder.jp/contests/abc196/tasks/abc196_d
これも難解な問題で、一応解説を見ながら AC はしましたが解き方を全く覚えていませんでした。見たことのある問題の類題しか解けないのに過去問の理解をおろそかにしているようでは先は無いですね。まあこの問題も今回の問題を経た後ならもう少しまともに立ち向かえるようになっているかもしれません。この手の問題の典型的な考え方として覚えておきましょう。

さて、僕は再帰関数を使うのが苦手です。できあがったコードを見ればどんな風に動くのかはなんとか理解できても、それを一から組み上げるのが難しいです。返り値を次々に渡していく形と関数の外の変数（グローバル変数など）を書き換えていく形がありますが、前者は特に思いつくのが大変ですね。形としては非常に美しいと思うのですが。

苦手でもなんとか考えてみましょう。再帰関数を用いて DFS でマスを埋めていきます。

• マスごとに3パターンを考える（典型的な考え方）
• 横向きを置く場合は右のマスも一緒に埋める
• 縦向きを置く場合は下のマスも一緒に埋める

この辺まで考えたところで、それぞれのマスに未確定 or 0 or 1 の3通りの状態を設定すればいいのではないかと考えます。しかし、よく考えたら未確定と 0 とは区別する必要がなさそうです。要はまだドミノが置かれていないマス（0になっているマス）に3パターンのいずれかを当てはめていけばいいです。

再帰関数ということで、何を引数として渡すのか考えてみましょう。今の盤面（マス全体）を表現する情報と、次に調べるマスの座標を渡してやると良い気がします。計算量のところで 2^20 と考察したように、bit を使って盤面が表せます。また、座標もこれに合わせて 0から19 (0 から H*W)で表すようにすれば何かと便利そうです。

返り値は上記の 3 パターンを実行した後の盤面 (bit) と、次に調べたいマスの座標です。……と考えたところで、やっぱり返り値はいらないなと気づきました。関数の外で変数（配列）を宣言し、それを書き換える形にします。配置が完成したら配列の中に配置を入れてきましょう。

始点は dfs(0,0) のようにし、終点は今から調べるマスが (H,W)になったときか枠を飛び出してしまうときあたりで良いでしょう。

実装

次は実装です。全てのマスを左上から順に見ていきます。盤面は最大 2^(H*W) となる 2 進数 bit で表現します。最初は何も置かれていない状態 bit = 0 から出発します。座標 (i, j) は i * W + j で表される整数 n で表現します。これも一番左上 n = 0 から出発します。

それぞれのマスについて、既にドミノが置かれている（bit の該当する桁が 1 になっている）なら bit を更新せず座標のみ +1 します。ドミノが置かれていない場合に 3 択があります。

• このマスにはドミノを置かない
  → bit はそのまま、座標を +1。
• 横向きのドミノを右隣のマスにまたがって置く
  → bit を更新し、座標を +1。
  ただし一番右の列ではこれはやらない。
  また、右にドミノがある（bit のその桁が 1 になっているなら）やらない。
• 縦向きのドミノを下隣のマスにまたがって置く
  → bit を更新し、座標を +1。
  ただし一番下の行ではこれはやらない。
  また、下にドミノがある（bit のその桁が 1 になっているなら）やらない。

終了条件は盤面を飛び越えて n = HW になることです。そのときにこれまで作ってきた盤面を配列に記録して終わります。また、 n = HW - 1 で終わるようにしても同じだと思います。一番右下のマスは、先にドミノが置かれていることはあっても今からドミノを置くことはないからです。

余談ですが、横向きのドミノを置くときに座標を +2 するように実装していたら終了条件で泥沼になって時間が溶けました……。他にもいろいろとおかしかったのでしょう。(H, W) で終わる場合と盤面を飛び越えて (H+1, 0) で終わる場合に分かれてしまったようで、終了条件を 2 つにしたらようやく AC になりました。座標の移動は +1 で共通にしてしまった方が楽ですね。横向きに置いたらどうせ右隣のマスには 1 が置かれるので、次の座標に進んだときに何もせずスキップされます。こういう風に処理を共通化するのは初歩的なプログラミングテクニックな気がします。最初からそれを考慮して書けないところに自分のプログラミングのセンスの無さが表れていますね……。

import sys
sys.setrecursionlimit(10**8)

H, W = map(int, input().split())
# 最初から 2 次元の盤面をバラしておいて 1 次元の配列として扱うようにする。
A = []
for i in range(H):
  line = list(map(int, input().split()))
  for j in range(W):
    A.append(line[j])

##### 盤面を全探索してドミノを置いていく
patterns = []
def dfs(bit, n):
  if n >= H * W: # 座標が盤面を飛び出していたら終了し、記録する
    patterns.append(bit)
    return
  
  # 何も置かずに次のマスへ移動する場合
  dfs(bit, n+1)

  # 横長のドミノを右隣にまたがって置く場合
  if n % W != W-1: # 右端の列には置けない
    # このマスか、右隣のマスに既に 1 が置かれていたら置けない
    if ((bit >> n) & 1) == 0 and ((bit >> (n+1)) & 1) == 0:
      next_bit = bit | (1 << n) # 自分と
      next_bit = next_bit | (1 << (n+1)) # 隣を 1 にする
      dfs(next_bit, n+1) # 置いたら次のマスに移動する

  # 縦長のドミノを下隣にまたがって置く場合
  if n // W != H-1: # 下端の行には置けない
    # このマスか、下隣のマスに既に 1 が置かれていたら置けない
    if ((bit >> n) & 1) == 0 and ((bit >> (n+W)) & 1) == 0:
      next_bit = bit | (1 << n) # 自分と
      next_bit = next_bit | (1 << (n+W)) # 隣を 1 にする
      dfs(next_bit, n+1) # 置いたら次のマスに移動する

dfs(0, 0)

##### XOR の最大値を全探索する
def base_10_to_n_fill_0(n, num, length): # 10進数を n 進数に変換する（0埋めver.）
  n_str = ""
  while (num >= n):
    n_str += str(num % n)
    num //= n
  n_str += str(num)
  for i in range(length - len(n_str)):
    n_str += "0"
  n_str = n_str[::-1]
  return n_str

ans = 0
for bit in patterns:
  xor = 0
  str_bit = base_10_to_n_fill_0(2, bit, H*W)
  for n in range(H*W):
    if str_bit[n] == "0":
      xor ^= A[n]
  ans = max(ans, xor)
print(ans)