3月2期，全然精進できていない…
11(月)
ABC 090 D Remainder Reminder: [1..N]の数字を異なる mod bで計算したとき，連続した区間が登場する．その大きい区間のK以上，余った区間のK以上をそれぞれO(1)で求めればよい． submission
ABC 089 D Practical Skill Test: mod Dで独立した累積和を作れば良い． 最初L≦Rでないと思っていたけど，結局解ける．順方向と逆方向の2つを作ればよいだけ． submission
ABC 088 D Grid Repainting: count(‘.’)-(最短距離+1)が答え． submission
ABC 087 D People on a Line: 制約条件からPotentializedUFで解ける．submission 当時はグラフで解いていたっぽい．
ABC 086 D Checker: 4K x 4Kの領域に対して，2K x 2Kの市松模様を動かすみたいなことをすればよい． submission
今日は研究もストレッチも筋トレもしてけど競プロは満足にできなかった．全部やるのは難しい…
12(火)
ABC 085 D Katana Thrower: AB同時に降順にgreedyにとって良い．AならHPがなくなるまで攻撃し，Bなら1回だけ攻撃をすることで達成できる．これは操作が可換であるから． submission
ABC 084 D 2017-like Number: 素数表からlike2017数を記録し，これを累積和で持てば高速にクエリを処理できる． submission
ABC 083 D Wide Flip: ““K以上”“の区間をflipできるので，K,K+1の区間flipでk+1番目の文字を任意にできる．したがって|S|/2以下のKでは常に構築可能．あとは左右からの重複区間が全部同じかを判定し，同じならそのKを答えの候補にすれば良い． submission
ABC 082 D FT Robot: dp(x,y,dir)みたいなのを考えるとだいぶ疎だし無駄．ところでX,Yは90度回転の命令で独立して操作していることになり，それぞれに影響を与えない．dp(x):=xに到達可能 としてX,Yそれぞれのdpをすれば良い．最初は+Xであることに注意． submission
ABC 081 D Non-decreasing: 全部正であるとする．このとき，axをa{x+1}に足すことでa_x,(a_x+a{x+1})となり必ず昇順になる．一部負であっても，最大値が正ならこれを全ての数に加算することで全部正となる．全部負あるいは絶対値の最大値を持つ数が負のときの議論も同様にできる． submission
ABC 080 D Recording: 境界の条件が謎．各チャンネルの使用区間を求め，合算すれば良い． submission
ABC 079 D Wall: 色iからjへの書き換えについて最小コストはワーシャルフロイドで簡単に出せる． submission
ABC 078 D ABS: O(N^2)再帰を書けばよいが，末尾で引数からの情報をもとに値を返す実装にするとO(N^3)になりがち．このような実装もサクッとできるといいね．f(p,player):=!playerがpを選択し，playerが最適行動を行った際のスコア．f(p,prev,player)とかにしてメモも同様にしがち．これは最後にpがNのときにしか使わないのだからprev,playerをメモするのが良い?? submission
13(水)
ABC 077 D Small Multiple: 無理そう∧最適が連続しないのでdpっぽい．dp(i):=生成された値がmod Kでiとなるときの最小コスト とする．桁dpぽい遷移を考えて遷移する．dp(0)が答え． submission
juju_62qにdockerを教えてもらった．研究再現にはdockerつかってたけどあんまりやる気がなかったので勝手に焚き付けられた．
14(木)
情報処理学会(福岡)で発表．なんとか賞は学会会員にならないともらえないらしい．
発表を見てくれていた2社からインターンと新卒のスカウトを受けた．
無限人知っている人が来てた．世界狭すぎ．ご飯をもりもり食べた．
15(金)
起きて筋トレした．全国どこでも筋トレできるエニタイムフィットネス便利…
新概念コンテストでc7c7さんが1位を取ったらしいので見に行った．すごい．
もりもりご飯を食べて帰った．
16(土)
docker-composeをたくさん書いた．すごい便利．触ってからじゃないと理解できないので触るの大事.
ABC 076 D AtCoder Express: 先に区間の両端の最小値を出す．これは両側から最小値を見ていけば良い．あとは区間内でv(i)を超えるかをみたいが結構面倒．v(i)がないものとしたときは中央or端の頂点で縦に分割して台形の和とすることができる．v(i)があるときは削られる三角形を求めれば良いことになる． submission
AGC031に参加 (480th). Aがわからないので飛ばした．Bは少し考えると重複しない区間の選択数なのでdpでできる． 意味不明を考えなかったのは良かったけど，すごく典型なので10分ぐらいで解きたい．
17(日)
.
18(月)
筋トレした以外の記憶がない(は?)
19(火)
RAでITベンチャー訪問へ． PFN・TierⅣ・bizreach へ行った．PFNはIOI人材が無限に吸収されているイメージがあったけど他の人も漏れなくヤバい人だけだった．
夜に大学の先輩であるおかづきさんと鍋をした．
久しぶりに会ったのに大学で一緒に問題を解いていたときのまま話せて嬉しかった．
あとQ#で来年はシャツを得よう！という話になったのでやっていきたい．
ABC 075 D Axis-Parallel Rectangle: $O(N^5)$が可能なので4点決めてその内部の点の個数を見る．submission
ABC 074 D Restoring Road Network: ワーシャルフロイドの確認っぽいことを確認すれば良い．$a(i,j)>a(i,k)+a(k,j)$なら間違っている．使われる辺は，$a(i,j)=a(i,k)+a(k,j)$のときa(i,j)はいらないと言えるのでそれ以外の辺の和を足し合わせれば良い． submission
ABC 073 D joisino’s travel: ワーシャルフロイドで最短路を決定してから$2^R$なり$R!$個の順路をみればよい．submission
ABC 072 D Derangement: だめな組を解消していく．端から進めていくとして進行方向のものとswapしたほうが回数を減らせるのでそうする． submission
ABC 071 D Coloring Dominoes: 状態遷移は一定なのでオートマトンを書けばよい． submission
ABC 070 D Transit Tree Path: 頂点Kを根として距離の和を求めれば良い． submission
20(水)
RAのITベンチャー訪問2. Google・ABEJA・WHILL へ行った．GoogleはITベンチャーなのかという気持ちになった．
ABC 069 D Grid Coloring: ヘビ．submission
ABC 068 D Decrease (Contestant ver.): 一様操作を行うと$N$回消費して全部$-1$になることが分かる． N=50として，(50,48,48,…,48)なら1回なので，全部の値を$49+K/N$として，$N-N\%K$個だけ$N\%K$だけ減らして残りは$+1$すればできる． submission
ABC 067 D Fennec VS.Snuke: 相手の自陣地への侵入を拒む的な事を考えると，最短距離で相手の方へ近づけば，衝突点から手前は自分の色にできる．よって自分が塗ることができる条件は$d(me,i)≦d(you,i)$である． submission
ABC 066 D 11: 区別すればよいのは重複している数字を1つ選ぶ時．$comb(N+1,k)$のうち，重複している数字の間以外の区間の数のみを使用していてかつ，重複している数字を1つだけ選ぶと区別できなくなる．これは$comb(N-(重複している区間の幅),k-1)$である． submission
ABC 065 D Built?: 最小全域木をつくる．xでsortされている場合にx1-x3の辺をつなぐならばx1-x2,x2-x3でつないだほうがよい．こうすることによってyでより小さいコストで辺を張ることが可能かもしれない．よってx,yでの隣接辺を$2N-2$本準備して最小全域木を構成すれば良い． submission
ABC 064 D Insertion: バランスが取れていなかったら補完すれば良い．submission
ABC 063 D Widespread: $X$回で倒せるなら$X+1$回でも倒せる．したがって二分探索可能．$X$回魔法を使うならすべての敵に$BX$のダメージを与える事ができる．あとは正のHPを持つ敵を$A-B$の攻撃を何回行えばよいかを求めて判定を行えば良い． submission
ABC 062 D 3N Numbers: 先頭$i$個のうち$N$個使った際の最大値，最小値を両端から求めておけば，$[N,2N)$でこれらを使用して求める値の最大値を取るだけになる． submission
大学の友だちにbuild-your-own-xを勧めたら喜んでいた．2人とも向いていそう．僕も埋めるのは好きなのでやりたい…
3月2期はあまり問題を解けなかったけど競プロ以外の学びがたくさんあった．
あとストレッチに慣れてきた．
おかづきさんと会ったらまた問題をたくさん解く気になれた．ありがとうございました．(やる気がどうこうじゃなくて息を吸うように精進してくれ…)