[ProjectEuler感想] ~2019/08/07【650問到達】

スポンサーリンク

進捗

645問 → 650問

[554] [562] [578] [589] [489]

650問 到達!
高すぎる目標のつもりで最高レベルを目指して進めてきましたが、何とか達成できました。


実は450問前後から既に、もうほとんど解ける問題が残っていないのではないかと感じ始めていたのですが…。

定期的に未解決問題の一覧を一通り見直して、解けそうな問題や部分的なアイデアがあれば書き出して、目の前の解けそうな5問くらいを選んで最優先にしっかり考えていくことを繰り返し。

とやっていたら、不思議と完全に行き詰まることはなかったです。また、解けた問題はthreadをきちんと確認して勉強しておくと、他の問題で活かせることは結構ありました。あとは、徒歩時間、電車時間、トイレ時間、風呂時間、布団時間などあらゆる時間にEulerを考えるような生活を心がけて気合で…。

完全制覇はまだまだ先、というか、何十年考えても達成できない可能性も十分ありますが、出来るところまで頑張ってみたいと思います。あとは、実行時間60秒に収まっていない問題やコーディングが下手だった問題の復習もしてみようかな?いったんペースダウンするとは思いますが、引き続き楽しみたいと思います。

若い頃から競技プログラミング特化のトレーニングをしている方々とも、数学寄りな問題集でなら戦えるのではないかと思いながら進めていました。ただプレイ人口がが少なめなので、実際どんなもんなのかよくわからない。

※4月にAtCoderを始めましたが、出題内容もかなり違いますね。また、5時間10時間かけて問題を解決する力はAtCoderでは評価に結びつかず、速解きできる範囲を広げないといけないあたりも、結構ゲーム性が異なると感じました。

感想など

・[554] パターンが割と限られることは分かったが、しばらく計算量が減らなかった。
改めて考えると、式の作り方が分かってきた。しかしきちんと詰め切るところが難しい。
だが、どういう形の式になるのかは分かったので、ナイーブ解法で小さい場合を求めることで解決した。
・[562] 格子点を含まず周長が長くなりそうな三角形を上手く生成すればよい。1ヶ月くらい前には解けたつもりになったが、テストケースは合うものの答が合わずしばらく放置されていた。結局、心機一転 1 から書き直した。
・[578] 条件を満たすものを数えるか、余事象を数えるのか。包除の原理を使うべきかなど、かなり何とでもできそうで、と思いきや何をやってもそれなりの手間がありそうで、最後まで迷った。結局計算に30分かかって答を出した。Forumを見るとそれほど方針を外しているわけではなさそう。主要な計算部分でうまく結果を使いまわせていないと思われる。後で見直し。
・[589] 95%の難易度評価がついているが,実際には50~60%くらいにあっても不思議ではないように思える。これは…問題文難?Poohstick とやらの知識が前提にないと読みづらい。終了条件も分かりにくい。例えば、ちょうど同時にゴールしての周回差を含むか等、もうちょっと明示的に書いて欲しかった。結局手法も平凡でコードも短めなものになった。
・[489] 単純計算部分を手計算でやろうとして、意外と複雑だーとなって後回しになっていた。そもそも単純計算は計算機の方が得意なことなので、もっと頼った方が良かった。
最大公約数を評価できたら、あとは簡単だった。$x^3 \equiv a\pmod{p}$ という式を解く必要がでてきたが、平方根の場合は以前学んだことがあったので、3乗根の場合も自力ですぐに考察、実装できた。

コメント

  1. You made a few nice points there. I did a search on the theme and found most people will go along with with your blog.

タイトルとURLをコピーしました