perogram

No.845 最長の切符 ~最長距離・ダイクストラ・ベルマンフォード・bit DP~

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 以下、(間違った考…

W - Intervals ~遅延セグ木(範囲加算・範囲Max)~

Quiz https://atcoder.jp/contests/dp/tasks/dp_w 解説AC https://atcoder.jp/contests/dp/submissions/8814646 感想 論理はemtubasaさんの解説を参考 遅延セグ木はふるやんさんのを借りてきた いくつかパターンが書かれているから再利用しやすそう /* 区間…

テクい!「D - サイコロ」(Typical DP Contest)

Wormholex 6面ダイス20個セット 14mm ラウンドコーナー クリア サイコロ 10色(レッド、浅いブルー、オレンジ、黄色、紫色、濃いブルー、バラ色、ピンク、蛍光グリーン、黄緑色) 1枚収納袋付きメディア: おもちゃ&ホビー Quiz https://tdpc.contest.atcode…

U - Grouping (Educational DP Contest / DP まとめコンテスト)

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 部分集合から部分集合を選…

ビットで表された部分集合の全探索(蟻本p144)

たとえば8人集合 01101101 1が生きているとする 生きている中から部分集合の選び方を全探索する 今回の場合、1が5つあるので、25=32種類の選び方がある それを無駄なく列挙する方法は蟻本に書いてある ll sup = 0b01101101; ll sub = sup; do{ debug(bitset<…

Range Max Query セグメント木

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…

assert(false)でREを起こしてジャッジの反応を見る

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だったら論理は合っていそう ただ、ジャッジに待…

J - Sushiで期待値DPを掴んだ気がする

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 しかし、+1の部分がよく分からなかった…

文字列s内に文字列tは部分文字列として存在するか?

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_partial_permutationとは何なのか?動作を観察した~ペアの全探索~

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,…

sum of all cost between all nodes in a tree ~木の全点間コストの和~

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 そこに…

D - Lucky PIN ~4次元DPで解く編~

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 解法 (1)各行を底としたヒストグ…

gdbでsegmentation faultをした場所を特定する

環境 Windows 10 + WSL g++にデバッグオプションを付けてコンパイル 動機 segmentation faultしたとき、位置が分からなかった gdbを使ってみよう やったこと sudo apt get gdb gdb ./a.out テストケース(テキストファイル)を入力したいので以下のようにし…

C++ 文字列 一括置換

// 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…

Invest Master (AOJ 2607) 個数制限なしナップサック

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

2点を通る円の中心を求める

設定 2次元平面上の2点を与えられた時、そこを通る円が存在するなら2つある その円の中心2つを求めたい 解法 2次元ベクトルで考える(プログラム的には複素数complexを利用する) 2点の中央cから垂直方向に単位ベクトルnを考える(画像参照) それを…

ICPC Calculator

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 文字列 "…

E - 車の乗り継ぎ

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 始点と終点にも車を定…

F - Sugoroku

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を使う u, v (depth[u] < depth[v…

C - On Changing Tree ~オイラーツアーとセグ木~

Quiz https://codeforces.com/contest/396/problem/C AC https://codeforces.com/contest/396/submission/65574597 解法 まずは「npca2015年部誌_木に対する一般的なテク達.pdf」p34を読んでください。それでも分からなければ続きを読んでください 補足 p34…

C++ floor int 誤差

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

範囲更新の遅延セグ木で殴る (No.318 学学学学学)

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

Expression 0041

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

Combination of Number Sequences

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

2次元累積和クラスを作成

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

POJ (北京大学オンラインジャッジ)に初めて提出してみた。オススメはしない

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

2次元BITクラス

参考 http://hos.ac/slides/20140319_bit.pdf Code #include<bits/stdc++.h> using namespace std; using ll = long long; using VI = vector<ll>; using VV = vector<VI>; #define FOR(i,a,b) for(ll i=(a);i<(b);++i) #define rep(i,b) FOR(i, 0, b) #define ALL(v) (v).begin(), </vi></ll></bits/stdc++.h>…

N個からK個選ぶ全探索(蟻本 p144)

例 例として、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)>…