No.1071 ベホマラー

Quiz https://yukicoder.me/problems/no/1071 AC https://yukicoder.me/submissions/507889 解法 三分探索(想定解ではない) 全部ベホイミが最適:左のグラフ 全部ベホマラーが最適:中央のグラフ 丁度いいベホマラー回数がある:右のグラフ 下に凸のグラフ…

No.1101 鼻水

https://yukicoder.me/problems/no/1101 こちらの問題の解説を図示してみました。黒い波打つ線が鼻水の余裕量で、0を下回るとアウトです 波線を下で支えるサポートラインを考えると、何回鼻をすすることができるかが求められます

永続Union Find

部分永続Union Findとも言うらしい 各uniteしたときに時刻が1進むとして、各時刻での連結情報が取れる、記憶力の良いUF // cf : https://misteer.hatenablog.com/entry/persistentUF // 永続UF struct PersistentUnionFind{ VI parent; // 親ID VI time; // …

山登り・登山の最大負荷

自分検索用に上記タイトルにした code // 山登りの最大負荷 // A[i] = -1 or 0 or 1 // 最大上昇を返す ll max_fatigue(VI& A){ ll ma=0; ll cur=0; ll N = A.size(); rep(i,N){ cur += A[i]; chmax(ma, cur); if(cur<0) cur=0; } return ma; } what is this…

popcount bitcount 関数 C++

int popcount(signed t){ return __builtin_popcount(t); } int popcount(ll t){ return __builtin_popcountll(t); } 参考 maroonrkさん https://atcoder.jp/contests/agc038/submissions/7633722?lang=ja

ラムダ式のサンプル

型 auto f = [&](){ a++; }; 利点 main関数内で関数が定義でき、main関数内の変数にもアクセスできる よって「関数に分離したいが変数をグローバルに書き直すのが面倒」を省略できる 実例 // 二分探索の判定関数 auto can = [&](ll center){ ll sum=0; rep(i…

F - Strivore

Quiz https://atcoder.jp/contests/abc171/tasks/abc171_f 有益なTweet引用 Fは昨日のAGCのおかげで割と速く解けた.「操作列の結果としてあり得るものの個数」を求める時は,結果に重複が生じないように操作列に制約を加えてから操作列の個数を数える,とい…

C - One Quadrillion and One Dalmatians 26進数っぽいもの

ABC

Quiz https://atcoder.jp/contests/abc171/tasks/abc171_c Submission https://atcoder.jp/contests/abc171/submissions/14599113 解説 editorialの通りなのですが、261, 262, ..., で分割されるグループごとに考えて、答えが何桁かを求める(それをX桁とす…

文字列の落とし穴 C++ 「リテラル文字列はそのアドレスを返す」

// そもそもできない string s = "aaa" + "bbb"; // できるけど、sには謎の文字列が入る。"a"は入らない string s = ""+'a'; 「リテラル文字列はそのアドレスを返す」を意識すると、2つ目のコードは""でどこか領域が確保され、+'a'によってアドレスがオフセ…

B - fLIP O(N)解法

Quiz https://atcoder.jp/contests/code-festival-2017-quala/tasks/code_festival_2017_quala_b 解説 editorialにO(N)でも可能と書いてあったのでやってみた 行への操作を全探索する 縦への操作をa回行って、Kが実現できるかを考える 下記画像の最後の式を…

multiset erase (数値指定 / iterator指定)

sorted 適当に突っ込んでからprintしてみると、ソートされていることが分かります #include<bits/stdc++.h> using namespace std; int main(){ multiset<int> se; se.insert(5); se.insert(3); se.insert(5); se.insert(2); se.insert(7); for(int v : se){ cout << v << endl; }</int></bits/stdc++.h>…

No.1076 寿司打

Quiz https://yukicoder.me/problems/no/1076 解説 editorialのように方程式一発でやるとかっこいい でも今回は基本に立ち返って求めてみると、以下のようになります 「等比数列の和の公式」を使いました

複数のC++をコンパイルしたものをつなげる(例:a.out, b.out, ...)

3パターン書いてみた。 Pythonでつなげる Pythonのsystemからa.outなどを実行して出力をファイルに書き、別の行でb.outを呼ぶ 参考:「グルー言語」 windows batを書く これもシンプル Unix (Linux)のパイプを使う 想定 a.cppとb.cppがあり、コンパイルした…

ブラウザの履歴を管理してください

というお題が出たとする 戻る・進む・クリア・仕様変更に対応したい シンプルにvectorを使うのがいいだろう 今回確かめたかったのは、構造体を定義したとして、実際の変数を波括弧で作れるかどうか 作れました。シンプルな書き方を知っておくのは良いこと #i…

判別式・2点を通る直線・2次方程式の解(x1,x2)

タイトルにある3つを関数化した // 判別式 ll discriminant(ll a, ll b, ll c){ return b*b - 4*a*c; } // 2次方程式の解(x1, x2) pair<ld,ld> quadratic_equation(ll a, ll b, ll c){ ll D = discriminant(a,b,c); ld x1 = (-b-sqrt(D))/(2*a); ld x2 = (-b+sqrt(D</ld,ld>…

第二回 PAST H - 1-9 Grid ダイクストラ解法

Quiz https://atcoder.jp/contests/past202004-open/tasks/past202004_h AC code https://atcoder.jp/contests/past202004-open/submissions/13146204 解法 始点を0, 終点を10とします 各グリッドの位置ごとにidを振っておきます 数値 i -> 数値 i+1 のそれ…

B - Powers of two

Quiz https://atcoder.jp/contests/agc029/tasks/agc029_b AC code https://atcoder.jp/contests/agc029/submissions/13113984 解説 A = 3,1,1,5 を考えてみる 左から見ていって2べきになれるペアに貪欲にくっつけるのはNGだと分かる A = 3,1,7,5 を考えてみ…

Google Codejam Round 1C 2020 B Overrandomized

Round 1C 2020 https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef4 予選突破 A✅✅✅ B✅✅✅ C✅❌❌ B問題 Overrandomized 1 (テストケース数) 2 (最大桁数) 20 P (以下、データが10000行) この10000行を「ログ」と呼ぶことにする 37 PU 26…

D - Multiple of 2019

Quiz https://atcoder.jp/contests/abc164/tasks/abc164_d 解法 (editorial) 右からi番目までを数字として見て mod 2019した結果を持っておく 入力の数字は文字列で受け取り、1桁ずつ処理すれば桁あふれしない modの結果が同じ数字のところは、それを組み合…

C. Yet Another Counting Problem

Quiz https://codeforces.com/contest/1342/problem/C 解説 l~rの範囲で数えたい。0~xまでの範囲で数えることが f(x)でできるなら、f(r) - f(l-1)で求められる。よくあるテク 周期a x bで同じ結果となるので、f(0) ~ f(a x b)までを事前計算しておき、fを…

MIS.W新歓コンテスト2020 Random Card Battle ~floatの精度は低い~

Quiz https://www.hackerrank.com/contests/misw-welcomecontest2020/challenges/random-card-battle/problem 解法 A>BならX=0で勝てるので勝率100% それ以外ならX=Aで全力で範囲を広げるのが最適 落とし穴(?) 小数点以下、有効数字5桁、四捨五入で出力す…

天下一プログラマーコンテスト2012 予選C「B - ロイヤルストレートフラッシュ」

Quiz https://atcoder.jp/contests/tenka1-2012-qualC/tasks/tenka1_2012_10 AC code https://atcoder.jp/contests/tenka1-2012-qualC/tasks/tenka1_2012_10 解説 どの絵柄でロイヤルストレートフラッシュを目指すのが1番速いのかを先に求めておく必要がある…

F - Select Half

Quiz https://atcoder.jp/contests/abc162/tasks/abc162_f AC code https://atcoder.jp/contests/abc162/submissions/11935719 dp[i][j][k] i : まで見て (N) j : その点を選んだ/選んでいない (0,1) k : 大ジャンプ回数 (0,1,2) として配るDP 解法以外 解法…

E - Virus Tree 2 「根っこは特別」

Quiz https://atcoder.jp/contests/abc133/tasks/abc133_e 解説 snukeさんの解説放送 https://www.youtube.com/watch?v=8uowVvQ_-Mo ひとこと void dfs(int v, int p=-1) { for (int u : to[v]) { if (u == p) continue; dfs(u,v); } int nk = (p==-1) ? k :…

Round 1A 2020 - Code Jam 2020 33点でフィニッシュです

#GCJ ✅✅❌✅✅❌✅❌の33点でした。これでは3768位で全然届かない— peroon_cp (@peroon_cp) April 11, 2020 睡眠調整 AM10時から2.5h, 睡眠調整はちゃんとできて頭は動いている 全体的な方針 取れる部分点は取ろう (これは振り返ると失敗) 解説 kmjpさんのブログを…

D - Semi Common Multiple ~lcm求めるだけではダメなサンプル~

Quiz https://atcoder.jp/contests/abc150/tasks/abc150_d AC code https://atcoder.jp/contests/abc150/submissions/11677574 間違った解法 A[i]をそれぞれ2で割る それらでlcmを求める lcmでMを割ったおよそ半分が答え lcm求めるだけではダメなサンプル 4 …

dfsで閉路検出 D - Subway

Quiz https://codeforces.com/contest/131/problem/D AC code https://codeforces.com/contest/131/submission/74636017 解法 閉路が1つだけあることが決まっているので、dfsして再訪した点があれば、それは閉路内の点 dfsしながら親を記録しておけば、閉路…

F - Knapsack for All Segments

Quiz https://atcoder.jp/contests/abc159/tasks/abc159_f 解説 私の解説ではないですが、良さそうな解説がTweetされていたのでたどり着ける人が増えるようにここに書いておく ABC159-F: Knapsack for All Segments の解説を書きました.DPの問題を,センス…

prefix palindrome

prefix palindromeの例 aaaabbbbbcc => aaaa (回文としてはbbbbbの方が長いが、prefixではない) editorial ??? 文字列のprefixのうち、最大の回文を求めたい この問題で必要だった https://codeforces.com/contest/1326/problem/D2 editorialを見てもよく分…

全方位木DPについてBlogを読むより先に見るべき動画

Educational DP Contest / DP まとめコンテスト (EDPC) : V - Subtree 解説動画 jupiroさんの動画 木DPは理解済みとする rerootingという言葉を使っていて、しっくりきた この動画でイメージを掴んだ後に https://atcoder.jp/contests/dp/tasks/dp_v を解い…