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 解法 毎日売ると考えてよいので、今日と明日だけを見て利益を最大化すればいい 画像のように荷物に置き換えて、個…

設定 ２次元平面上の２点を与えられた時、そこを通る円が存在するなら２つある その円の中心２つを求めたい 半径rは与えられるとする 解法 ２次元ベクトルで考える（プログラム的には複素数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 文字列 "…

Quiz https://atcoder.jp/contests/gigacode-2019/tasks/gigacode_2019_e AC https://atcoder.jp/contests/gigacode-2019/submissions/8639311 サンプル6 解法 // i番目の車で j まで行く最短時間 double dp[2050][2050]; と定義してDP 始点と終点にも車を定…

Quiz https://atcoder.jp/contests/abc146/tasks/abc146_f AC https://atcoder.jp/contests/abc146/submissions/8639063 解法 後ろから貪欲 補助配列Fを作った。iに飛びたい時、s[i]=='0'ならそのまま飛べるけれど、s[i]=='1'の時はその手前の'0'の位置を教…

Quiz npca2015年部誌_木に対する一般的なテク達.pdf p36 Running Away from the Barn (USACO 2012 December Gold) 木上の点に一律の値を足す これをO(logN)でする方法が必要 下図のようなグラフを考える オイラーツアーとBITを使う vの先祖がuである場合のみ…

Quiz https://codeforces.com/contest/396/problem/C N頂点の木 (3 x 10^5) クエリQ (3 x 10^5) ・1 v x k : 頂点vにxを足す。vの子孫にも、vからの距離 i によりx - i kを足す ・2 v : 頂点vの値をmod 10^9+7でprint 足す値が一律ではないことをどう扱うか …

yukicoder 軽減税率？で誤差に苦しんだ。かけてから割るのと、割ってからかけるの、floorしたときに切り捨てるものが違ってくる pic.twitter.com/nz7UoBiY8b— peroon_cp (@peroon_cp) November 22, 2019 原因 パット見 1839816.0000に見えるが、実は1839815.…

Quiz No.318 学学学学学 - yukicoder https://yukicoder.me/problems/no/318 AC https://yukicoder.me/submissions/399103 解法 想定解ではないが範囲更新の遅延セグ木で殴るというのをやってみた 範囲を書き換える (範囲に足すのではない) pekempeyさんのセ…

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力)出版社/メーカー: マイナビ発売日: 2015/01/30メディア: 単行本（ソフトカバー）この商品を含むブログ (7件) を見る Quiz http://judge.u-aizu.ac.jp/…

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力)出版社/メーカー: マイナビ発売日: 2015/01/30メディア: 単行本（ソフトカバー）この商品を含むブログ (7件) を見る Quiz http://judge.u-aizu.ac.jp/…

動機 1次元累積和クラスはよく使っているため 2次元累積和を使う問題と出会ったため Code // 2次元累積和 struct AccSum2D{ VV Ac; // accumulate ll W; ll H; AccSum2D(){} AccSum2D(VV &A){ H = A.size(); W = A[0].size(); Ac.resize(H+1, VI(W+1)); // i…

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?作者: 秋葉拓哉,岩田陽一,北川宜稔出版社/メーカー: マイナビ発売日: 2012/01/28メディア: 単行本（ソフトカバー）購入: 25人 クリック: …

参考 http://hos.ac/slides/20140319_bit.pdf そのままC++で実装するとこんな感じ(1-indexed, x,y順の変数) http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4890859#1 自分用 0-indexed, y,x順の変数 E： たい焼きマスターと食べ盛り - Taiyaki-Mast…

例 例として、N個からK個選ぶことを考えます N=5 K=2 N人のクラスからK人の委員長を選ぶことをイメージします もちろんN人はそれぞれ別の人です（赤玉・白玉のように同一視しない） 蟻本VER ll n = 5; ll k = 2; int comb = (1<<k) - 1; while(comb<1<<n){ //ここで組み合わせに対して処理をする cout << bitset<5>(comb) << endl; int x = comb</k)>…

Quiz https://codeforces.com/contest/508/problem/D AC https://codeforces.com/contest/508/submission/64427177 上記提出に、オイラー路を求める構造体、あります オイラー路：全ての「辺」を1度ずつ通る路 (Trail) 参考：全ての「点」ならハミルトン路 (…

Quiz E - MUL https://atcoder.jp/contests/arc085/tasks/arc085_c AC Code https://atcoder.jp/contests/arc085/submissions/8316327 解法 アルメリアさんの解説の通り その他 割る・残すは右左のどちらでもいい（今回たまたまアルメリアさんとは逆になった…

参照先 英語だが https://blog.anudeep2011.com/mos-algorithm/ Codeforcesで2400などの難しさなので、早期に学ぶ必要はない 例題 数字の配列Aがある（長さN=105など）（値域も 0～N） クエリがQ個ある（105など） O(N2), O(NQ)ではTLE クエリ：L Rからなり…

コンテストページ https://atcoder.jp/contests/future-contest-2020-qual/tasks/future_contest_2020_qual_a シミュレータ 手法 ゴールからBFS。ブロック以外の全マスに方向マスを置く 人の動きをシミュレートし、踏まれない方向マスを削除 →→→などのマスは…