ちゃんとお休みなので先週のABCの復習。今回Dを飛ばしてEを解いてる人が多かったのでEもやりたいですが、取り合えずDまで。リアルタイムでは愚直に実装して2/3がTLEでした。
以下、ACまでの取組結果ですが、やりながら書いたので非常にまとまってないです。
ーーー
■ 解説を読む
目標は解説ACなので、まずは解説PDFを読むが全然分からず。次に解説動画（実装前まで）を見るけど、やはり良く分からない。動画はPDFよりは分かりやすいしやってくれるのは有難いんですが、C以上を解説動画見て理解できたことが一度もないです。自分は茶色中位だけど、おそらくもう少し上のレート（または頭いい人）を対象視聴者として設定されてるっぽいです。同じ位のレートの人でも「解説動画でACできました」「凄いわかりやすい」という人もいるので、慣れの問題もあるかもしれない。
という訳で解説サイトを探します。前回の日記で解説サイトさんをリンクしましたが、Dについて詳しい説明を書いてる方が中々おらず。まぁ万人向けに解説している訳ではないし、自分用メモって方も居ると思うので。そんな中、一番わかりやすかったのは下のブログでした。この方は結構上のレートの人みたいですが、かなり下のレベルにもわかりやすい解説を書いてくれるので、大変ありがたいです。
AtCoder ABC 152 D - Handstand 2 (400 点) - けんちょんの競プロ精進記録
これで回答にたどり着いた訳ではないけど、方針が理解できたので、再度実装にトライしました。ここまで前振りで以下解法メモです。
ーーー
■ 実装してみる
最初にやったとおり愚直に計算するとO(N2乗)、Nが2×10の5乗なので時間が間に合わない（後述しますが、この条件だと間に合わないって皆さん何を以って判断してるのだろう…）。という訳で工夫が必要。
最初と最後の数字に注目します。例えばN=10000のとき、Aが1234、Bが401の場合は条件に合致する。あとAが1みたいな一桁の場合、Bが1221の場合とかと一致します。よって間の数は関係ないので、桁数とかも関係ない訳ですね。
そこで、まずAについて最初と最後の数字のペア（以下、[X, Y]と記載）を数えます。N=100の場合、[1,1]はA=1、11の場合が該当するので2回、[1,4]はA=14の時だけなので1回。これをmapとかに持っておく。これを作るのはO(N)の計算でできるみたいです。
次にBについて、今度は逆に最後と最初の数字のペア（[Y, X]）に対して、[X, Y]があるか探すわけですが、すべてのAについて探すと先の通りO(N2乗)になります。ただし、先にAの[X, Y]の組み合わせは登場回数をカウント済なので、1つのBに対して99通り試せばよいだけです。これはオーダでいうとO(N)ですね。例えばB=11の場合、全てのAについて探すと結果A=1とA＝11がヒットするわけですが、[1,1]の登場回数が2回なのを知ってるので、これを回答用の引数ansに足しこんでいきます。
これでAC出来ました。
ーーー
■ 計算量について
今回に限らないんですが、どこの解説でも「Nが2×10の5乗で、愚直実装だと計算量がO(N2乗)なので間に合いませんよね」って書いてますが、何故そうなのかに触れてる人がいないので、未だに理由が良く分からず。経験則なんでしょうか？
例えば最内ループで1[ns]掛かる計算をする場合、単純に2×10の5乗を2重ループにすると40,000,000.000[ns]＝合計40[sec]。大抵、実行時間制約が2[sec]なのでこれだと確かに間に合わないですね。これが10の4乗だと合計0.4[sec]になりますが、そもそも1[ns]の処理とか無理なので、係数次第ってことになるんでしょうか？
ーーー
そんな感じで記録を書いてみました。この後Eに取り組みます。
上でも書きましたが低レベル向けの解説不足に困っているので、灰色・茶色向けに解説書いてますって方がおられたら教えてください。こっちからできる事は何もないですが…
