[AtCoder 参加感想] 2020/08/22:ABC 176

	A	B	C	D	E	F
問題文	■	■	■	■	■	■
自分の提出	■	■	■	■	■	■
結果	AC	AC	AC	AC	AC	AC

全体感想
問題B – Multiple of 9
問題D – Wizard in Maze
問題E – Bomber
問題F – Brave CHAIN

全体感想

66 分 2 ペナ → 6位。なかなかの高順位です。

問題F、FAです！

結構時間かかったので、速い人は6完してるんだろうなーと思って順位表を見たら、FAでびっくりしました。 pic.twitter.com/cXGmdN6H2P
— maspy (@maspy_stars) August 22, 2020

問題Fで、First AC をもらいました。ABC級-問題F では、3回目のFirst ACみたいです。少しずつ戦闘力上がってるかなー？

問題B – Multiple of 9

多倍長整数を使う方法：

x = int(input())
print('Yes' if x % 9 == 0 else 'No')

これで AC になります。長い文字列から整数への変換が必要であるため、一桁ずつ見るよりもパフォーマンスは悪くなるようです。

(207ms) https://atcoder.jp/contests/abc176/submissions/16145111

問題D – Wizard in Maze

01-BFS と呼ばれる方法で、$\Theta(HW)$ 時間解法が実現できます。dijkstra 法（$\Theta(HW\log HW)$ 時間）を使う場合と結果的に同じ計算順序になりますが、計算量がよいです。

（dijkstra 法でも余裕を持って通ります：https://atcoder.jp/contests/abc176/submissions/16156582）

問題E – Bomber

はじめ、$H\times W\leq 3\times 10^5$ と勘違いして、1ペナです。残念。

行、列の爆破対象の個数を $\mathrm{row}[x]$, $\mathrm{col}[y]$ などとすると、爆弾を $(x,y)$ に仕掛けた場合のスコアは、$\mathrm{row}[x] + \mathrm{col}[y]$ あるいはそこから $1$ を引いたものになります（$(x,y)$ に爆破対象がある場合に、ダブルカウント分を除く）。

私は思考順序としては、「とる行を固定すると、最適解はどうなるかな？」から考えました。$\mathrm{col}[y]$ が最大となる列で、交点に爆破対象がないところがあればそこを選べばよいです。そういう列がない場合……あれ？？その場合も $\mathrm{col}[y]$ が最大の列を選べばよさそうです。

結局、$\mathrm{row}[x]$, $\mathrm{col}[y]$ が最大であるような行・列を選ぶ戦略しか考える必要はありません。そういう選び方であって、交点に爆破対象が置かれていないものがあるかどうかを確かめればよいです。

そのような行の集合を $A$, 列の集合を $B$ とします。問題は次のようになります。

集合 $|A|, |B|, |C|\leq 3\cdot 10^5$ が与えられる（$C\subset A\times B$）。$a\in A, b\in B$ であって $(a,b)\notin C$ となるものが存在するかどうかを判定せよ。

すべてのペア $(a,b)$ を調べると、一見間に合いません。ペアは $(3\cdot 10^5)^2$ 通りあるからです。

しかし、実は次のような単純なアルゴリズムで問題ありません。

find = False
for a in A:
  for b in A:
    if (a,b) not in C:
      find = True
      break

二重ループがありますが、それとは別に $(a,b)\in C$ となる回数は $|C|$ 以下なので、ループ回数は $|C|$ で評価できます。

私は、別の方法をとりました。単純に、$|A|\cdot |B| = |C|$ であるかを確認すればよいです。

問題F – Brave CHAIN

各時点で、「残した2枚のカード → 最適なスコア」を求めることにより、dp 解法ができそうです。

もともとの手持ち $2$ 枚 $x, y$ から、$3$ 枚 $a,b,c$ が追加されて、残す $2$ 枚（$10$ 通り）を選ぶ。遷移が $\Theta(1)$ なので、単純にやると計算量 $\Theta(N^3)$ となります。定数倍も軽くなく、間に合いません。

しかし、持ち替えない場合（$a=b=c$ なら $1$ 点の共通の加点、そうでない場合はスコア変化なし）は加点を dp テーブルとは別の変数で持てば、dp テーブルを書き換える必要はありません。すると、$3$ 枚のカード $a,b,c$ が追加された場合に新たに計算必要があるのは、これら $3$ 枚と関係する場所：$(a,-), (b,-), (c,-)$ の形のインデックスに限られます。合計で $\Theta(N)$ 通りしか遷移先がありませんから、これらへの遷移を上手くまとめて計算すれば、計算量が落ちるのではないかと考えました。

これは実際、以下の通り実現できます。遷移前の手持ちのカードを $(x,y)$ として、追加されるカードを $(a,b,c)$ とします。$a=b=c$ の場合は、スコア $1$ を追加するのみで、更新は行いません。この場合は以下省略します。

カードをそろえない場合。
- 手持ちカードが変化しない場合：更新なし
- $a,b,c$ から手持ちカードを $1$ 枚採用する場合：
  - $a$ を採用するとして、$\dp[a,x] \leftarrow \max(\dp[a,x], \dp[x,y])$ の形の遷移である。これは $\dp[x,-]$ の最大値を用意しておけば、$1$ 件あたり $\Theta(1)$ で行える。$x$ を動かして、全体では $\Theta(N)$ である。
- $a,b,c$ から手持ちカードを $2$ 枚採用する場合：
  - $(a,b)$ を採用するとして、$\dp[a,b] \leftarrow \max(\dp[a,b], \dp[x,y])$　の形の遷移である。dp テーブル全体の最大値を用意しておけば、$\Theta(1)$ で行える。
カードをそろえる場合。$a$ をそろえるとしてよい。
- 新しいカードから $1$ 枚を使う場合。
  - 遷移は $\dp[b,c]\leftarrow \max(\dp[b,c], \dp[a,a] + 1)$ である。これは $\Theta(1)$ で行える。
- 新しいカードから $2$ 枚使う場合。$a=b$ を使って $c$ を残すとしてよい。
  - 遷移は $\dp[c,x]\leftarrow \max(\dp[c,x], \dp[a,x] + 1)$ である。これは $x$ ごとに $\Theta(1)$、全体で $\Theta(N)$ で行える。

以上で、カードを $3$ 枚追加したときの遷移が $\Theta(N)$ で計算できることが分かりました。

地味に、どの $2$ 枚をそろえるかなど、実装に頭を悩まされます。次の方法をとりました。

a, b, c = 新しい 3 枚
for _ in range(3):
  a, b, c = b, c, a
  # (x,y) から (a,x) に持ち替える場合の遷移
  # (x,y) から (a,b) に持ち替える場合の遷移
  # (a,a) から a をそろえて (b,c) に持ち替える場合の遷移
  if a == b:
    # (a,x) から a をそろえて (c,x) に持ち替える場合の遷移

a,b,c を入れ替えながら、同じ処理を $3$ 回まわしています。ときどき使える実装の簡略化だと思います。