AtCoder ABC118 2完つらい - メモ@inudaisho

敗戦の弁
C の考え方

敗戦の弁

　今回は一言でいうと「つらい」。Cが見ぬけなかった。

　まずA,B。これは8分で飛ばせた。お？今回は快調に行けるか？とおもったものの。

　C がGCDであることをみぬけず、半二重ループでひたすら全検索してしまった。まぁ前処理で全部のテストケースを全検索することはなかったものの、ひとつだけ前処理で圧縮できず、しかもこんな簡単そうなものはバカループで抜けるはずと思いこみ、ひたすらひたすら半二重ループをまわしていた。そのとき男の頭に計算量の概念はなかった。終了。

f:id:inudaisho:20190216231710p:plain — え汗また落ちた

　これはダメ。黒歴史とかじゃない。ただのダメ。当然のことながらはげしく順位を落としてしまった。いやー。さすがに緑から落ちる日が来るとは思わないが、この調子でダメを晒していると転落もあるかも？

C の考え方

　違うことを考えていたときに、ついでにCについて反省してたら、ふと気がついた。C問題のイメージ的には数字が殺しあい消し去り合いながら最後に立っていたものの最小と考えていた。そこでスキマ(差分)がたまたまうまく1になるときがあるので実際に消しながらそれを探す、みたいなことを考えてしまったわけだ。

　そこで前提条件を変えて、皆消えない、殺しあうのでなく減らしあって何かが残るその高さと考えていればよかった。そうすると、ユークリッドの互除法そのものか、となる。どうもこういうとき考えの邪魔だからどんどん消していこうとしてしまうのだが、実際に問題が問うているのは「最小は？」ということなので、残していった方がよい。結局、頭の中のイメージ操作に思考を依存しているので幾何的にハマると強いが、逆にそこをちょっとズラされただけでうまく釣られてしまうということか。うーむ。

　twitter みてるとこのABC118C、意外に考え方が難しいと書いてる人が多いので、たぶん同じような思考の穴にハマった人がいるのでは。