人は忘れる
~ 2021/09/26
P_i-1 += P_i
P_i = - P_i
P_i+1 +=P_i
実はこれ累積和のSWAP．
他にも隣接要素に関して操作を行い，最小回数，操作パターン数などはは累積を考えてやると良いかもしれない
これも類題？わからない．まだみてない
noshiさん
これかなり面白かった https://t.co/ywQaNDovoH
— 熨斗袋 (@noshi91) 2020年10月15日
重みないとO(1.hoge ^ N)とかの有名があるけど，重み付きだと次数1を必ずとってよいわけではなくなる．
半分全列挙解法なら問題なさそう．これもまだ詳しくみてない．ちゃんとやったら追記 G - Mixture Drug
ACPC全てを復習します
研究，お前邪魔だよ
友人たちがドタバタとインターンにエントリーシートを出しているのを見て，怖くてインターンを探しました．
AtCoderJobsから2個，普通に1個エントリーしたらJobsの方2個受かりました． AtCoder，お前しか信じられない
仕事内容，どこまで触れていいかわからないので，仕事内容には基本的には触れません． インターンの流れとかシステムだけに振れているので多分大丈夫です．
開発経験がないので，研究と競プロの合わせ技で勝つしかねぇと思っていたので頑張って虚勢をはりました．
後からわかったのですが，地味にコミュ力を評価してくれたところもありました． 接客バイトやりまくっていてよかった．
| イA | イB | |
|---|---|---|
| 形態 | リモート | 現地 |
| 期間 | 15日 | 5日 |
| 給与 | とても良い | すごく良い |
オンラインなのでPCや書類を送ってもらって，あとは頑張りました． 1つのチームに所属し，みんなでミーティングをして僕の介護をしてもらいました．
オフラインなので行きました．
大都会新宿で人の心を失いかけた時，高島屋の半額ウナギ弁当に救われました．
マジで競プロer超いた．観察した感じ，イAはマジでヤベェ．暖色が当たり前に要る．屈強すぎてさすがにビビった．
しうかつに対する漠然とした不安，みたいなのが少し和らいだのが一番良かった．
後，会う人会う人みんな優しい．僕みたいなカスに時間をさいてくれてありがとう．
なんか頑張って生きていこうという気持ちになった．
人は忘れる2
2021/9 ~
DAGで2人の最短路 -> TTPC-F
一般グラフはへのさん，snukeさんのツイッターで議論されている
https://t.co/KM2KTaRvlh
— heno (@heno_code) 2020年8月17日
リンク先は辺が2回目以降無料の問題なんですが、それを書き換えました。
dist[i][j]:=行きの現在位置がi,帰りの現在位置がj(帰りはt->sではなく逆順のs->tで遷移させたい)とすると、
・iとjをswapする(両側で同じi->j pathを通る)
・片側を1進める
・両側を同じ頂点に進める
これは同じように一般グラフで2人が最短路，街に訪れる際にもコストがかかるが，2人目はいらない https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1324
任意のiでs[i + t] == s[i]が成立するとき，周期tの文字列と呼ぶなら，条件の言い換えが可能で， s[i, |S|-t] == s[i+t, |S|]と言い換えられる．これは頑張れば割と普通に示せる．
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2711&lang=jp
誰か僕の修論書いておいてください．
Horn SATとは2-SAT同様，高速に解けるSATの特殊ケースらしいです．
のしさん教えてくれてありがとう
以下のようなSATです．
和積標準形の形で，各節に肯定リテラルが高々1個のものです．
これは解けます．
仮に，肯定リテラルのみの節が1つもない場合を最初に考えます． この場合，全てのリテラルを0にしてやればいいです． 各節，否定リテラルが1つはあるので，そいつが1になってみんな幸せです．
じゃあ肯定リテラルが1つのみの節があったらどうするかです．
この場合，そのリテラルを必ず1にしなければなりません．
そしてその影響で他のリテラルを決定するかもしれません．
のような場合，a=1でなければなりません．
このことから真ん中の節を考慮するとb=1でなければなりません．
同じようにc=1でなければなりません．
上で議論したことをふまえると，1にしないといけないリテラルをそうして，あとは全て0にしてしまえばいいんじゃないか，という気持ちになります． なんかそれでいいです．
なぜなら否定でも肯定でもいいなら否定にしておいて絶対に損をしないからです． 最初の議論的にそんな気がします．多分．
実装をします．
できました．
1にしないといけないところを1にして，残りを全て0にして最後に全ての節がtrueになるかをチェックして終わりです．
verifyはDashboard - The 2020 ICPC Asia Shenyang Regional Programming Contest - CodeforcesのCです．
査読通った論文の会議から次の手続きをしろと連絡が来てた． 10 Augustまでね．って書いて合って．August，10月か，と思って放置してたらボスから「お前大丈夫かよ．はよせい」とメールが来た． Augustって8月だったのか マジで申し訳ねぇ
イ先「PC貸し出したで．書類付で送った．そこにPWとか書いてる．社外秘も書いてるからPCセットアップしたら送り返して」 僕「うぇいよ～．(初日に送り返す)」
~2日目~
僕「あれ？PCにログインするPWわかんねぇ．紙観るか...ねぇわ」 始業時間を待って電話をかけ，イとかシステム担当者を数名呼び出して解決してもらう． 死にたい
忘れた．咄嗟の機転でラボに立ち寄り印刷した． 実は会場でもらえたらしい． ただ汗をかいた
領域木はいいぞ
二次元空間を考える．
重み付きの点N個を前もって与える．
矩形内の重みの総和クエリがO((logN)2)でできる．
簡単に言えば，二次元空間に広がる点がN個あって，矩形内の点数のカウントクエリがO((logN)2)だよ
嬉しい．
はい． Submission #19394286 - AtCoder Beginner Contest 174
配列vがある． そのうち，添え字が[i, j), 値が[l, r)のもののなんらかの総和，みたいなのが答えられる． たまにほしくない？
ABC202 - Eがやるだけ 問題概要は略． オイラーツアーしておいて頂点を並べて置き，xの値がこの並べたときのindex, yの値が根からの距離で領域木を構築しておく． 各クエリを処理するには[in[u], out[u]) * [d, d+1)のクエリを投げればオンラインで倒せる． in, outはオイラーツアーの時に作れるヤツ
https://atcoder.jp/contests/abc202/submissions/22805167
x座標を基準にセグメント木を構築するイメージ． セグメント木のノードはソートされたy座標を持つ． セグメント木のノードに訪れるたびに，y座標で当該範囲がどこになるかを二分探索し，累積和してあげる．
X座標のみ前もってわかっていればY側は更新可能にできたりすると思います． ソートされた配列ではなく平衡二分探索木などをのせてみます． 昔書きましたが，ゲロみたいに重かったのでここではあまり触れません
工夫することでクエリあたりO(logN)にできるようです． 昔書いてみましたが，定数倍の関係で競プロの問題ではそこまで速さが変わらなかった記憶があります．そんなことないよ！っていう例があれば知りたい
なんか他にも僕の知らないこといっぱいありそう
割と仕組みわかりやすくない？ そのわりにはつよくない？ そうでもない？ そう...
色んな人のプログラムをみて「へー」とか「ほー」とか言いながらつぎはぎして書いたらヤバイことが起きた
対象プログラム pic.twitter.com/JMz5AC88vL
— むげーーーーーん (@mugen_1337) 2021年4月24日
get_rootした後splay(root)しない
— むげーーーーーん (@mugen_1337) 2021年4月24日
(昨日みさわさんにヤバイと教えてもらった方) pic.twitter.com/YCNdSHlFX8
splay(root)をします pic.twitter.com/mCJuaP7WxR
— むげーーーーーん (@mugen_1337) 2021年4月24日
これ，それはそうだった．
頑張ってSplay木を深くまで潜ってrootを引っ張ってきたとき，splay木の形が一切変わらずに，もっかい同じクエリが来るとヤバイ！
それはそう
rootを見つけてきて，splay(root)をするとよくて，こうなると，splay木の形がイイ感じになるので，もっかい同じクエリが来ても，イイ感じの木を探索するので，大丈夫になる．
1つ気づいたこととして，布団の中でLink Cut Treeについて想いを馳せると，木のrootとsplay木のrootを混同して死ぬ．
起きて紙でしっかり考える