ABC224(雑感)
初投稿です。
ちょうど先週末にABC224に参加したので、それのレビューをしたいと思います。
全体として、いつもよりも手を動かして実装している時間が長かったなぁと感じました。最近気温が下がってきたためか、キーの打ち間違いがもどかしかったです。
ひとまず、コンテスト中に考えたことを説明していきます。
<各問題について>
A.Tires
2文字以上の文字列Sが与えられる。
Sの末尾は"er"または"ist"のいずれかであるため、その末尾を出力せよ。
Sの末尾は必ず"er"か"ist"なので、末尾2文字を取り出して"er"と同じであるか否かを判定すれば十分。
なお、Sが2文字で与えられる可能性もあるため、S[-3:]=="ist"とすると危険。この点さえ気をつければ、あとは使用言語の文法を理解しているかどうかを問う問題といえる。
コード： https://atcoder.jp/contests/abc224/submissions/26753274
（本番中はこれ以上簡単な方法が思いつきませんでしたが、終了後に公式解説を見て、後ろ1文字で判断すれば十分だとわかりました。10秒くらい損したかも。）
B.Mongeness
二重数列A[i][j]が与えられる。
「任意のi < i', j < j'について、A[i][j] + A[i'][j'] <= A[i][j'] + A[i'][j]である」か否かを判定せよ。
A[i][j] + A[i+1][j+1] <= A[i][j+1] + A[i+1][j]を確かめれば十分。
A[i][j] - A[i][j+1] <= A[i+1][j] - A[i+1][j+1] <= A[i+2][j] - A[i+2][j+1] <= ... となるため。jについても同様。
計算量もO(HW)で問題なし。
コード：https://atcoder.jp/contests/abc224/submissions/26757208
（この問題では、問題文通りに４つの変数を全て動かしてもO(H^2W^2)で間に合いました。そちらが想定解のようです。
自分はタイトルのMongenessという言葉から、一つ返事でA[i][j] + A[i+1][j+1] <= A[i][j+1] + A[i+1][j]だと解釈してしまい、問題文をよく読んでいなかったです。こういう衝動的な行動、WAにつながりやすいから反省すべきですね・・・。）
C. Triangle?
二次元平面上の指定された相違なるN点のうち、三角形を作る点の三つ組（順序無視）の個数を求めよ。
O(N^3)で間に合うため、三つ組(v1, v2, v3)を全探索すればよい。
その三つ組を採用するかどうかは、二つのベクトル(v2- v1)と(v3-v1)が平行であるか否かを判定すれば良い。（平行なら三角形がつぶれるため、採用しない。）
なお、二つのベクトル(x1, y1)と(x2, y2)が平行であることの必要十分条件は、x1*y2 - x2*y1 = 0が成立することである。たまに出てくると思い出しにくい。
コード：https://atcoder.jp/contests/abc224/submissions/26759903
（なぜか実行制限時間スレスレ。背筋が凍りました。）
D. 8 Puzzle on Graph
9頂点からなるグラフの盤面があり、うち8個の頂点には区別可能なコマが置いてある。コマには1から8, 頂点には1から9の番号が振られている。
空の頂点へ、隣接するいずれかの頂点からコマを動かす操作を繰り返す。
全てのコマが同じ番号の頂点にあるようにするために、必要な操作回数の最小値を求めよ。
9! ~ 3*10^5 なので、全部の盤面の状態を列挙しても間に合う。
具体的には、盤面の状態を「(1のコマがある頂点番号, 2のコマがある頂点番号, ・・・ , 8のコマがある頂点番号, 空の頂点番号 )」という9つ組([1,2,...,9]の順列)で管理することにする。
辺の情報をもとに、現在の盤面から１回の操作で実現できる盤面をすべて列挙することができる。（空の頂点と隣接する頂点にあるコマについて、そのコマがある頂点番号と、空の頂点番号とを入れ替えればよい。）
ここで、やや抽象的な描像ではあるが、盤面を頂点とし、１回の操作でうつりあえる盤面同士を辺で結んだグラフ（以下、「盤面グラフ」と呼ぶ。）を新たに考える。（こういう考え方、ゲームの問題などでよく出てくる印象があります）
「盤面グラフ」上で辺を一つ通ることは、操作を１回行うことに対応する。このため、もとの問題における操作回数の最小値は、「盤面グラフ」上の最短経路問題の答えに等しい。したがって、この盤面グラフ上でBFS（幅優先探索）等を行えばよい。
なお、計算量については、次のように見積もることができる。１回の操作では空の頂点以外の頂点を選んでコマを動かすため、ある盤面から１回の操作で実現できる盤面は高々８個である。したがって、上記「盤面グラフ」の辺の数は８×(盤面の数) 、すなわち、 3*10^6程度を超えない。最短経路問題を線形で解くBFS（幅優先探索）等の方法を採用すれば、十分高速に解くことができる。
コード：https://atcoder.jp/contests/abc224/submissions/26768166
（正直、この問題が一番てこずりました。
念のため、itertoolsを使って[1,2,...,9]の順列すべてに番号をふったのですが、結果、番号と盤面の状態とを変換する手間が増え、タイムロスにつながりました。辞書(C++でいうmap)や集合を使えば事足りたなぁ・・・と反省。）
E. Integers on Grid
H×Wの２次元のマス目のうち、N個のマスに正の整数が書き込まれ、それ以外のマスには０が書き込まれている。「今いるマスと同じ行または列のマスであって、今のマスに書き込まれた番号よりも真に大きな番号が書き込まれたマスに動く」という操作を行うことのできる最大の回数を求めよ。
ただし、正の整数が書き込まれた全てのマスについて、そのマスを始点とした場合の上記操作の最大回数を答える必要がある。
あるマスから別のマスに遷移できる場合には、その後の操作回数ができるだけ多くなるようなマスを選んで遷移したいはず。そのとき、遷移可能な全てのマスについて、遷移後の最大の操作回数がすべてわかっていれば、適切な遷移先の頂点を選ぶことができるだろう。
具体的には、以下のような遷移式となる。
（あるマスを始点とした場合の最大操作回数）
＝１＋（遷移先のマスを始点とした場合の最大操作回数）の最大値
遷移先のマスは、今のマスよりも書き込まれた数字が大きくなくてはならない。そこで、書き込まれた数が大きい順にマスを調べることにすれば、それぞれのマスを調べる時点で、上の計算式の右辺を計算するための情報がすべて揃っていることになる。考察としてはこれで十分。
実装上、上の計算式の右辺を計算する際に、愚直に遷移先となり得るマスを列挙していると最悪O(N^2)となり間に合わない。このため、行ごと、列ごとに、現在判明している操作回数の最大値を記憶しておくとよい（いわゆる累積maxによるDPの高速化）。もちろん、答えが求まるごとに、行ごと、列ごとの最大値を更新することを忘れないように。
コード：https://atcoder.jp/contests/abc224/submissions/26771493
（遷移順がやや非自明なDPの問題といえます。実装上はそれほどタフでないため、D問題で荒んだ心が癒されました。）
F. Problem where +s Separate Digits
1から9までの数字を複数個並べた文字列Sが与えられる。
Sの適当な位置に"+"を挿入し、足し算の式として解釈した場合の計算結果を、全ての挿入方法について足し合わせた値を求めよ。
2^(|S|-1)のパターンがあり、問題文の通りに計算を行うには時間が足りない。
切り口を変えて、Sの各数字について、それが１の位、１０の位、１００の位、・・・として計上されるパターンが何通りあるかを求める。（いわゆる主客転倒）
たとえば、ある文字を１００の位として計上したい場合、そこから２つ右までの文字間には"+"を挿入できず、その右は必ず"+"を挿入する必要がある（ただし、Sの右端に到達した場合、何もしなくて良い）。それ以外の文字間については、"+"を挿入してもしなくてもよい。
同様に、ある文字を10^nの位として計上したい場合、そこからn個右までの文字間には"+"を挿入できず、その右は必ず"+"を挿入する必要があり（右端をのぞく）、それ以外の文字間については、"+"を挿入してもしなくてもよい。文字間は|S|-1箇所あるが、そのうち自由に"+"を挿入できか否か決められるものがk個あるとすれば、寄与分は、「(その文字の数字)×10^n × 2^(|S|-1-k)」となる。これを、全ての文字とnの組み合わせについて足し合わせれば良い。
上述の通り、k（自由に"+"を挿入できか否か決められる文字間の数）は、基本的には k = |S|-1-n とすればよい。ただし、"+"を挿入できない区間がSの右端に到達する場合には、右端には"+"を挿入する必要がないから、自由に"+"を挿入できか否か決められる文字間の数に一つ余裕ができる。すなわち、この場合に限って k = |S|-n となる。
実装上、2べきや10べきは前準備として計算しておくとよい。
コード：https://atcoder.jp/contests/abc224/submissions/26774433
（主客転倒はよかったのですが、上記右端が例外でることに気づいたときにテンパりました。メンタル弱し。）
G. Roll or Increment
1からNまでのマスから成るすごろくで、コストAを払って1進むか、コストBを払って完全ランダムに移動するかを選べる。マスSから出発してマスTにたどり着くまでの必要移動回数の期待値がもっとも小さくなるようにした場合、その最小期待値を求めよ。
E問題と同様の発想で、どの場合においても有利な選択をするということに着目すれば良い。
(今いるマスからの最小期待値)
＝min { A + (1進んだマスからの最小期待値), B + (全てのマスの最小期待値の平均) }
と遷移式が立つ。
しかしこの遷移式は、E問題のように答えを確定させる順番を工夫することで解くことはできない。なぜなら、右辺の「(全てのマスの最小期待値の平均)」を確定させるには、左辺の「(今いるマスからの最小期待値)」の値が確定していなければならないためである。（相互参照）
この場合でも強引に計算を進めるため、右辺に出てくる「(全てのマスの最小期待値の平均)」の値を適当な値で決め打ちしてしまう。これにより、右辺の「B + (全てのマスの最小期待値の平均)」の部分は定数となり、「(今いるマスからの最小期待値)」を仮計算できるようになる。
当然ながら、適当な決め打ちをした以上、仮計算の結果が正しいという保証はない。しかし、この仮計算により求めた全てのマスの最小期待値から、改めて「(全てのマスの最小期待値の平均)」を求め、それが決め打ちした値と一致するのであれば、上記の遷移式が矛盾なく成立していることになる。すなわち、仮計算の結果が真の値となる（発想としては、自己無撞着とか、セルフコンシステントとかと呼ばれるものに近い。）。この一致点を探索により決定すればよい。
具体的には次のようになる。
まず、遷移式から、各マスについての「(今いるマスからの最小期待値)」の値は、以下のようになる。
（１）目的地(T)よりも値が大きいマスにいる場合、B + (全てのマスの最小期待値の平均)
（２）目的地(T)以下の値のマスにいる場合、A*(Tまでの距離)とB + (全てのマスの最小期待値の平均)の小さい方
特に（１）は、目的地(T)よりも値が大きいマスにいる場合、インクリメントしても目的地にたどり着くことはないことから理解できる。また、（２）は、目的地(T)以下の値のマスにいる場合、ランダム移動に頼るよりもインクリメントした方が有利な場合があることから理解できる。
この（１）（２）から、「(今いるマスからの最小期待値)」の値は、目的地(T)から左に伸びる一定区間ではA*(Tまでの距離)となり、それ以外ではB + (全てのマスの最小期待値の平均)となることが導かれる。この一定区間の範囲を求めれば、あらわに各マスの「(今いるマスからの最小期待値)」の値を求めなくとも、等差数列の和の公式などを使って、「(今いるマスからの最小期待値)」の平均値を計算できる。この平均値が、仮置きした「(全てのマスの最小期待値の平均) 」に等しい点を探せば良い。
上記平均値と仮置きした「(全てのマスの最小期待値の平均) 」とが等しくなるところを探すには、二分探索を使えば高速にできる。今回は、上記平均値と仮置きした「(全てのマスの最小期待値の平均) 」との差が単調性を有するため、二分探索を適用して良い。
コード：https://atcoder.jp/contests/abc224/submissions/26778661
（正直、コンテスト中には単調性を十分に検討していなかった。過去にABC189Fを同じ方針で解いていたため、二分探索を適用する正当性についての考察を省略してしまっていた。良い子は真似しないでね
また、コンテスト後にO(1)で解けることを知りました。このくだりABC189Fでもやったので、僕の数学力は改善していなかったということになります・・・）
<感想>
D問題に想定以上に時間がかかってしまい、その後の問題を焦って解きました。F問題を終えるまでは生きた心地がしなかったです・・・。
それでも、E以降の問題がすんなり解けて、最終的に61位まで上ることができました。最近スランプ気味だったこともあって、メンタル的にはとてもプラスです。なお来週のAGCで爆死する模様
H問題については、たどり着いた時点で９分しか残っておらず、双対問題に直してフローが使えそう、という心証を得て時間が尽きました。辺のコストが負で、扱いに慣れていなかったので回避する方法を検討したのですが、それもタイムロスの原因です。修行が足りていないですね・・・。
この記事ですが、７問分のレビューを載せるとかなりの分量になってしまいました。今後は問題ごとにするかもです。
