2019-01-01から1年間の記事一覧
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造作者: 渡部有隆,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。ブロック以外の全マスに方向マスを置く 人の動きをシミュレートし、踏まれない方向マスを削除 →→→などのマスは…
Quiz https://atcoder.jp/contests/abc039/tasks/abc039_d AC Code https://atcoder.jp/contests/abc039/submissions/8144631 void paint(ll i, ll j, VV& G, ll v){ ll H = G.size(); ll W = G[0].size(); // 近傍8も塗る FOR(dx, -1, 2){ FOR(dy, -1, 2){ …
Quiz https://atcoder.jp/contests/abc036/tasks/abc036_c 解法 座標圧縮（座圧と呼ばれる）をするだけ AC https://atcoder.jp/contests/abc036/submissions/8143705 // 座標圧縮 // Aをそのまま書き換えるVER void compress(vector<ll>& A){ // 変換表 auto B =</ll>…
Quiz https://atcoder.jp/contests/abc119/tasks/abc119_c AC Code https://atcoder.jp/contests/abc119/submissions/8134185 void dfs(VI V){ if(SZ(V)==N){ calc(V); return; } rep(i, 4){ V.push_back(i); dfs(V); V.pop_back(); } } 解法 各竹を0, 1, 2,…
// 隣接行列 ll d[100][100]; int main(){ // input ll N, M; cin >> N >> M; // 隣接行列の初期値。infにする rep(i, N){ rep(j, N){ if(i!=j) d[i][j] = inf; } } // 距離データ入力 rep(i, M){ ll a, b, c; cin >> a >> b >> c; a--; b--; d[a][b] = c; d…
Quiz 1239A - Ivan the Fool and the Probability Theory https://codeforces.com/contest/1239/problem/A 縦横 n x mのタイルを”at most one adjacent cell of the same color”で塗る塗り方 AC Code https://codeforces.com/contest/1248/submission/630801…
対象者 coutを使っている 確認コード 1466ms https://codeforces.com/contest/1220/submission/62112806 78ms https://codeforces.com/contest/1220/submission/62113199 差分 coutの改行でendlを使ったのが1番目、'\n'を使ったのが2番目 500000行ほど出力す…
Quiz https://codeforces.com/contest/1215/problem/B Submission https://codeforces.com/contest/1215/submission/62082416 解法 dpのようにi番目まで考えた時の ansP (正の組み合わせ数) を考える A[]の値は+1, -1に単純化しておく 前から i まで見ていっ…
Quiz https://atcoder.jp/contests/agc039/tasks/agc039_b AC✅ (解法：二部グラフ判定＆グラフの直径） https://atcoder.jp/contests/agc039/submissions/7879736 解法 解説放送の通り、二部グラフ判定し、二部グラフなら構成可能 構成可能な場合、グラフの…
Quiz https://atcoder.jp/contests/agc039/tasks/agc039_a AC Code https://atcoder.jp/contests/agc039/submissions/7879593 ランレングス圧縮 (復元はできない) // ランレングス // 例 s = "aabccc" => [2, 1, 3] VI run_length(string s){ char prev = s[…
Quiz https://yukicoder.me/problems/no/898 Submission https://yukicoder.me/submissions/387090 解法 editorialの通り dijkstraとLCAの過去コードをコピーペースト その他 全点間距離が必要？ワーシャルフロイド？制約的に無理・・・ と思ったけれどLCAを…
Quiz https://atcoder.jp/contests/abc055/tasks/arc069_b AC Code https://atcoder.jp/contests/abc055/submissions/7840056 解法 editorialの通り、添字0, 1の動物を決めてしまえば連鎖的に後ろが決まる 最後に整合性チェックをするのだが、私は最初、動物…
https://codeforces.com/contest/1228/problem/C この問題を解いていて、入力nが1018までなので、long longギリギリまで入力されうる pow(p, k)をナイーブに求めたらoverflowするし、modをとると正しく判定できない ということで判定関数を作った pk > 1018…
Quiz https://atcoder.jp/contests/abc142/tasks/abc142_f Submission https://atcoder.jp/contests/abc142/submissions/7805082 解法 ワーシャルフロイドを使った最小閉路の検出 algorithm - graph - How to find Minimum Directed Cycle (minimum total we…
Quiz https://atcoder.jp/contests/agc038/tasks/agc038_b AC https://atcoder.jp/contests/agc038/submissions/7654290 解法 editorialは読み、解説放送も見たとする まったく被りなしの場合は答えがN-K+1で、これが最大。ここからダブルカウントしてしまっ…
Quiz https://atcoder.jp/contests/abc141/tasks/abc141_e 3パターンで解いた。とはいえ完全に「けんちょん」さんの記事に依存している 解いた順に書く あとから検索する用に書いている。1度使ったコードは安心感があるため 1. ローリングハッシュ（ロリハ）…
Quiz E - Who Says a Pun? https://atcoder.jp/contests/abc141/tasks/abc141_e Submission https://atcoder.jp/contests/abc141/submissions/7553482 けんちょんさんのロリハ使用 衝突した状況 途中のデータでWA. 1つのロリハでは衝突してしまったのだろう …
注意 range add, range updateは区別しよう 今回はrange add 使った問題 C - Attack Survival https://atcoder.jp/contests/abc141/tasks/abc141_c Submisssion https://atcoder.jp/contests/abc141/submissions/7551683 できること 範囲加算 [a, b) にwを加…
Quiz https://atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_c Submission https://atcoder.jp/contests/tenka1-2018-beginner/submissions/7508948 ジグザグに配置 editorialに書いてあるとおり、1, 3, 5と置くより1, 5, 3と置いたほうがよ…
Quiz https://atcoder.jp/contests/abc140/tasks/abc140_d Submission https://atcoder.jp/contests/abc140/submissions/7498421 解法 editorialの別解の方だと楽です（別解じゃない方も通したけど苦労した）。つまり、 連続したL, Rは圧縮して1文字にする …
Quiz https://codeforces.com/contest/1202/problem/A Submit https://codeforces.com/contest/1202/submission/60410011 解法 文字列をs, tとする 2kをかけることは左シフトと同じ tを左に滑らせていき、足して反転させたものを辞書順最小にすればいい 最後…
