俺グラフが好きだ
はじめに
俺，グラフが好きだ． 自分の気持ちに嘘はつけない．
俺と，付き合ってくれないか
有名じゃないものでシンプルで面白いものをまとめたい気持ちになった
できること
DAG，ある辺を除いた時にsからtへのパスがまだ存在するかクエリ
なるほど
— SSRS (@SSRS_cp) 2021年9月30日
乱択をしてしまうのが一般的な気がします (トポロジカルソートして、各頂点 v について s から v のパスの個数と v から t のパスの個数を適当な数を法として計算して、
クエリの辺 (v, w) に対し s から t のパスの個数と s から t のパスの個数で辺 (v, w) を使うものの個数が等しければ YES、等しくなければ NO と答えます)
— SSRS (@SSRS_cp) 2021年9月30日
頂点に重み，S-Tパスでxor最大化
これかなり面白かった https://t.co/ywQaNDovoH
— 熨斗袋 (@noshi91) 2020年10月15日
2人で最短路，2人目はコスト無料
3選択肢の燃やす埋めるが出来る時がある
最大流，ある辺を反転したときに流量が増えるか
フロー流して使ってない辺，残余パスでグラフを作る． 終点から逆辺で辿り着ける箇所，始点から辿り着ける箇所を調べておいて，辺を反転させたときにS->Tが到達可能になればそこで流量が増える．
タイトルに書いてないが，流量が全部１じゃないときに同じように解けるのかはあんまり考えてない． 下の問題は流量全部1
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2594
道に種類があり同一種類なら無料で使い続けられる．(鉄道の運営会社)
今解いています．
普通に解けました．
集約する頂点を作ってやればよいです．別に難しくありませんでした．
鋭意追加をします
シャンプーうめぇ
おわりに
こういうの，先に記事を用意しておいて，出てくるたびに追加するようにしておかないと漏れる
忘れたくない 3
はじめに
人は忘れる
~ 2021/09/26
めもたち
実は累積和のSWAP
P_i-1 += P_i
P_i = - P_i
P_i+1 +=P_i
実はこれ累積和のSWAP．
他にも隣接要素に関して操作を行い，最小回数，操作パターン数などはは累積を考えてやると良いかもしれない
これも類題？わからない．まだみてない
頂点に重みついていて，ウォークでxor，最大化
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日 |
| 給与 | とても良い | すごく良い |
イA
流れ
オンラインなのでPCや書類を送ってもらって，あとは頑張りました． 1つのチームに所属し，みんなでミーティングをして僕の介護をしてもらいました．
感想
- チームに所属し，社員さんと同様にミーティングをし，社員さんのミーティングも聞けるので，距離が近い感じがした．みなさんのやってることにすごく興味が出た．
- gitとかガッツリ使って，社員さんとかと同じ仕事の流れを体験してもらう，を大切にしているらしい．これ，すごく良いです．仮に入社とかできたら，のイメージが湧いた気がしています．
- 15日なので結構ゆっくりじっくりやれた
- ぶっちゃけ割とよくできたので満足度が高い
- 地方民の僕としては，オンラインで試行錯誤開催してくれようとしてくれているところに心うたれた．本当に今東京に行くのはヤバイ，周りの人にどう見られるかとか非本質がある．
イB
流れ
オフラインなので行きました．
大都会新宿で人の心を失いかけた時，高島屋の半額ウナギ弁当に救われました．
感想
- 課題がかなり険しかった．イAでは「hogeという問題があります．解決する方法を考えて」みたいだったがイBでは「hogeがあります．なんかやってください」みたいなノリだった．
- やっぱりオフラインだから楽にコミュニケーションがとれるのはデカい．
- 社員さんが毎日かわるがわるコミュニケーションをとってくれるので会話の機会がめちゃめちゃ多い
- 社のフリードリンクとかフリーピノとかありがたい．一日に500mlペット5本とか普通に飲む人間なので．
- 東京マジで怖い．みんなよくあんなところで生きていけるな
雑
マジで競プロer超いた．観察した感じ，イAはマジでヤベェ．暖色が当たり前に要る．屈強すぎてさすがにビビった．
やらかしたこと
- オンラインの方，pcのパスワードを忘れ，書類を書いてある重要書類と一緒に送り返してイ2日目にpcに入れなくなる
- unsigned long をprintする時にprintf("%ul", hoge);と書いていて，数値の末尾に小文字のエルが入ってしまい，しばらく気づかず，数値を1桁多く観察していた．正しくはlu
- オフラインの方，ホテルで自販機行こうと思ってYouTube見ながら廊下に出たらインキーした．バカ
まとめ
しうかつに対する漠然とした不安，みたいなのが少し和らいだのが一番良かった．
後，会う人会う人みんな優しい．僕みたいなカスに時間をさいてくれてありがとう．
なんか頑張って生きていこうという気持ちになった．
忘れたくない 2
はじめに
人は忘れる2
2021/9 ~
2回目無料，最短路問題
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
周期tの文字列
任意の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のメモ
研究したくねぇ
誰か僕の修論書いておいてください．
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に入れなくなった
イ先「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座標で当該範囲がどこになるかを二分探索し，累積和してあげる．
実装
https://mugen1337.github.io/procon/DataStructure/RangeTree.cppmugen1337.github.io
わかりやすい資料
verify
発展
更新可能にできるか
X座標のみ前もってわかっていればY側は更新可能にできたりすると思います． ソートされた配列ではなく平衡二分探索木などをのせてみます． 昔書きましたが，ゲロみたいに重かったのでここではあまり触れません
Fractional Cascading
工夫することでクエリあたりO(logN)にできるようです． 昔書いてみましたが，定数倍の関係で競プロの問題ではそこまで速さが変わらなかった記憶があります．そんなことないよ！っていう例があれば知りたい
あ
なんか他にも僕の知らないこといっぱいありそう
おわりに
割と仕組みわかりやすくない？ そのわりにはつよくない？ そうでもない？ そう...
