忘れたくない 3

はじめに

人は忘れる

~ 2021/09/26

忘れたくない - むげんのぶろぐ

忘れたくない 2 - むげんのぶろぐ

めもたち

実は累積和のSWAP

P_i-1 += P_i

P_i = - P_i

P_i+1 +=P_i

実はこれ累積和のSWAP.

Aizu Online Judge Arena

他にも隣接要素に関して操作を行い,最小回数,操作パターン数などはは累積を考えてやると良いかもしれない

No.1493 隣接xor - yukicoder

これも類題?わからない.まだみてない

K - Air Pollution

頂点に重みついていて,ウォークでxor,最大化

noshiさん

重み付き最大独立集合

重みないと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

F - Road Construction

一般グラフはへのさん,snukeさんのツイッターで議論されている

これは同じように一般グラフで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です.
 (a∨¬b∨¬c)∧(¬b∨¬c∨¬d∨¬e)∧(¬e)∧(c∨¬a∨¬b∨¬d)

和積標準形の形で,各節に肯定リテラルが高々1個のものです.

メモ

これは解けます.

仮に,肯定リテラルのみの節が1つもない場合を最初に考えます. この場合,全てのリテラルを0にしてやればいいです. 各節,否定リテラルが1つはあるので,そいつが1になってみんな幸せです.

じゃあ肯定リテラルが1つのみの節があったらどうするかです. この場合,そのリテラルを必ず1にしなければなりません. そしてその影響で他のリテラルを決定するかもしれません.  (a)∧(b∨¬a)∧(c∨¬a∨¬b) のような場合,a=1でなければなりません. このことから真ん中の節を考慮するとb=1でなければなりません. 同じようにc=1でなければなりません.

上で議論したことをふまえると,1にしないといけないリテラルをそうして,あとは全て0にしてしまえばいいんじゃないか,という気持ちになります. なんかそれでいいです.

なぜなら否定でも肯定でもいいなら否定にしておいて絶対に損をしないからです. 最初の議論的にそんな気がします.多分.

実装をします.

mugen1337.github.io

できました.

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わかんねぇ.紙観るか...ねぇわ」 始業時間を待って電話をかけ,イとかシステム担当者を数名呼び出して解決してもらう. 死にたい

ワクチンの予診票を忘れた

忘れた.咄嗟の機転でラボに立ち寄り印刷した. 実は会場でもらえたらしい. ただ汗をかいた

領域木の布教

はじめに

領域木はいいぞ

mugen1337.github.io

できること

二次元空間を考える.
重み付きの点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座標で当該範囲がどこになるかを二分探索し,累積和してあげる.

実装

mugen1337.github.io

わかりやすい資料

直交領域探索

verify

judge.yosupo.jp

発展

更新可能にできるか

X座標のみ前もってわかっていればY側は更新可能にできたりすると思います. ソートされた配列ではなく平衡二分探索木などをのせてみます. 昔書きましたが,ゲロみたいに重かったのでここではあまり触れません

Fractional Cascading

工夫することでクエリあたりO(logN)にできるようです. 昔書いてみましたが,定数倍の関係で競プロの問題ではそこまで速さが変わらなかった記憶があります.そんなことないよ!っていう例があれば知りたい

なんか他にも僕の知らないこといっぱいありそう

おわりに

割と仕組みわかりやすくない? そのわりにはつよくない? そうでもない? そう...

Link Cut Tree の get_root ヤバかった

Link Cut Treeを書いてみた

色んな人のプログラムをみて「へー」とか「ほー」とか言いながらつぎはぎして書いたらヤバイことが起きた

これ,それはそうだった.

頑張ってSplay木を深くまで潜ってrootを引っ張ってきたとき,splay木の形が一切変わらずに,もっかい同じクエリが来るとヤバイ!
それはそう

rootを見つけてきて,splay(root)をするとよくて,こうなると,splay木の形がイイ感じになるので,もっかい同じクエリが来ても,イイ感じの木を探索するので,大丈夫になる.

1つ気づいたこととして,布団の中でLink Cut Treeについて想いを馳せると,木のrootとsplay木のrootを混同して死ぬ.

起きて紙でしっかり考える