1(月)
競プロライブラリとスニペットが別の実装になっていたりするのが最悪すぎたのでライブラリからsnippetを自動で生成するやつを書いた． ただ書くだけじゃつまらないのでテンプレートエンジンぽいのを作った． 簡単に実装を拡張できるようになって良い．
よくコードにある/// {{{の意味が分からなかったけど，あれはvimの折りたたみ機能らしい． 識別子だということは分かるけどそれはvimを使ってかつ/// {{{を使わないとわからないので驚いた．
ライブラリにはsnippetとtestを書いて，snippet呼び出しはtest以外の部分を持ってくるようにしたのでかなり便利．
2(火)
BinaryTrieを書いた．二分木系をたどるのは楽しいね．
研究室の新B4の人たちにAtCoderを布教したり研究室の説明をしていたら一日終わった．
3(水)
やっていくぜ！
ABC 050 D XorSum: OEISで$O(NlogN)$の求め方が書いてある．式を再帰的な形に変形するとメモできて，$O(logN)$でできる形に変形できる．
submission
ABC 049 D 連結: 2つのグラフの属する番号がわかればよい．それぞれUnionFindで番号をもっておき，そのペアの値が何個あるかを数える．数える部分はmapとかで適当にできる． submission
ABC 048 D An Ordinary Game: 両端の情報が大事かなあという気持ちになると，最後は2種類の文字しか残らない？というところまでは行く．わからないので実験すると規則がつかめる．
よくよく考えると最終状態のパリティが決まっているのだから，消せるものが分からなくても消せる個数のパリティは分かる．これは操作回数そのもの．
submission
ABC 047 D 高橋君と見えざる手: 差分が最大になる区間の数を数えれば良い．これは区間LRのカウント問題の派生なのでmapで適当にできる． submission
ABC 046 D AtCoDeerくんと変なじゃんけん: 二次元にプロットする．順番は好きに入れ替えるとして，グーの余剰の半分をスコアにすることができる． submission
ARC 002 D ボードゲーム: まず，左端にx，右端にoがある場合は先手からゴールまで最も近いものがある方が勝ち．
そうでない場合を考える．膠着状態に陥るまでの移動回数が多いほうが勝ちである．
各列[o..o..x..x]で区切ってそれぞれの問題を考える．
最近接のoxについて，間の点を2づつ詰めて良い．すると後ろに待機しているコマの移動数が増える．残りの間が1のときはこれでOK．
2のときは先に詰めた方がその部分ゲームでコマの移動数を増やすことができる．
複数のゲームが同時に行われるので(自分が増やせる数，相手が増やせる数)を最適な順番で取っていきたい．
これはよくあるやつで和の降順で貪欲に取っていけば良い．(交代はする)
submission
ARC003 D シャッフル席替え: 許容誤差が大きすぎるのでシュミレーションする．こういった問題は今はもう出題されなさそう． submission
(復習) AOJ 2335 10歳の動的計画法: 軸ごとに独立してカタラン数を求める．
ABC 078 D ABS: $O(N^3)$の末尾が固定引数であることに気づけば$O(N^2)$に改善できる．
久しぶりにモリモリ書いたけどバグらなくて良い．
一方で考察漏れがあるのは本当にきついので解いた問題量を糧にやっていきたい．
4(木)
ABC 045 D すぬけ君の塗り絵: $N*10$マスしか影響を与えないので1以上になる部分だけをmap等で保持する． submission
ABC 044 D 桁和: $b$が大きいときは存在しない場合が大半そう．$b≦\sqrt{N}$については全探索し，そうでない$b$進数の値は二桁なので$xb+y=N∧x+y=S$を満たす$x$について全探索したもののうち，$b$の条件を満たすものを探せば良い． submission
ABC 043 D アンバランス: 2or3文字以内の区間がアンバランスならそれを含む極大な区間もアンバランス．submission
ABC 042 D いろはちゃんとマス目: 組合せを分断された経路ごとに組合せを求めるだけ． submission
ABC 041 D 徒競走: bitdpをするときに遷移してはいけない組が与えられている．これをチェックして数えれば良い．昔の提出は賢い$O(N2^N)$でやっていた． submission
ARC 004 C 平均値太郎の憂鬱: 式変形すると$N=2\frac{X}{Y}+2\frac{M}{N}-1$になる． $\frac{M}{N}$は0から1に収まるので，値の範囲は大きく取っても+3まで．よって2$\frac{X}{Y}$から+3の範囲までの$N$について全探索すれば良い． submission
ARC 004 D 表現の自由: まず正負を無視すると，素因数ごとに独立して割り振ることができる．正負について考えると，配った$M$個の整数について，$M-1$個の符号を決めて最後の1個で辻褄を合わせれば良い． submission
今日はICPCの中継と問題を見ていた．codingとかチームの様子が見れて面白かった．
半分以上の問題をサクサク解いていて怖い．
東大金おめでとうざいます！
5(金)
ABC 040 D 道路の老朽化対策について: クエリの内容は$T>y$となるような$T$をもつ辺のみのグラフであり，これは$y$を降順にソートしておくことで連結成分のサイズを求めるだけの問題になる．連結成分のサイズはUnionFindで簡単に求められる． submission
ABC 039 D 画像処理高橋君: 白であった部分の周りのマスは白であったはずなので，ここを白で塗る． もう一度復元して確認すれば良い．syncioでWA出した．．． submission
ABC 038 D プレゼント: 二次元LISとみることができる．submission
ABC 037 D 経路: $f(i,j):=(i,j)$を最初の場所にしたときの移動経路の総和を求める関数，とする．無限に経路は生成できず，これは部分問題を解くことになるのでメモ化再帰をするだけで解ける． submission
ABC 036 D 塗り絵: 根付き木として問題ない．
黒-黒にならないように色を塗っていくことを考える．$f(v,p,c):=$頂点$p$から来て今頂点$v$を色$c$で塗るような組み合わせ数とする．この関数から呼び出される子の要素について，何度も同じ呼び出しをして色を塗っていくことになる．これはメモしてあげれば良い．
submission
ARC 005 D 連射王高橋君: とりあえず復元を考えずに最小の長さを求めたい．まず最初に分かることとして，0or1を常に使用することができるので9項あれば必ず最小値を実現できる．
9項同時に値を加算していく的なことができればなんとなくできそう．
また，それぞれの項は同じ長さとは限らないので項を徐々に減らす部分もありそう．
9項同時に扱うことで繰り上がり等も考慮する必要がある．したがって下からDPをする．
$dp(i,j,k):=$達成したい数字の上から$i$桁目について，$j$項の値を用いて，現在繰り上がってきた数の和が$k$である際のボタンを押す最小値，として$f(|price|,X,0)$を$X=[1,10)$について求める．
加算する数字は予めdp等をして，使える数字からk個選択してつくれる和みたいなのを持っておく．
復元パートはどうすればいいかというと，もう一度dpをたどる際に$subdp(j,k):=j$項で和を$k$にするために必要な値を予め使用可能な数字で作っておき，遷移ごとに復元していく．
項数が1か否かで場合分け，項数を減らす処理，復元の順番等でミスりがちなので要注意．
AVL木を書いたけど書き方を忘れたので書き直した．
6(土)
ABC 035 D トレジャーハント: 2つ以上の頂点に滞在する必要はない．適当な経路の移動時間を除いた滞在時間$t$について，$t=a+b+c+…$とする．スコアは大文字を得られる部分スコアとして$a*A+b*B+c*C+…$とできるが，$t$が一定なので部分スコアが大きいところに全振りした方が当然良くなる． ここまでわかれば経路の時間だけわかればよくて，これは普通の有向グラフと帰るための逆辺のグラフがあればできる． submission
ABC 034 D 食塩水: $K$個選択して，平均値を最大化したい．これは二分探索である集合$S$に対して$\frac{\sum p(i)w(i)}{w(i)}≧X$をみたすXが存在するかをみればよい．ある$X$でOKならそれ以下の$X$についてはすべて存在することになるので二分探索でできる．(というか平均値最大化or最小化はだいたい二分探索でできる) submission
ABC 033 D 三角形の分類: 幾何系の高速化は思考停止偏角ソートみたいなところがある．(本当か?)
一点についての偏角を2周分つくってソートすると，一つの辺を元にした鈍角，90度の角をつくる辺がどれだけあるかが二分探索で分かる．
鈍角三角形と直角三角形を数えれば鋭角三角形の数も分かる．
submission
ABC 032 D ナップサック問題: 半分全列挙+$dp(w):=$重さが$w$のときの最大価値+$dp(v):=$価値が$v$のときの$w$の最小値を実装する．
半分全列挙は検索パートのために重さの昇順にしたあとに，小さい方から価値も昇順になるように一部要素を削除する必要がある．
submission
ABC 031 D 語呂合わせ: グラフとかを書くけど難しいなあとなる．文字を決め打ちしたとしても長さを確認する部分でcheckを行わないといけない．
間違っている長さであるのにそれらの文字の構成を変えたところで無駄なのだから，先に文字の長さを決定して矛盾がないかを見たほうが効率が良い．
実際に$O(\sum text(i)*3^K)$である．
submission
ARC 006 C 積み重ね: DAGの最小パス被覆に見えてしまったのでフローで殴る． submission
ARC 006 D アルファベット探し: できる数が12,16,11の$i^2$倍したものであることに着目する．
8方向に移動したマスの合計値について，$i^2$でできるだけ割ったあとに3,1,11だけ余る．これで分類すると楽そう．
submission
CSA 086を解いた．
C: おもしろい
D: イベントをsetで頑張る
E: 区間幅を小さい方から上手に管理する 気合すぎるのでライブラリ化してもいいかもしれないね
7(日)
ABC 030 D へんてこ辞書: $k$が小さいときはシュミレーションをすれば良い．$k$が大きいときは閉路でぐるぐるする部分を省きたくなる．
$x$を閉路までの距離，$y$をループ数，$z$を残りの移動としたとき$k=x+loop*y+z$となる．$k=U+loop*y$とみることで$U$を先に求めてからループ部分を削減してシュミレーションをすればよい．
submission
ABC 029 D 1: 基本桁dpを書く． submission
ABC 028 D 乱数生成: 中央値と一緒の数が何回出るかをそれぞれ独立して数え上げる． submission
ABC 027 D ロボット: まず+-の列は圧縮できる．部分点は基本的なDPだが満点はDPでは無理．
+-で得点を得るために$M$を変化させようとすると影響する範囲は$M$より後にある+-であることが分かる．
影響する範囲についてより+が多い部分をsuffixに持つ$M$とそうでないものを半分づつ選択すればよく，これは貪欲にできる．
submission
ABC 026 D 高橋君ボール1号: 直線がなみなみしている関数のうち，100になる場所を1つでも見つければ良い．これは二分探索でできる． submission
ARC 007 D 破れた宿題: おもしろい．
まず初項を最小化したときに第二項を適当にすれば大きな公差が存在することが可能で必ずその初項に対する組は存在する．
したがって初項は決まる．あとは第二項を広げながら頑張る．
submission
8(月)
KUPC2018 M 整数と根付き木: binarytrie+segtree+eulertourっぽい．
根の回転は部分木加算の場合分けが増えるだけなのでOK．
範囲加算単一取得のsegtreeは、単一加算範囲取得のsegtreeの逆バージョンで取得を下からやるみたいにすればできる．
メモリの使用量がやばいのでbinarytrieの親ポインタを消して頑張ると900MBぐらいで耐えきれる．(yosupoさん)
無理な場合は時間を犠牲に整数をmod pで扱い，pの剰余ごとに扱うみたいなことをするとできそう．(beetさん)
submission
大学院の様々な手続きが面倒になってきたけどこういうのは最初だけなので我慢…
9(火)
ABC 025 D 25個の整数: 表を埋めるのと数字を昇順に扱いたいという気持ちになる．
bitdpで解決する．stateをマスの埋まった状況とし，nxstateはpopcount(state)+1の数である場所を埋めるとすれば良い．
埋める際は既にある数字の横に埋めると必ず条件を満たさなくなるのでこれだけを除けば良い．
submission
ABC 024 D 動的計画法: 二項係数の式変形をする． submission
ABC 023 D 射撃王: 高さ$H’$に到達するまでに何秒かかるかを見る．$H(i)+X*S(i)=H’$であり，それぞれの風船が$X$秒より前に割られればよい．
これは$X$を昇順にソートしてそれぞれの期限までに毎秒風船を割ることができるかをみることで判定できる．
この高さ$H’$に関する条件は単調であるため二分探索ができる．
submission
ABC 022 D Big Bang: 重心をもとに移動させる．あとは比だけわかればよく．これは適当に距離なり面積なりを取れば求める事ができる． submission
ABC 021 D 多重ループ: ““このプログラムの出力する答えは $1≦a1≦a2≦…≦ak≦n$ であるような整数の組 $(a1,a2,…,ak)$ の個数に等しい”” らしい．
重複組合せそのものなので$nCr(N+K-1,K)$で求まる．
submission
10(水)
ABC 020 D LCM Rush: まず実験をして規則性が無いかを確認するが無い．
諦めて式変形をすると
$\displaystyle
\begin{align}
\sum_{i=1}^{N}\mathrm{lcm}(i,K) &= \sum_{i=1}^{N}\frac{i*K}{\gcd(i,K)} \\
&= \sum_{g \mid K} \frac{K}{g} \sum_{\substack{1 \leq i \leq N\\gcd(i,K)=g}}i \\
&= \sum_{g \mid K} \frac{K}{g} \sum_{\substack{1 \leq gi \leq N\\gcd(gi,K)=g}}gi \\
&= K\sum_{g \mid K}\sum_{\substack{1 \leq i \leq N/g\\gcd(i,K/g)=1}}i \\
\end{align} $
であるから，結局$K$の約数$k$について$gcd(N/k,K/k)=1$を満たす$N/k$以下の数の和をそれぞれ求めることになる．
互いに素である部分が重要で，これらの個数を包除原理で求めるのと同様に和も求めることができる．
昔解けなかったので嬉しい． submission
ABC 019 D 高橋君と木の直径: 木の直径は端から端へ移動みたいなやつ．インタラクティブにするだけ． submission
ABC 018 D バレンタインデー: 女の人中心で見る．$2^N$の組から$P$人になるような選択をする．
男の子ごとに得点が追加されるので，降順にとっていけば嬉しさを最大にできる．
submission
ABC 017 D サプリメント: 要するに，各区間に異なる要素しか無いように分割をする総数を求める事ができれば良い．
$dp(i):=i$番目に要素を初めて食べるときのvalidな食べ方の総数とする．
これは異なる要素しか無い区間は常に連続しており，右端を伸ばすと左端は縮めるしか無いのでしゃくとり法の動きになる．
この際総和を保持することで区間和のdpができる．
submission
ABC 016 D 一刀両断: 切れた回数/2+1が答え．切れた回数とは線分の交錯回数なので幾何を書く． submission
01-10日はストレッチも筋トレも競プロの復習もたくさんできた． あと3日で復習終わりなのでAOJICPCとARC級をゴリゴリやっていきたい．