AtCoder反省会
AtCoderでうまく実装できず、解説を見たものを列挙していく。反省を成長に繋げたい。
・ABC123-D
初見の方針
全列挙してソートすると計算量が多くなってしまう。なのでいかに不要なデータを削るかの話になってくる。
一つのリストAを見ていって、その値がB, Cでどこに入ってくるかを二部探索で探す。そうやって探したインデックスia,ib,icの積がKを超えてしまったら、それ以降は必要ないのでループを切る。
あとは念の為それぞれia,ib,icより一個分多いところまでのリストを作り、全探索してソートで終わり。
でもなぜかWA...
解説を見て
データを削るというのは良い。が、わざわざリストを作らなくても全探索中のループでインデックスの積がKを超えるならbreakしてしまえば良い。
「また、一般の 𝐾 に対して、𝑎 × 𝑏 × 𝑐 ≤ 𝐾 であるケーキの選び方は高々 𝑂(𝐾 log2 𝐾) 通りです。」
らしい。ab<=Kで考えると、aは1からKまでのK通り試して、それに対してb<=K/aが決まるとするとK/aをa=0~Kで積分すればよく、O(KlogK)になるってわけか。
他にも色々方針があるが一番近いのはこれ。
・ABC118-D
初見の方針
桁をなるべく増やしたい。なのでとりあえず1とか7とか必要数の少ない数をダーッと並べる。ここから合計をちょうどNに合わせる。
この合わせ方をかなり苦労して実装。ダーッと取ってきたやつを一つずつ減らして、残りを他ので分け合うようにする。「他の」は複数ありえるので再帰関数で組む。
なんとか実装はできたもののTLEが残ったので退散。
解説を見て
DPだった。dp[i]=「ちょうどi本使うときの最大桁数」として先に桁を求めておいて、あとで数字を上の桁から埋めていくらしい。
「ちょうど」といえばDPか。DP使う可能性を頭から外さないようにしないと。
・ABC022-C
初見の方針
最短経路問題やん！よっしゃこないだ蟻本でやったダイクストラ法が火を吹くでーww
1に繋がってる各頂点に対して、1とその頂点を除いたグラフに対してダイクストラ法で最短経路を求める。
TLEだった。
解説を見て
この方法はモロでダメなやつらしい(凹んだ)。隣接頂点ペアの選び方がO(N^2)、そこからダイクストラで探索するとさらにO(N^2)かかってしまう。ダイクストラは始点が決まってると有利だけど全探索っぽいのには向いていない...
そこでワーシャルフロイドくんの登場である。全頂点対の最短距離をO(N^3)で求めてくれる。蟻本読んでた時はダイクストラでよくね？と思っていたが全探索した方がいいならこっちを使うようにしよう。
書き方が簡単ではあるがループの取り方を間違えてたくさんWAを出してしまった。経由頂点を一番外に持ってくるんだね〜
・ABC017-C
初見の方針
その前の問題でいもす法を使ったので今回も使うかなと思って実装。しかしその後どう答えにむすびつけたら良いかわからず、部分点解法に切り替えた。
解説を見て
いもす法で良い。各座標のうちもっとも合計の小さいものを選べば、これを満たすものを選択しないことでもっとも損失の少ない得点を得ることができる。
・ABC018-C
初見の方針
よくわからなかった。愚直に全探索したらO(RCK^2)で明らかに間に合わないことがわかっていたのでどうしたもんかなあと。
解説を見て
最初にたて一列で見て距離を計算しておく。そうすれば全マス見るときにたて方向は呼び出すだけでいいのでO(RCK)となってまあ間に合うくらい。なんかこうやって「たて(横)一方向で事前に処理しておく」というのは前やった気がするけどなんだったかな。
・ABC104-D
初見の方針
この感じはDPだとはわかった。i文字目を読んだとき「それまでにあったAの数」と「それまでにあったA→Bの数」を記録していくようにした。しかし '?'の処理の仕方がよくわからなかった。
解説を見て
dpではあるが、「残りのあり得る可能性の数」を記録する。それを完成させた方から遷移させていくとうまくいく。目から鱗。
・ABC096-D
初見の方針
とりあえず素数をだすコードは書いたが、それ以降が全然わからない。
解説を見て
「足して合成数」を「足して5の倍数」に限定してしまうとグッっと簡単になってしまう。こういう「適当な例を引っ張ってくる」って数オリとかに近い発想があるなあ...
・ABC044-C
初見の方針
いわゆる部分点解法。O(2^N)で全列挙。どうしたらいいんか....
解説を見て
DPだった(またか)。解法はほぼナップサック問題。とるかとらないかを要素ごとに選べる。合計は小さいので、合計で整理していけば良い。この発想はまだ慣れないなあ。
・ABC076-D
初見の方針
列車の走行区間ごとに見ていって、前の区間と後ろの区間によって形を決める。早く実装できたーとか思ってたけど、これは誤り。上限がめっちゃ大きい区間が連続すると前後の区間を見るだけでは足りない。
解説を見て
時間で区切って離散的に見ていってしまう。各時間ごとに全部の区間の寄与を考えて積分していけばできる。Nとtが小さいことに気づけば自然な発想である...
・ABC061-D
初見の方針
この前のABCでやったのに似ている。スコアにマイナスをかけて最短経路問題としてしまう。負符号なのでベルマンフォード法を使う。
ただ、負閉路ループがあるときは注意が必要で、更新され続けてしまう。よって必要以上に更新されたら打ち切るというのが元のアルゴリズムである。
ただ、終状態までにない経路でループがあった場合もinfとなってしまう。なんとかこの場合を取り除く必要がある。
解説を見て
一旦更新をやめてから、もう一回更新ループをやって見てどの点が更新されるかリストで見ておく。これで最後の点がループ状態にあるかどうかわかる。
・ABC063-D
初見の方針
愚直シミュレーションでは無理。そこでHの最小値を基準に最初に引いちゃえ！と思ってとりあえず引いたがこの方針ではこれをO(N)繰り返さないといけない。実質愚直と同じ。
解説を見て
「条件を満たす最小回数」を二部探索していく。ある回数Tを固定したとき、これが条件を満たすかどうかを判定することができる。うーん、こういうのはよくある発想なのか...?
・ARC093-D
初見の方針
頑張って互い違いに組もうとしたらバグが永遠に取れなかった。
解説をみて
制約を見ればある程度の余裕があることはわかってしまう。最初に「ベース色」を2分割してそこに違いにプロットしていけば良い。
・ARC073-D
初見の方針
ナップザックって言ってるし完全にDPだと思うじゃん？？「重さ」「いくつまでとったか」「実際にとった個数」の３次元配列を組んで遷移させようとしたけど意味わからなくなって挫折...
解説をみて
全然DPじゃないやんけ。重さで場合分けすれば全探索できるんかーい！
・全国統一プログラミング王決定戦本戦-C
初見の方針
方針立たず放置。
解説をみて
縦横独立に考える。そしてそれぞれの中央値を持ってくるだけ。よく考えればそりゃそうだ...
・ABC020-C
初見の方針
「黒マスを通る回数」を固定すれば白マスを通る回数をなるべく少なくするような経路を取れば良い。が、実際にこの経路を探すのが思ったよりしんどく(最悪O(N!))、諦めた。
解説を見て
「x秒で黒マス移動」のxを固定してしまう。単調性があるので二部探索が使えて、O(HWlogT)で間に合う。
・DISCO2016予選-C
初見の方針
Kを素因数分解して因数ごとにループ組んで〜ってやろうとした。でもループが意外に重くなりそうだったし「残りペア」の探し方もよくわからなくて断念。
解説をみて
素因数ではなく、約数全列挙で良い。約数の個数で見れば大した量ではないので。
・ARC090-D
初見の方針
重みつきUnionFindでなんとかならないかなーと思ったけどこっちの実装が辛そうで断念。実際に割り当てするのが現実的だとは思ったが、一回調べたものをもう一回みる必要がある&非連結部分の判定がよくわからなかった。
解説をみて
重みつき有向グラフにする。片方からの距離が D、もう片方からの距離が-Dとなるように設定しておく。連結性は先にUnionFindで根を取ってくることで行う。
