ABC-D 57-64
昨日までで、ABC-B, ARC-A,ABC-Cが終わったのでABC-Dに戻る。
むずい。ABC-Bが恋しい。
今週末もABCがあるようだ。
４月までに水色を目指したいが、前回の体たらくでは難しいかもしれない。
最近いろいろプライベート忙しいし。
以下解答メモ。
ABC57
数日ぶりにD問題に戻ってきたらWAを出しまくった。
方針は正しかったのだが、最大要素がa個以上あるときにどの範囲まで和を取るのかの部分でミスしたり、最大要素の個数を数えるのにわざわざ二分探索を使おうとして降順になっているのに比較関数をデフォルトのまま使おうとしてバグったり、二項係数の計算を行うのにdoubleでやって数値誤差で値がずれてやられたり。
教訓: 大きさが不安だからといって二項係数の計算をdoubleでやって最後にキャストするなんてことは絶対にしてはならない。誤差でやられる。
ABC58
x, y方向をそれぞれ予め処理しておけばok。
yの方で和を取るときに範囲を間違ってｍではなくnで指定していてREした。
コード内でコピペするときには細心の注意を払う。
ABC59
勝敗は石のとり方に依存する。つまり、最適にという部分は重要。
制約が巨大なのでdpではなさそう。
最終状態は(0,1) or (1,0)のみ。
場から石は毎回 i 個減っていく。片方の山からしか取れない。
(n,m)から最適手で(n-2i, m+i)に行ったとする。
他の動き、(n-2(i-k), m+i-k)を選んだとすると、相手は次のターンで(n-2i,m+i)にできる。
つまり、最大個数を取った場合に将来的に勝つ場合、それ以外の選択では負ける。
最大個数を取ったとき将来的に負ける場合、取る個数をi-k個にしてもその後で合わせられてしまう。
中途半端な個数を取ることでのみ勝てる場合はありえるか？
最大個数で負けるならやはり次のターンで合わせられてしまう。
結局、どちらかの山から最大個数取り続けるのが最適?
高々最初の1ターンしか無いので両方試す。
-> WA & TLE
WAはともかくなぜTLE?
一方に値が寄っていれば (n+m) -> (n+m)/2 -> …なのでlog(n+m)ぐらいのはず。
-> 初期状態として(1,1)の場合を考慮していなかった。
しかしWAの原因はわからないまま。
最大個数を取ったときに勝つならば、という部分を軽く考えすぎた？
相手がどのような行動を取ったとしても、という部分が取り入れられていない気がする。
|X-Y|>1ならAlice, それ以外ではBrownでいいらしい。
終了状態の近辺でどのように遷移が起こるのかをもっとしっかり分析すればよかったのかもしれない。
「最適に行動する」というタイプの問題では、
「負けが決定する状態[今回では (0,1), (1,1)]に１手で持っていけるなら勝ち」
という点を意識してみる。
制約が巨大であるところからシンプルな法則性がありそうという点に気づき、実験してみる。
ここでいう実験とは、紙とペンではなく、小さいサイズに対してdpなどで実際にシミュレートしてみること。
0の時後手が勝利、それ以外の時先手が勝利となるようなもの。
まず、終了状態に対して0を割り当てる。
遷移順を処理するのは面倒なので、実験する場合はメモ化再帰を使うとよい。
ゲーム問題は大抵の場合grundy数求めて法則性探る or ゲーム木探索でゴリ押すのどっちかという印象。
ABC60
w1 <= wi <=w1+3ということは？
入れる品物の個数がnのとき、
重量は n w1 <= sum{wi, n} <= n(w1+3)を満たす。
-> 入れる品物の個数がほぼ決まる。
N(w1+3) <=Wなら全て入れる。
(N-1)(w1+3)<=W <N*w1ならN-1個
N*w1とN(w1+3)の間はN-1個 or N個。
一般に、 n(w1+3)<=W < (n+1)(w1+3)となるnを見つければ
m = n個 or n+1個が最適(たぶん)。
品物の重さは、w1, w1+1, w1+2,w1+3の4種に分けられる。
それぞれの重さの中で価値の順にソートしておけば、重さごとの個数mjを
m = m1 + m2 + m3 + m4
を満たすように回して、重量がW以下の状態での最大価値を求めれば良い。
mは高々N<=100なので、このO(N^3)のループは回る。
とりあえず全てNまで回して、個数が足りなかったらcontinueで良い。
ループの境界値をミスして一度WAを出したが、割とスムーズに解けた。
ABC61
“最長”パスを見つければ良いので、重みを符号反転させて最短距離を出せばいい。
到達可能な閉路の検出が必要なのと、N <=1000なのでベルマンフォード。
重み反転したグラフにおいて1からnの間に到達可能な閉路がある場合、
ベルマンフォードのV-1回の更新のあとにもう一度V-1回回した時に1からnの最短経路長が更新される。
サクッと解けた。スニペット化してあったベルマンフォードを改造するのにすこし時間取られたが。
ABC62
a’の前半にできるだけ大きい要素を、a’の後半にできるだけ小さい要素を集めればいい。分割位置について探索する。O(N log N)でないとTLEするが?よーわからん。
プライオリティキューを使えば良かったらしい。
しばらくdp問題が来てない気がする。
ABC63
解がn回だったとすると、まず全体からB*n引かれる。
その上で体力の残っているものについて(A-B)をn回振り分けて引いていくことになる。
とりあえず、現時点で最大の値のものからAを、それ以外からBを除くことを繰り返せば良い。だが、制約的に、引く回数はO(10^9)になりうるので、各処理がO(1)でも間に合わない。
回数について二分探索して、その上で各 i について調べれば O(N log N)。
上限値は最大体力/B +1にでもしておけばいい。
ABC64
第一印象よりは面倒。
キャンセルされてない’)’と’(‘がそれぞれいくつかあるかを見ればいい。
例えば‘(‘に関しては、左から見ていって、’(‘に出会ったらストックを増やし、’)’に出会ったらストックを減らすようにする。
今日は7問。昨夜解いたABC-D57と合わせて8問。
飲酒してしまったのできょうは終わり。
