euler全埋め維持、AtCoderアルゴ赤維持で一応目標は達成 pic.twitter.com/MS4UAyfCeH
— ひとあれ (@hitoare1) 2023年12月31日
現時点でProject Eulerの問題を全て解いているので、今回はdifficulty 100%の問題27個について解説をします。
ProjectEulerは101番以降の問題は原則解法の共有が禁止となっています。 解法の核心には触れないレベルでのコメントを添えてあります。
注意点
- 完全主観
- この辺の難易度だと実装はほぼ考慮しない
- 類題があると気持ち低め
- 「典型」と書いてあっても、あくまでEuler内で典型というだけであって他の場所ではあまり見ないテクニックだったりする
S+
#763 Amoebas in a 3D Grid - Project Euler
個人的には現時点でPE最強枠 シンプルな設定だけどどこから手を付ければいいのかから難しい 解としてありえるものの構造を考えることになるがかなり複雑
S
#499 St. Petersburg Lottery - Project Euler
正直評価が難しい 重要な性質があるのでそれを見抜けるか、もしくはエスパーするか
#585 Nested Square Roots - Project Euler
Eulerらしい問題 重複を取り除くのに苦戦した記憶
どの順で当たったらこの順になる…を整理するのが難しい、 それ以降はゴリ押しっぽいけどそれなりに数学する必要はある
#780 Toriangulations - Project Euler
solved数が異様に少ないけど個人的にはそこまでだと思ってる 条件を丁寧に1つずつ処理してサンプルに合わせる
#792 Too Many Twos - Project Euler
簡単そうに見えて難しい 二項係数関連は公式がありすぎて逆にどれを使えばわからなくなりがち 苦労して通した後にForumの一番上の解法を見て魂が抜けた
#798 Card Stacking Game - Project Euler
すみません完全に実験で通しました
#806 Nim on Towers of Hanoi - Project Euler
結構な量の考察が必要とされる 競プロ的な要素が結構ある問題でオススメ
#812 Dynamical Polynomials - Project Euler
数学パズル好きには刺さる問題だと思う
A
#450 Hypocycloid and Lattice Points - Project Euler
いかつい式が出てきてもきちんと式変形で条件を整理するのが重要
#459 Flipping Game - Project Euler
人によってはC以下かも
(1:1:1)を作れる条件を整理するとよく見る形に
#489 Common Factors Between Two Sequences - Project Euler
計算できる形に式変形する 制約は小さいので甘えよう
#494 Collatz Prefix Families - Project Euler
方針さえ引き当ててしまえば後はやるだけ というかそうでないと困る
#566 Cake Icing Puzzle - Project Euler
「こういう形で求めれたらいいな」的な雰囲気が出つつも計算量を落とすのは工夫がいる 実装はほぼ考慮しないとはいいつつこれは難しかった
#579 Lattice Points in Lattice Cubes - Project Euler
一応それぞれの要素は典型だから地力枠っぽいけど面倒そうな部分が実は全探索でよかったり 最後の最後に一捻りあったりで翻弄される
B
#344 Silver Dollar Game - Project Euler
この手のはまず実験 ただ実験だけで必要十分条件にたどり着くのは難しいのでちゃんと考察も必要
#415 Titanic Sets - Project Euler
典型枠 典型に帰着するまでがちょっと工夫がいる
#439 Sum of Sum of Divisors - Project Euler
これも典型だけど他に比べて1段複雑なのでこの位置に置いた
#502 Counting Castles - Project Euler
ゴリ押しゲーはゴリ押しできると気付くのが難しい 求める値が3つあるが大した問題ではない
#584 Birthday Problem Revisited - Project Euler
典型っぽく見えて雑にやるとオーダー増える 一応PCぶん回しを考慮するとC
発想の似た問題がAtCoderにあるがそのままではないのでこの位置 素で思いつくのは少しむずかしい
C
#331 Cross Flips - Project Euler
着実に考察する
#483 Repeated Permutation - Project Euler
テクニックとしてはかなり面白いと思うけど露骨な類題があるので…
#484 Arithmetic Derivative - Project Euler
典型枠で実装も軽い PCが壊れたときに解法が思いついたのでネカフェで実装して提出した思い出がある 100%最易かも
#495 Writing $n$ as the Product of $k$ Distinct Positive Integers - Project Euler
完全に典型枠になってしまった感じではある
#559 Permuted Matrices - Project Euler
競プロ的にはこれも典型か
総評
この表を作って改めて100%の問題を全部見た感想
- 763が考察の質・量で頭一つ抜けてる。763と780は(約2年を要して)solved数が最近ようやく100を超えたけど、763は純粋な難しさ由来としても780は考察すら諦めた人がほとんどじゃないかと思う。ただ解法を導くのはそこまで難しくなく、過大評価気味
- 400番台前半は今では(Eulerで)ド典型になっているやつもあって過大評価気味
- 494,566とかは他所でまず見れなさそうな問題で凄い
- 700番台以降とかは難易度は高いけど、ARCとか大学有志コンのボスとかでギリ出そうではある
- 「式変形してしまえばあっさり」的な問題が多く、やはり問題の見た目で惑わされずにしっかり手計算で考察することが一番重要
