ちなみに記事のタイトルは「この問題で私が学んだこと」という基準で決めているため、実は解法に必ずしも関係があるとは限りません。atcoder.jp まず、数列は以下の三つに分けられる。 ①前半となるN個 ➁後半となるN個 ③抜いたN個 全ての①は必ず全ての②の前に…

atcoder.jpまず、列を0(直立)の領域と1(逆立ち)の領域に分けます。 この領域は必ず交互に並んでいるので、ある状態にしたい場合に0の部分を選択してひっくり返した時が回数が最小です。（これって自明でいいのかな…？） のでK個の直立グループをひっくり返し…

機械学習>(検索よけのためここは後ほど記入する)という東大前期教養課程の授業を履修するのでどのような授業なのかメモしていく もちろん板書をそのまま載せるのは著作権的にまずそうなので、板書を見ないで思い出したり調べたりして書く。 一日目、二日目 …

atcoder.jp電車の中で考察するとだいたい終わるし時間が潰せるので良い。直線によって区切られている小さなマスについて、そのマスが長方形の中に含まれる回数は、縦横それぞれでその範囲が長方形に使われるかを なのでまず一方の方向について考える。 実験…

todoistと同期できるスケジューラー兼トラッカーみたいなものが欲しいので、プログラミングの勉強がてら作ります。で、ついでにslack botの作り方を学んでいこうと思いました。 目標 作っているうちに変わってくると思いますが、大まかには ・todoistとスラ…

atcoder.jp朝の電車の中で10分くらい考察して、あとは実装した。 大切なのは「ある2箇所の動物が決まると、その次の動物も決まる」と言うこと。 まず、可能かどうかを調べる。場所二つごとに羊と狼の組み合わせ（通り）を要素としてunion-findを行い、一周し…

atcoder.jp400点に飽きてきたのでたまには500をやるか、と思って簡単そうなのを選んで解いた なんでこれ500点なの…？300点くらいでは #include <stdio.h> #include <stdlib.h> #include<math.h> #include<algorithm> #include<vector> #include<queue> #include<string> #include<set> #include<cstring> using namespace std; #define re</cstring></set></string></queue></vector></algorithm></math.h></stdlib.h></stdio.h>…

atcoder.jp 簡単な問題が続いている… 通る頂点が8個と少ないので、この8つの頂点からの各頂点への最短距離を求めておく。 まあ全頂点間でも間に合うしめんどくさいのでそうする。ワーシャルフロイド（計算量） あとは8!通りの通り方についてこれを使って合計…

atcoder.jpオリ合宿のバスの中で。ただのダイクストラ。五分。 #include <stdio.h> #include <stdlib.h> #include<math.h> #include<algorithm> #include<vector> #include<queue> #include<string> #include<set> #include<cstring> using namespace std; #define rep(i,n) for(int i=0;i</cstring></set></string></queue></vector></algorithm></math.h></stdlib.h></stdio.h>

atcoder.jpえ〜、なんかすぐ出来た。括弧列であることと、(の個数と) の個数が同じで、さらに前から部分列を取得したときその部分列において( の個数が )の個数以上であることは同値である。 また、追加する個数が同じとき、(は先頭、)は末尾に持ってきても(…

atcoder.jp問題を見てダイクストラ法ですかねと思い、ダイクストラ実装…してから気づいたけどよく考えたら最長経路問題だった。部分構造最適性が成立していないのでダイクストラ法みたいに計算量少なくは出来なかった…（色々考えた）辺の値全てに-1をかける…

atcoder.jp前回のやつより簡単だった（ただのナップサック問題で考察がほとんどいらないただのDPだったので） 何個選ぶか決めた時、価値の平均値が大きい順は価値の合計値が大きい順と同じ。合計を保持するDPを作って、最後にそれを個数で割って平均値を出し…

ところでD問題って（n年前の感覚としては）普通に解けるような感覚でいたけど結構厳しい 精進をn年もサボっていたせいですねatcoder.jp二通りのやり方で解きました。半分全列挙全探索すると2^40かかる。 半分全列挙すると2^21かかる。難しいこと考えずにこれ…

コンテストの時だけ思い出したように進捗を生むのも良くないと思うので、精進をしようと思います。なお、証明とかがガバガバかもしれませんのでご了承ください。現在の私にとっては、苦手だったり勘違いしなければコンテスト時間内に、そうでなくても時間を…