筆者はレーティング201の灰色コーダーで、普段はRustを使って解いています。もしかしたら考察が不十分な点が見られるかもしれませんが、その点は突っ込んでいただけると幸いです。
A - Raise Both Hands
- A問題ではおなじみ（？）の与えられた入力に応じて条件分岐を書くだけの問題。
- $L$と$R$が$1$、または$L$と$R$が$0$の場合にInvalid、$L$が$1$の場合にYes、$R$が$1$の場合にNoを出力するように書くだけ。
B - Binary Alchemy
- $A$を入れるための二次元配列aと元素の番号を入れる変数ansを用意する。
- $N$回回すfor文の中にif文を作って、ansとfor文のカウンタiを比較する。
- ansの方が大きければa[ans][i]をansに代入。
- iの方が大きければa[i][ans]をansに代入。
- 以上の処理を行った後にansの値を出力する。
C - Word Ladder
- 辞書順最小ということで、貪欲法を使う。
- 一回の書き換えの動作で書き換えられる候補を列挙して、そこから辞書順で最小の文字列を選べば良い。
- 例えば$S=abcd$、$T=bbbb$だった場合、$1$回目に$S$を書き換える際に考えられる候補は$\{bbcd, abbd, abcb\}$の3つ。このうち、辞書順で最小なのは$abbd$なので、$abbd$を問題文でいう所の配列$X$に入れる。
- これを$2, 3, 4, \cdots n$回目まで同様に行う。
- 例えば$S=abcd$、$T=bbbb$だった場合、$1$回目に$S$を書き換える際に考えられる候補は$\{bbcd, abbd, abcb\}$の3つ。このうち、辞書順で最小なのは$abbd$なので、$abbd$を問題文でいう所の配列$X$に入れる。
- $S$と$T$の一致を確認する処理を行う時点でまず最悪時間計算量が$O(N)$で、$S$と$T$を一文字ずつ比較したり、違う場所を書き換えたり、列挙したりする時点で$O(N^2)$の計算量を要するため、時間計算量は$O(N^3)$となる。
- $O(N^3)$は比較的大きい計算量だが、この問題の場合はSとTは両方とも$1$以上$100$以下の文字長であり、$100^3 = 10^6 < 10^9$ であるため、十分間に合う（$10^9$は家庭用PCの毎秒計算速度）。
D - Cross Explosion
- どのように座標上に壁があるかないかを判別し、速く壁の数を計算できるようにするかが鍵。
- $H×W≤4×10^5$であるため、例えば壁を「*」、壁でない場所を「」とした二次元配列を用意して、「*」をそのまま数え上げる方法では間に合わない。
- 集合を使って、壁がある座標をタプルで管理して数え上げる方法も、爆弾を落とした場所から最も近い座標を計算する過程で膨大な時間がかかる可能性があるため、同様に間に合わない。
- 爆弾を落とした座標よりも低い/高い座標の中で最も近い値を簡単に得るには？
- 壁があるかないかをグループ分けする$\Rightarrow$Union-Find木を使う方法もある（寧ろこっちの方法の方が先に思い浮かびやすいかも）。
- 恐らくボンバーマンにインスパイアされた問題？
E - Avoid K Partition
- まずは数列Aの累積和を計算する。
- 累積和の結果を基に、どこで分割すれば和がKにならないかを、二重ループを使って数え上げる。
- 各分割ごとに数えたものを保存する→動的計画法を使う。
- 上記の方法で二重ループを使っているために$O(N^2)$の計算量だが、この問題の$N$の制約は$1≤N≤2×10^5$であり、$(2×10^5)^2 = 4×10^{10} > 10^9$ということでこの問題では間に合わない。
- 二重ループを使わずに数え上げるには？→連想配列を使う。
- 着目している位置以前の累積和をキーとした連想配列を使って、現在着目している位置から考えられるすべての場合の数と、着目している位置と$K$の差を使って取り出した連想配列内の値の差を取れば答えが求まる。
- 着目している位置と$K$の差を使う理由は、累積和の数列を$B$、着目している位置を$n$、着目している位置以前にある任意の位置を$m$として、動的計画法を使う方法では$B_{n}-B_{m}=K$である場合の数を除外して数え上げている。この式は$B_{m}=B_{n}-K$と変形できることから、着目している位置以前にある任意の位置の累積和が着目している位置の累積和と$K$の差と等しければ、着目している位置の累積和と着目している位置以前にある任意の位置の累積和の差が$K$になるということであり、連続部分列の和が$K$に等しいということにも繋がる。
- $B_{m}=B_{n}-K$となる場合の数は本来除外すべき場合の数であるため、現在着目している位置から考えられるすべての場合の数から引いているということ。
- 着目している位置以前の累積和をキーとした連想配列を使って、現在着目している位置から考えられるすべての場合の数と、着目している位置と$K$の差を使って取り出した連想配列内の値の差を取れば答えが求まる。
- 恐らく上記の連想配列の方法を取れば計算量は$O(N)$で、$2×10^5 < 10^9$より十分間に合う。
- for文は一回使う必要があるのでその時点で$O(N)$の計算量を要する。
- 連想配列に要素を挿入したり、取得したり、更新したりする処理は基本的に$O(1)$の計算量で行われるので、$O(N)×O(1)=O(N)$といったところ。
- 制約で示されている$N$がデカかったら連想配列を使うことを疑ってみると良いかもしれない。
F - Cake Division
- ケーキを$K$人で分けて食べる際に、切ったケーキの中で最も質量が小さいケーキをどれ程大きくできるか、という問題。
- この際、切れる場所はあらかじめ決まっているものとして、切れる場所に応じた重みが$A$として渡される。
- 所謂「最小の最大化」の問題なので、二分探索を使うと良い。
- 「すべてのピースの質量が$X$以上である」と考えて、条件を満たすような切れ目を探す。
- $A$が$X$以上になる場合をしゃくとり法で計算し、$X$以上になった時点で$A$を分割するといった貪欲法のアプローチでAの切れ目を探すことができる。
- しかし、例えば$A_0$と$A_1$の間を最初に切りたいといったような、$A$の始点を要素と要素の間にしたい場合があるため、$A$の始点から判定するだけでなく、$A$の各要素からも判定する必要がある。
- もちろん、この際の計算量はそれなりに要するため、判定方法を工夫する必要がある。
- 考え得る$A$の切れ目を頂点として、グラフを作る。
- この時、1つの切れ目を作った時に、次の切れ目がどこになるかを辺として結ぶ。
- こうして結ぶと、1つの頂点に対して1つの辺が一本のみでできている（$n$頂点$n$辺のグラフである）ことがわかる→辺を$k$回辿った際の移動距離を求めるfunctional graphの問題に言い換えることが出来る。
- 辺を$k$回辿った際の移動距離の求め方に関してはダブリングで計算できる。
- この時、1つの切れ目を作った時に、次の切れ目がどこになるかを辺として結ぶ。
G - Divisible by 3
- 問題自体は正の整数$n$の正の約数の総和が$3$で割り切れる時に、$n$を「良い整数」として、$M$の長さの正の整数列のうち、その正の整数列の要素の総積が$N$以下になる「良い整数」になるものの個数を求めるというもの。
- 正の整数列の要素の総積がN以下になる数で構成された$M$の長さの整数列を取り出した後に、その整数列内の約数を（重複を無しとして）すべて取り出し、$3$で割り切れるようなものを求める。
- あまり考えずに解こうとすると、計算量が膨大になるのは言うまでもない。
- G問題はABC全体を通して、基本的にはARCやAGCなどといった中級者〜上級者向けコンテストの合間の暇つぶしのためにABCに参加している人向けの問題だと個人的に思っており、今回も解いている人の数は60人と少なめ。
- その中でも期間中に5人ぐらいしか正答していなかったので、正直自分みたいな素人がコンテストの期間中にこれを解く必要はあまり無いのではないかとは思う。