Quiz https://atcoder.jp/contests/abc151/tasks/abc151_f 参考 https://codeforces.com/blog/entry/23554 最小包含円・最小包含球 内容 中心を平均などで適当に決め、一番遠い点の方に少し近づける調整を繰り返す 計算量 O(N x R) R : 繰り返し回数（求めら…
Quiz https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_b AC https://atcoder.jp/contests/dwacon6th-prelims/submissions/9431139 解法 N=5の場合の順列（4! = 24通り）を全て描いて観察する 隣り合う丸の間（上記画像のアーチ）の…
Quiz https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp19Day2/problems/D 問題意図のみ説明 貪欲に（柱の角に向かって引く）取ればいいんじゃないの？と思ったが違った 画像のように、柱の上辺を交差するように引くと合計が小さくなる 解法 DP htt…
立命館大学(理系−全学統一方式・学部個別配点方式、薬学方式) (2020年版大学入試シリーズ)作者:出版社/メーカー: 教学社発売日: 2019/05/25メディア: 単行本 Day 1 (立命館大学) https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp19Day1 解説 http:…
目的 これってセグ木でできる？をまとめる 参考コードを探すときの高速化 モノイド 結合律 単位元 モノイドの例（随時追記） min max sum or https://atcoder.jp/contests/iroha2019-day1/submissions/5205846 タコヤキ https://atcoder.jp/contests/arc008/…
Quiz https://atcoder.jp/contests/past201912-open/tasks/past201912_k AC https://atcoder.jp/contests/past201912-open/submissions/9277571 解法 LCA Code // LCA set VV G; const int N_MAX = 150010; const int MAX_LOG_V = 20; ll depth[N_MAX] = {};…
図 9 14 1 3 5 110 24 21 34 5 3 の場合の図 (サンプル2) Quiz https://atcoder.jp/contests/abc149/tasks/abc149_e AC https://atcoder.jp/contests/abc149/submissions/9230235 解説 editorialより複雑なことをしてしまった気がするが、解けたので共有 全…
Quiz https://yukicoder.me/problems/no/225 AC https://yukicoder.me/submissions/408789 解説 編集距離そのものの問題 int dp[1050][1050]; i : sのi文字目 j : tのj文字目 までを一致させるための最小コスト としてDPで解く。O(N2) Code // 編集距離 cons…
説明 累積XORとは、累積和と同じように事前計算しておくことで範囲のXORをO(1)で求める方法のこと XORの性質 a xor a = 0 a xor 0 = a 上記を利用すると、A = a xor b xor c xor d xor e の値を持っていて c xor d xor e の値が知りたいときは A xor a xor b…
Code VV A(5, VI(5)); // 10x10で確保したくなった A.resize(10, VI(10)); for(auto a : A){ debug(a); } exit(0); Result [a]: {0, 0, 0, 0, 0} [a]: {0, 0, 0, 0, 0} [a]: {0, 0, 0, 0, 0} [a]: {0, 0, 0, 0, 0} [a]: {0, 0, 0, 0, 0} [a]: {0, 0, 0, 0, 0…
お得？ 桁DPは「知らなきゃ解けないけど、知っていればやるだけ」らしい 習得しておきたい 問題「D - 禁止された数字」 https://atcoder.jp/contests/abc007/tasks/abc007_4 AC https://atcoder.jp/contests/abc007/submissions/8900569 解法 // keta // sma…
Quiz https://atcoder.jp/contests/abc040/tasks/abc040_d AC (verified) https://atcoder.jp/contests/abc040/submissions/8891107 解説 editorialの通りですが、ポイントとしては「橋の構築」と「クエリ」を同じvectorに入れてyearでソートした後、yearの…
Quiz No.845 最長の切符 - yukicoder https://yukicoder.me/problems/no/845 AC https://yukicoder.me/submissions/405827 解法 // i : また訪れてない頂点フラグ // j : 現在地 // とした場合の最長距離 int dp[1<<16][16]; としてbit DP 以下、(間違った考…
Quiz https://atcoder.jp/contests/dp/tasks/dp_w 解説AC https://atcoder.jp/contests/dp/submissions/8814646 感想 論理はemtubasaさんの解説を参考 遅延セグ木はふるやんさんのを借りてきた いくつかパターンが書かれているから再利用しやすそう /* 区間…
Wormholex 6面ダイス20個セット 14mm ラウンドコーナー クリア サイコロ 10色（レッド、浅いブルー、オレンジ、黄色、紫色、濃いブルー、バラ色、ピンク、蛍光グリーン、黄緑色） 1枚収納袋付きメディア: おもちゃ＆ホビー Quiz https://tdpc.contest.atcode…
Quiz https://atcoder.jp/contests/dp/tasks/dp_u AC https://atcoder.jp/contests/dp/submissions/8803874 参考にした解説 https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_3 部分集合から部分集合を選…
たとえば8人集合 01101101 1が生きているとする 生きている中から部分集合の選び方を全探索する 今回の場合、1が5つあるので、25=32種類の選び方がある それを無駄なく列挙する方法は蟻本に書いてある ll sup = 0b01101101; ll sub = sup; do{ debug(bitset<…
Quiz Q - Flowers https://atcoder.jp/contests/dp/tasks/dp_q AC (自作セグ木) https://atcoder.jp/contests/dp/submissions/8796568 Range Minimum Query用のものを書き換えて作成 書き換える箇所が複数ある AC(https://ei1333.github.io/luzhiled/) https…
Quiz M - Candies https://atcoder.jp/contests/dp/tasks/dp_m RE Code https://atcoder.jp/contests/dp/submissions/8791689 解説 REとなったコードはO(NxKxK)なので普通に出すとTLE そのまま出してAC or TLEだったら論理は合っていそう ただ、ジャッジに待…
Quiz https://atcoder.jp/contests/dp/tasks/dp_j AC https://atcoder.jp/contests/dp/submissions/8788822 参考 けんちょんさん https://qiita.com/drken/items/03c7db44ccd27820ea0d#j-%E5%95%8F%E9%A1%8C---sushi しかし、＋１の部分がよく分からなかった…
Quiz D - Lucky PIN https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d AC https://atcoder.jp/contests/sumitrust2019/submissions/8781474 Code：部分列判定 // s内に部分列としてtがあるか探す bool is_substring(string& s, string& t){ //…
next_permutationの動きを確認 VI V; rep(i, 4){ V.push_back(i); } do{ debug(V); }while(next_permutation(ALL(V))); 出力 [V]: {0, 1, 2, 3} [V]: {0, 1, 3, 2} [V]: {0, 2, 1, 3} [V]: {0, 2, 3, 1} [V]: {0, 3, 1, 2} [V]: {0, 3, 2, 1} [V]: {1, 0, 2,…
Quiz https://yukicoder.me/problems/no/872 AC https://yukicoder.me/submissions/404193 解法 まずはganariyaさんの解説を読みましょう https://scrapbox.io/ganariya/YukicoderContest221_C%E5%95%8F%E9%A1%8CP2_%E3%80%8CAll_Tree_Path%E3%80%8D そこに…
Quiz https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d AC https://atcoder.jp/contests/sumitrust2019/submissions/8754255 解法 dp[i][j][k][l] i : i番目まで見た時 j : 最後に選んだ数 k : 1つ前に選んだ数 l : 2つ前に選んだ数 としてDP …
Quiz 最大長方形 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_B&lang=jp 壁のあるグリッド内で作れる最大長方形の面積を求めよ AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4010799#1 解法 （１）各行を底としたヒストグ…
環境 Windows 10 + WSL g++にデバッグオプションを付けてコンパイル 動機 segmentation faultしたとき、位置が分からなかった gdbを使ってみよう やったこと sudo apt get gdb gdb ./a.out テストケース（テキストファイル）を入力したいので以下のようにし…
// https://www.sejuku.net/blog/54493 // を少し書き換えたもの // 参照なので書き換えます string replace_all(string &s, string from, string to) { ll pos = s.find(from); while(1){ pos = s.find(from, pos); if(pos==string::npos) break; s.replace…
Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2607 AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4008533#1 解法 毎日売ると考えてよいので、今日と明日だけを見て利益を最大化すればいい 画像のように荷物に置き換えて、個…
設定 ２次元平面上の２点を与えられた時、そこを通る円が存在するなら２つある その円の中心２つを求めたい 解法 ２次元ベクトルで考える（プログラム的には複素数complexを利用する） ２点の中央ｃから垂直方向に単位ベクトルｎを考える（画像参照） それを…
Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1602&lang=ja AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4007025#1 解法 入力をN行全部読み込んで後ろから処理 サンプル 10 + .+ ..6 ..2 .+ ..1 ..* ...7 ...6 .3 文字列 "…
