AtCoder Beginner Contest 119 & ABC-D 72-77
4回目のコンテスト参加。初回以来の全完。前回のリベンジは果たせた。
43分で4完の108th。
初の上限パフォーマンス1600を達成。上限解放してくれ。
レーティングは872 → 1047で1000台に突入。
デバッグに手間取って5分ほどロスしたのと、A問題でちょっと時間かかってしまった。pythonでsplitつかってサクッとやったほうが良かったかも。あと、正直D問題はもっと早く解けたはず。方針はすぐに立ったのに実装力とライブラリ知識の浅さで突っかかってしまった。
とは言え、全部一発AC通せたので良い。近傍順位は他はもっぱら青コーダーという感じで、緑の身で潜り込めて気分は良い。
順位表見てる感じでは、やはり皆さんDのほうが簡単という判断をしたようだ。全通り調べてやるという踏ん切りがつくかどうかが鍵だったように思う。想定解は全探索をdfsでやっている。
ratedな参加者の中では10位だったようだ。
4月までに水色になるという当座の目標、あと2回ABCで4完 or ARCでパフォ1800出せれば到達できそう。でも旅行とかで忙しいんだよな…。
以下、C, D解法。
C問題は、N<=8だったので全通り試せると判断し、数列 ell から i個使ってAを作り、j個使ってBを作り、k個使ってCを作るというのを全て列挙して計算した。
使用する竹の組み合わせが決まっていれば、それらで長さXを作るコストは 10*(本数-1) + abs(X - sum(使う竹の元の長さ))で一発で求まる。
実装はnext_permutationでゴリ押した感じ。全探索するという判断を下すまで時間がかかってしまった。計算量の感覚がもっとついていればすぐに動き出せたはず。
D問題は、クエリのかかった点の左右の寺と神社を一つづつ選んできて、それらの訪問順を8通り全て試せばいい。s, t, そしてそれらを逆順にしたものを用意して、lower_boundを使って左右の寺社を探せばいい。前回のD問題に比べると、同じ400点でもだいぶやりやすかった。前回がdpで食らいつけなかったというのが大きいけど。
以下、今日といたD問題の解答メモ。
わからないときはとことんわからない…。
ABC72
単純に左から決めていけるか？
条件を満たしていないもの(pi = i)については、隣接したものとswapすれば必ず条件を満たすようになる。
回数を最小化するには、自身の左と右のどちらとswapするかを決めればいい。
複数個連続して並んでいる場合には、それらの間でswapする。
基本は左から処理していけばいいが、最後尾が条件を満たしていない時どうするか。
左から処理した上で条件を満たさないということは、n-1番目は条件を満たしている。よって、そこでswapすればいい。
ABC72
R<=8なので、街を訪れる順番を全部試しても40000程度。
先にワーシャルフロイドで二点間を求めておけば、
Rから2点 ri, rj 選んだ場合に、他のR-2を経由する距離を求めて最小値を出せば良い。
異なる探索順の列挙はnext_permutationで。
ABC73
まず、Aijのうちで最小のものは必ず道に入る。
各 i について、Aikのうちで最小のものは必ず道に入る。
なぜならば、道の長さは正なので、より大きいものを経由してそのAikを作れないから。
この時点で、都市はいくつかのクラスターに分割されている。
次に、kの次に小さいAijを見る。
Aijについては、直接結ぶ or kを経由するのどちらかが最短。他を経由するより直接結んだほうが近い。
Aij < Aik + Akjなら直接結んだほうが良い。3番目については、Aik + Akl, Aij + Ajlと比較する… 繰り返し。
というか、単純にAijとAik + Akjを比較して、全てのkに対して見ればO(N^3)?
d[i][j] == d[i][k] + d[k][j]なるkが存在すれば、d[i][j]を直接結ばなくても良い。
Aijが最短距離になりうるかどうかについては、Aijに対してワーシャルフロイドしたときに更新が発生するかを見ればいい。
更新が無ければ少なくとも矛盾はない。
要素数がN^2だから全パターン調べたらO(N^4)で… という謎思考にハマってしまって時間を取られた。
ABC74
最適状態では、4辺それぞれに、少なくとも１つの点とのオーバーラップがある。
binom(50,25)はO(10^14)なので、全パターン試すのは無理。
ただ、binom(50,4) = 230300なので、辺に使う4点を選んで全パターン計算して、K以上を含むものの中で最小を探せばいい。
角に来るケースを考えると、x, yそれぞれで考えたほうが良い。
結局、長方形が指定されたときにその内側にいくつの点が含まれるかを調べればいいが、Nが小さいので全て調べても大丈夫。
ABC75
減速が間に合う範囲でとにかく最大速度を目指すのが最適。
時間を横軸、縦軸に速度を取れば、とにかく面積を最大にする問題。
最初の区間について考えると、
v1 > v2ならば、最終的にはv2以下になっていなければならない。
この場合、最大加速度でv2を超えられるかどうか。
v2を超えられるなら、v1に達しない限り加速し、t = t1で帳尻をあわせてv2にする。
v2を超えられないなら、ひたすら加速でいい。
v1 < v2ならばひたすら加速でいい。
とりあえずコード書いてみたが、入力例3のようなケースの処理が面倒。
次の区間だけ見る方針だとこのようなケースを処理できない。
区間 i を見ている時、 t{i+1} + …+tn >= v(t=t1+…+t{i-1})であること = 帳尻をあわせられることを保証しておけばいい。
区間終了時のゴール候補として、v[i+1]とt[i+1]…t[n]の小さい方を採用すればよさそう。
-> 入力例は全部通ったが、テストケースが全然ダメ。
想定通りの動きをしているように見えるのにWA。戦略が間違ってる？
-> 最後に帳尻が合うというだけでは不十分。その後の全ての区間で矛盾が生じないようにする必要がある。
区間iの終了時点の速度glは、 全てのj>iについて、gl - (tj-1 + … + ti+1) <=v[j]でなければならない。
すなわち、その後の全ての区間で減速し続ければ帳尻が合う事を保証しなければならない。つまり、gl <= min_j{v[j] + cumsum(v,j-1) - cumsum(v,i)}
WAがどうしても残ってしまう。心が折れた。
0.5刻みで見てやって、各時刻で許される最速値を取っていけば良かったらしい。
場合分けが多くなるとバグが確実に発生すると思ったほうがいい。
より実装がシンプルな解法を考える。
ABC76
ABC-Dで700点出るんか。
自明な最小の候補としてK自身があるので、まずKの桁和を求める。
高々何桁まで考えればよいなどがあればやりようはありそう。
桁和にはどのような法則性があるのか。
周期性があるわけではなさそう。
倍数を見ていった時、 kをn桁としたとき、 10^n * k以降は確実に桁和が大きくなると言えるのでは？
つまり、各kについて10^nまで見れば十分。kは最高で5桁なのでこれで回る？
-> k = 4が反例。他にも、k = 17で 5882353倍が最適だったり。
10^nしたところで、繰り上がりの影響は排除できない。
解法は、最短経路問題に落とし込むというもの。
givenな数字の桁和を求めるのではなく、その数字を1から構成していくという発想。
ある数字に1を足す or 10をかけるを繰り返すことで任意の数字を作ることができる。
1を足す操作に対応して重み1, 10をかける操作に対応して重み0の辺を張れば、
1からKの倍数への最短経路を求めれば良いことになる。
頂点たちはmod Kで同一視できるので、有限サイズのグラフになる。
1からスタートして遷移させていく。
全ての可能な状態からの遷移が、mod Kで同一視した整数に対してより大きい桁和を返すならば、そのさきの探索は打ち切ることができる。
なぜ mod Kで同一視できるのか。最終的に知りたいのは、Kの倍数、すなわち mod Kでゼロの整数の中でもっとも小さい桁和を持つもの。
mod K が同じものは、全て同じ回数だけ1を加える (and 好きな回数１０倍する)操作によってKの倍数になる。よって、遷移の仕方としてそれらは全て同じなので同一視してしまい、同じmod Kの整数の中で桁和最小のものだけを残して探索すれば良い。
さすがに思いつかんわこれ。
ABC77
二ターン以上は続かないように見える。
最後のカードを自分で引くか相手に引かせるか。
