3月終わり! 大学を卒業した．
21(木)
ABC 061 D Score Attack: コストを反転すると負辺のある最短路問題になる．
Nに関するループ検出を行えばよく，これはベルマンフォード法を少し書き換えることによって$O(VE)$でできる．
こういう基本的なアルゴリズム等の書き換えがサクッとできるといいよね．
submission
ABC 060 D Simple Knapsack: $dp(i,k,add):=$$i$個目まで考慮して，$k$個選択し，重さの和が$kw(0)+add$のときの価値の最大値とする．
これによって$w$の情報を小さくもてるので，$O(N^3)$で解ける．そろそろchmaxを導入した．
submission
ABC 059 D Alice&Brown: 実験すればわかる． submission
ABC 058 D 井井井 / ###:
式にすると$\sum_{a<b}(Y_b-Y_a) \sum_{i<j}(X_j-X_i)$ となる．
それぞれのsumについて何回+,-になるかを見ると$2i+1-N$回なので全体で$O(N)$で解ける．submission
ABC 057 D Maximum Average Sets: まず，大きい方から貪欲に取っていき，小さいものが混じると平均値が下がる．
maxの値がA個以上ある場合は選択数について$\sum_{A≦i≦B} comb(cnt(max),i)$となる．そうでない場合はだいたいA個使うことで最大値となる．
A個ギリギリになる値を$a(i)$として，A個までに含まれる最小値の個数について$comb(cnt(a(i)),inAcnt(a(i)))$が組み合わせ数となる．
雑な考えでWAを出した．大大大反省．
submission
ABC 056 D No Need: $a(i)$を使って$K$以上になるようなものが存在すれば必要な数といえる．
→$a(i)$を使わずに$[K-a(i),K)$となる数を構成できるかを判定できれば良い．
愚直なdpを考える．$a(idx)$を使わずに，$dp(i,s):=i$番目まで見て，和が$s$となるような$a$の選択が存在するか?とすれば$O(N^2K)$で解くことができる．
戻すdpをすれば良さそうだが，modで戻すと復元に失敗しそう．
$A,a(i),B$という区間に分け，A内で順にdp配列を毎回$O(K)$で足して構成する．
ここで問題は$a(i)$を使わずに$[K-a(i),K)$となる数を構成できるか，であったためAの添字$s$について$[K-a(i)-s,K-s)$となる数が1つでもBの中で構成できれば良い．
B側でもあらかじめdpをしておき，区間内に数が存在するかを高速に見ることができればよい．これは累積和で$O(1)$でできる．
よって$O(NK)$でこの問題を処理できる．
submission
22(金)
ABC 055 D Menagerie: 初期状態は4つしか存在しないので，適当につくって正しいかを全部見れば良い．submission
ABC 054 D Mixing Experiment: $dp(i,a,b):=i$番目までみて，成分のうち$a(g),b(g)$含まれる薬品の最小値として解く． submission
ABC 053 D Card Eater: $cnt(a(i)) \space mod \space 2$ が1ならキレイに1枚にできる．
そうでない場合位，2枚残ることになる．偶数個このセットがあればちょうど過不足なく消せるため，解ける．
submission
ABC 052 D Walk and Teleport: 隣接要素でしか移動しない．AかBの移動のどちらがコストが低いかを見れば良い． submission
ABC 051 D Candidates of No Shortest Paths: 最短路を実際に構築して，辺が最短路を構築しているかをcheckすれば良い．辺が疎なときはワーシャルフロイドではなくダイクストラの方が良い． submission
23(土)
Q#をやり始めた． ゲートの式と可能/不可能な動作をまとめ中…
24(日)
Q#その2をやった．
ABC 122 D We Like AGC: AGC,ACG,GAC,A_GC,AG_Cという状態を含まなければ良い．
これは末尾を区別するために終端3文字を記憶しておけばできる．$dp(i,a,b,c):=i$番目まで見て，末尾がabcとなっている状態数
として，遷移させれば良い．
状態数が少ないので行列累乗もできて，$N≦10^{18}$でも解ける．
submission
25(月)
卒業式 私服で行ったら浮いた 悲しい
26(火)
RA
27(水)
RA
28(木),29(金)
なんか疲れてしまったので寝たり本を読んでいた．
30(土)
ライブラリの整備をした． 古いものは書き直した．そこそこ統一感がでてきていい感じ．
31(日)
AOJ 2886 対空シールド: $M$個目以外について考える．愚直$O(NM)$だが，二次関数のパートは独立して扱うことができて，先に区間に二次関数を足してから同時に扱うことができ$O(N+M)$で処理できる．
$M$個目の置き場所について考える．が難しい．
そこで最小値の最大化という言葉から二分探索を連想する．あるスコアを達成できるか？
という問に答えることができれば問題を解くことができそう．
あるスコアを達成できる→$N$までの全ての$i$について同じ置き場所$X$が存在する
と言い換えることができるので，各$i$についてスコアを達成しうる連続した$X$の区間について重複する場所があるかをチェックしていく．
$O(M+Nlog^2N)$で解くことができる．なんか定数倍が重い…
submission
今年の目標達成度の確認
もう3ヶ月経ったのね．．．
- 競技プログラミングRating +400
- +100もしてない
- コンテストで賞金を得る
- 今年も得たい…
- 1200AC
- 👍これはできていそう．手でカウントするのを辞めたのでgithubだけが頼り．
- Kaggleに参加
- まだ．サンタに託す．
- このページの更新
- 👍してるね
- 新しいプログラミング言語3つ
- 👍Q#はカウントされますか?されますね．今はGoの本を買ったので研究室で使っていきたい．
- 英語
- 👎やってない．やろうね
- ICPC
- 👎AOJICPCを埋めるシーズンになってきたけどやってない
- 筋トレの継続
- 👍月木だけに変更したけど続けている．
- ISUCON学生枠で突破
- SQLの高速化についてまとめたりまとめなかったりしている．普通にISUCONの過去問やったほうが良さそう．
- 就活
- 4月にインターン申込み締切があるので出していきたい．(出すのはタダなので)
- なにかしらのOSSにpullrequestを出し、mergeされる
- そんな気力はない…でもやりたいね
- 指数時間アルゴリズムpdfを全部読む
- 👎読んでませんが やっていきたい
- nand2tetrisをやる
- そんな気力はない…でもやるぞ
- 積読の消化
- 👍10冊ぐらい読んだ．いつもはインターネットばかりだなあということに今更気がついた．
- なんか暗記系のことをする
- 👍やってない，脳がもったいないのでやろうね．
目標達成が具体的じゃないやつが多いね．
ZenHubとGitHubIssuesで全てを管理しているので具体的なものに変更した．
4-6月の成長が楽しみだね．