結果
今の私に５完は無理だと悟っていたので、４完は率直に嬉しかったです。D問題は似た問題を多めに解いていたのでラッキーでした。
A問題
サンプルコードにatcoderやtouristを使用しているところに遊び心を感じました。
B問題
O(50^4)=O(6.25*10**6)=O(10**6)だから全探索できました。50**4を概算する力がない私は、最初全探索が間に合う気がしませんでした。5**4はO(10**2)、10**4はO(10**4)なので、かけ合わせてO(10**6)って考えれば良いのですね。とても小さく成長しました。
C問題
点a、b、cがあったとき、aとbを結ぶ線分とaとcを結ぶ線分の傾きが異なれば三角形を構築できることは、中学か高校で習った記憶がありました。それぞれの線分の傾きを求めて等式で評価したところ、0で割ってはダメだというエラーが出てきました。分母が０になるときの場合分けを追加してみると、答えが合わなくなってしまいました。どちらの分母も0なら三角形は構築できず、片方だけ0なら三角形構築できると思ったのですが何が違ったのでしょうか。何が間違えているか理解できなかったので、a/b=c/dをa*d=b*cにしてみると、ACできました。私にしては柔軟に対応できたと思います。
D問題
配列pによって、頭がごちゃごちゃになりました。インデックスを情報として捉えなきゃいけない問題は私の脳のキャパを超えてきます。
考えられうるコマの動かし方を全て考えて、終了条件に合致したらやめるっていう解法しか思いつく気がしなかったので、それを書いてTLEになったら諦めようと思いました。グラフ系の問題の計算量の見積もりが全くわからないのでどうにかせねばと思ってはいるのですが、放置してしまっています。無能が無能たる所以です。
無限にループしては大変なので、あらかじめpの状態として考えられるものを全て列挙して、作られた状態はそこから消していきました。こうすることで一度作られたpがもう一度出てきた場合、そこでストップできます。と、あたかもすぐこの発想が出てきたかのように話していますが、これを思いつくのに20分くらいはかかりました。
配列pによって苦しめられた私は、実装に多大なる時間を要し、もうダメかと思いましたが、なんとかACできました。dequeを使ってグラフを辿っていく問題は相当な数を解いたのですが、まだまだ実装に時間がかかります。無能は人よりたくさん精進しなくてはならないことを再確認すると同時に、なんとかACできたことに成長を感じました。D問題の最速正解4分34秒って書いてあるんですけど、どんな頭してるんですか。こちとら、問題文の意味を理解するのに5分以上かかってるんですが。本当に凄すぎます。
E問題
残された時間は20分弱。実装は諦めて、どうやって解くんだろ〜って考えてました。aの大きい方から見ていくべきな気がするけど、そんなことよりこれ実行時間に間に合う気がしないんですけどって思ってました。解説を読んだところ、この考察はあながち間違ってなくて嬉しくなりました。嬉しくなるより前にどうやって高速化できるか考えろって話です。５完できる日はまだまだ遠そうです。
前処理して高速化する方法が本当に考え出せません。解説ACばっかりじゃなくて自分で考える訓練をしなきゃダメなんだろうな〜と思います。
総括
このまま行くと、水色になれる日はとても遠そうです。有言不実行が特技の私ですが、今週はたくさん精進したいと思います。
