平均 平均を引いておき和の条件に変換するテク 例題 例題 平均の最大化・・・平均を決め打つ 桁和 繰り上がると8減る 閉路 例題 例題 変化点だけ考えるテク 例題 幾何で交点や端点だけ考えるやつ 問題の条件を緩めるテク 例題 例題 意地悪な問題文 例題 例題…

この記事はこのスライドの受け売りなので, ちゃんと知りたい人はこっちを読んでください。 はじめに ゲーム系の問題は以下の三つに大別できます。 後ろから探索 grundy数を計算 adhocな必勝法を見つける 順番にみていきましょう 後ろから探索 単純にゲーム木…

最近Atcoderの青difficulty問題を解き切ったので、それに絡めて記事を書いていこうと思います。初回は半分全列挙についてです。半分全列挙はその名の通り半分だけ状態を列挙する方法です。これだけだと何のことかわからないと思うので、例題を用いて考えてみ…

二分探索 pairs snuke the wizard nearest card game decrease sports festival 食塩水 高橋ノルム君 高橋君ボール 壁抜け 細長いお菓子 DP payment swap and flip balanced path common subsequdnce we love abc mixing experiment 徒競走 経路 塗り絵 1 難…

最近Ted Chiangの"Story of Your Life"を読み終えました（原著で読んだら死ぬほど時間かかった）。色々調べたら「サピア＝ウォーフの仮説」というのが出てきたのでちょっと書きます。 サピア＝ウォーフの仮説は認識、思考は言語に強く依存するという仮説です…

UnionFindはrootで各集合を代表させているので、root = U.find(a)で色々やる。 独立集合の数 a == U.find(a)なるaの時のみcnt+=1する 集合のサイズ U.find(a)の時のsizeを取得

競プロで題材にされがちな「木」についてメモしておきます。 木の性質 閉路のない連結グラフ DAG 木の用語 木の直径 もっとも遠い頂点間距離 任意の頂点を一つ選び、そこからもっとも遠い頂点を見つける。その頂点からまたもっとも遠い頂点を見つけると、そ…

負の剰余 -15%7 = -1とか-8/3 = -2になる（絶対値の剰余に符号をつけているらしい）。 そこで、あまりは((a%b)+b)%b商は(a-((a%b)+b)%b)/bと書く（もっといい方法がアリそうだが...）。 初期化 変数を初期化しないと死ぬ