PE32

今回は計算量削減でかなり頭を抱えた。
愚直に回したのでは、超ハイパーウルトラアルティメットPCを組まない限り、
通常のPCでは終わらないようなとてつもない数の組み合わせを
試さなければならない。

寝起きにボーッとしていたらふと気がついた。
1～9の数字をそれぞれ必ず1度だけ使わなければならないので、
の式で、 となる。
（当然といえば当然である）

これをもとにループ範囲を制約して実装し、正解を出せた。

実装面でも少し苦戦。
最初に正解を出したコードでは1分10秒弱かかり、1分ルールを超えてしまった。
これは、Pythonのitertools.permutationsのような
長さ指定ありの順列取り出しのやり方が分からなかったので、
順列の重複を前提として、そのまま出た結果（積）の重複を
unordered_setで除くような実装だったためである。
順列取り出しのループの重複を除くよう実装し直したところ2秒で終わった。

PE31

力任せにループさせてカウントし、解いた。

PE30

どう当たりをつけて良いか分からなかったので、
9⁵あたりを最大として試しながら探索するよう実装した。

この当たりのつけ方で良かったのかどうかは謎。
(そもそも当たりをつけるタイプの問題であるのかどうかも…)

PE29

28に続き、力任せに集合に放り込んで解いた。

Pythonでは数行の実装で非常に簡単だったのだが、
C++で書こうとしたときに多倍長整数のような実装をしなければならず、
自力実装を諦め、boost::multiprecision を利用して実装した。

std::unordered_set<boost::multiprecision::cpp_int> にうまくinsertできなかったので、
std::unordered_set<std::string>にcpp_int.str()してからinsertして数えたのだが、
どうやればよかったのだろう。。。

PE28

番号順に解いていこうとしたが、26と27の解法がわからず飛ばすことにした。
（先が思いやられる。。。）

今回解いた28は、見たままの通りにマトリックス構造を作って力任せにやって解けた。
これ以外の方法もありそうだが思いつかない。

PE最初の25問を終えて

2年前くらいに、あるきっかけでProject Eulerにアカウントを作成した。
このブログもその頃作ったと思う。（たぶん）

最初の5問も解いたか解かないかくらいでつまずいてどちらも放置していたが、
ここ数日少し頑張って解いていたところ、今日最初の25問+αまで解けたので、書く。

これからも今回のように一定のマイルストーンに到達できたときや、
うまくいったときに書いていこうかと思う。

また、Project Euler以外にはAtCoder Beginner Contest に参戦することがある。
こちらについても書いていきたい。
（ただ、事前に開催メールが届くにも関わらず、その時間を忘れてしまう… orz）

いずれも「上には上が…」なんて言えるレベルにすら到達してないが、
悩んでうまくいったときに備忘録的に書いていきたい。