gccをソースからインストールするという経験を積んだ。
とりあえずガイド通りにやったら「gengtype-lex.cc」というソースファイルがないという。flexというパッケージをインストールしたら良いらしいのでインストールしてみたら解決した。
解決したのはいいがしかし、ライブラリでもヘッダでもなく「ソースファイル」がない、しかもそれがパッケージのインストールで解決するというのがなんとも奇妙に思える。そこで調べてみたところ、flexというのはソースファイルを自動生成するような目的のコマンドらしいということが分かった。これで得心がいった。本来flexで自動生成されるはずのソースコードが生成されなかったためにエラーが出たのだ。
ビルドには3~4時間かかった。あまりちゃんとは計測していないがなかなかの長さだ。面倒だったが面白い経験だった。
ビルドしたgccでh2oをビルドしようと思ったのだが、そこでも問題が出た。
CMakeがビルドした方のgccを使ってくれない。
- CCとCXXにパスを指定する→だめ。なんで？
- 古いgccをアンインストールする→新しい方を検知してくれた。しかしいくつかの必須ライブラリも消してしまったようで、ビルドが通らない。だめ。
- /usr/bin/ccと/usr/bin/c++を置換する→成功。CMakeはデフォのコンパイラをこのパスからとってくるらしい。
/usr/bin/ccはシンボリックリンクだったのでupdate-alternativesで指す先を変えた。しかし/usr/bin/c++は実行ファイルだった。どうするか悩んだが、最終的に/usr/bin/c++を/usr/bin/c++-oldに改名し、/usr/bin/c++はupdate-alternativesでシンボリックリンクを置いた。あまりよろしくないやり方な気がするが、まあ問題が起きたらそのときはそのときで。
今日解いた競プロの問題。
AGC051-A 自力AC。天才っぽい問題だが、ちゃんと考察したらなんとか通った。見た目よりは優しい問題。
実際に図を書いてちょっと考えると、ある一辺に沿って並べられるのは「正方形のみ」か「正三角形のみ」しかありえないことが分かる。なおかつ、「正方形のみ」の辺の隣は「正三角形のみ」の辺でないといけないことが分かる。逆も同様。ということは、ある12角形があるときに辺に沿って1段階敷き詰める方法は2通りしかないことが分かる。
12本の辺を交互に「偶数辺」と「奇数辺」のような感じで分類すると議論がしやすい。
1段階敷き詰めると、三角形を敷き詰めた辺の長さは1短くなり、正方形を敷き詰めた辺の長さは保たれる。つまり、「偶数辺の長さだけを1減らす」敷き詰め方と「奇数辺の長さだけを1減らす」敷き詰め方があると言い換えられる。(偶数辺長, 奇数辺長)=(d, d)なる12角形の敷き詰めパターンをDPか何かで求めれば良さそうだというのが見える。
敷き詰めパターンの数を偶数辺長・奇数辺長の関数として$f(a,b)$と表すと$f(a,b)=f(a-1,b)+f(a,b-1)$になる。これを解けばいい。
なお、(偶数辺長, 奇数辺長)が(n, 0)や(0, n)なる12角形は正6角形だ。これのパターンは1通りになる。(全て正三角形のみ)
これを把握すればとりあえずDPで答えは出せるが$O(d^2)$なのでTLE。しかし表を書いてみれば分かる通り明らかな二項係数だ。ということで$f(d,d)=_{d*2}C_d$となる。
回転して一致するものは同一と見なすことに気を付けて、最後に÷2すればAC。気持ちよかった～。
今日はぐっだぐだな一日になってしまった。タスクの優先順位が付けられていない。
今日摂取したコンテンツ。
https://ja.wikipedia.org/wiki/ローラン多項式
Categories: 未分類