競技プログラミング

ABC078C – HSI

確率pで成功するまで試行した場合、成功までの試行回数の期待値は1/pになるらしい。 なるほど C - HSI PDFガン見しながら解法書いていたらほぼ変わらない内容になった・・・ #include <bits/stdc++.h> #define INF 1e9 using namespace std; #define REPR(i,n) for(int i=(n); i >= 0; --i) #define FOR(i, m, n) for(int i = (m); i < (n); ++i) #define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define ALL(a) (a).begin(),(a).end() template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; } template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; } int gcd(int a,int b){return b?

ARC051A – 塗り絵

これリアルでやってたら二点間距離に気づかずにおわおわになるやつ 右下、うまく四角形描けなくて申し訳ない A - 塗り絵 こんな感じの場合分けを作り出す問題本当に苦手なので得意になっていきたい・・・・ #include <bits/stdc++.h> #define INF 1e9 using namespace std; #define REPR(i,n) for(int i=(n); i >= 0; --i) #define FOR(i, m, n) for(int i = (m); i < (n); ++i) #define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define ALL(a) (a).begin(),(a).end() template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; } template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; } int gcd(int a,int b){return b?

AGC028A – Two Abbreviations

ムズイ A - Two Abbreviations 解説、O(N+M)って書いてあるんですけどNはどこだろう。。。 条件式にLが出てこない => Lは良い文字列を作れるかどうかに関与しない ってことですね・・・ ちゃんと式立てて考えるとかなり時間がかかる・・・・ #include <bits/stdc++.h> #define INF 1e9 using namespace std; #define REPR(i,n) for(int i=(n); i >= 0; --i) #define FOR(i, m, n) for(int i = (m); i < (n); ++i) #define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define ALL(a) (a).begin(),(a).end() template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; } template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; } int gcd(int a,int b){return b?

キーエンスプログラミングコンテスト 2020 【Cまで】

Cまでしか解けなかったんですけど、何というかAtCoderでは珍しい雰囲気の問題だった・・・ A: Aにしては結構珍しい、読解力で実装を軽くしていく様な問題。 二つの操作は独立している ので最もマスが多く塗れる様な操作をひたすら繰り返せば良い。 A - Painting #include <bits/stdc++.h> #define INF 1e9 using namespace std; #define REPR(i,n) for(int i=(n); i >= 0; --i) #define FOR(i, m, n) for(int i = (m); i < (n); ++i) #define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define ALL(a) (a).begin(),(a).end() template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; } template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; } int gcd(int a,int b){return b?

AGC041A – Table Tennis Training

AGCお疲れ様でした。 AtCoder Grand Contest 041 - AtCoder Writerがtouristの時点で最高に興奮しますね。 超つまづいた訳でもないのですが、僕が高校時代卓球部に所属していたこともあり、「うわ〜〜〜やってた、やってたw」って気持ちになったので、折角なので解説を書こうかと思います。 問題はこれです。 A - Table Tennis Training これ本当よくやってたんすよ・・・・(しつこい) 提出 #9180259 - AtCoder Grand Contest 041 #include <bits/stdc++.h> #define INF 1e9 using namespace std; #define REPR(i,n) for(int i=(n); i >= 0; --i) #define FOR(i, m, n) for(int i = (m); i < (n); ++i) #define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define ALL(a) (a).

ABC148E – Double Factorial

ここまでDiff低めなコンテスト中々無くない・・・? 珍しい下振れなコンテストでしたね! 12分でDまで解いてパフォ800の世界怖い・・・・ そしてE問題です。 E - Double Factorial 末尾に10がある⇨2*5の組み合わせがいくつあるかって言う話です。 こういった問題は、TLE解を実装してから解答を作ると、比較できて滅茶苦茶良いのですが、TLE解間違ってると終了します。 なんでこんなこと書いているかって言うと、私はこれで終了したからです。 例えばf(12)の際末尾に0が何個並ぶと思います? 12,10,8,6,4,2,1を掛けるので1になるのは和英とさくっとわかると思います? では、100の場合は? 100,90,80,70,60,50,40,30,20,10ですよね これ、11じゃないんです。 私、これに気づくのに1時間かかりました。 何をやらかしたかって、TLE解を間違えたのでそもそも間違っていることに気づかない地獄パターンへ・・・・ 辛いね。 ちなみにこんな感じのコードでACできます。 #include <bits/stdc++.h> #define INF 1e9 using namespace std; #define REPR(i, n) for(int i=(n); i >= 0; --i) #define FOR(i, m, n) for(int i = (m); i < (n); ++i) #define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define ALL(a) (a).

ABC108 C-Triangular Relationship

全くわからなくて草生えたので、 AtCoder ARC 102 C - Triangular Relationship (300 点) - けんちょんの競プロ精進記録 けんちょんさんのこの記事を読むついでにブログを書きつつ理解していきたいと思います。 今回は解法2でいきます。 ほぼ先ほどの記事と同じですが考察はこんな感じになります(えっ難しい・・・難しくない?) コーディングをば #include <bits/stdc++.h> #define INF 1e9 using namespace std; #define REPR(i,n) for(int i=(n); i >= 0; --i) #define FOR(i, m, n) for(int i = (m); i < (n); ++i) #define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define ALL(a) (a).

ABC143 大反省会場

どうしてこうなった・・・ そもそも色々知らなかった所があるので、まずはそこから もくじ nC2, 2重Forループで出来るってマジ? A問題 B問題 C問題 D問題 参考 nC2, 2重Forループで出来るってマジ? インデックスをうまいことやればnC2の組み合わせが出来るそうです。 例えば [0,1,2]から二つの組み合わせを取る場合、 [0,1],[0,2],[1,2] の3通りです。 これをC++の2重Forループでやってみましょう。 #include <bits/stdc++.h> using namespace std; #define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i) int main() { int A = 3; REP(i, A) { for (int j = i+1; j < A; j++) { cout << i << ", " << j << endl; } } return 0; } これが実行結果

【CLion+WSL 2】Windowsで俺的競技プログラミング用 C++環境構築

これは2019/10/19に書いた記事です。 IntelliJ信者なのでCLionで競技プログラミングがしたい。家のデスクトップPCはWindowsなのでWindowsでなんとかやりたい。新しいもの好きなのでWSL 2をうまく組み合わせたい。 もくじ 環境 前提 CLionのインストール WSL側設定 CLion ToolChainsの設定 参考 環境 Windows 10 Pro Insider Preview Build18970.rs_prerelease WSL 2 Ubuntu 前提 WSL 2環境は構築完了している前提 CLionのインストール IntelliJ信者ならJetBranins ToolBoxは使うべきなので入ってないならまずはインストール JetBrains Toolbox App: Manage Your Tools with Ease

heapqとABC141D – Powerful Discount Ticketsと私

ポエム兼備忘録です。 悔しいので一気に書ききります。 これは問題 多分解くのは二段階 問題の読み替え(一番値段の高いものを取得してそれを半額って流れだと読む) 実装(私はここでおしまいになりました) 1は多分そんなに難しくない。問題は2 愚直実装(M,Nの二重forループとか?)だとO(MN)で間に合わない。ここはわかる。 じゃあいったんソートして、一番後ろの要素(一番値が大きい)をpop (O(1))してその要素を半分にしてbisectでぶち込めばO(MlogN)じゃん!!! お手上げ 私は涙を流し、残り五分という短い時間を使いrocket leagueをするのだった・・・・ もくじ ABC終了後 変わりました ちゃんと書きました poem ABC終了後 それはそうとして解説を読んだらheapqらしい。どうやろ値の追加削除がO(logN)で最小値の取得がO(1)だとか (えっでもそれ俺の実装と変わらなくない) 変わりました array.Insert() がO(N)だからいくらインデックスの発見がO(logN)で挿入したら遅くなるという・・・ 謝罪 ちゃんと書きました poem 今までPythonで書いてた理由として、趣味のプログラムをPythonで書いてたのと、言語仕様を知るために活用して来たが正直もうPythonで書いてないのでC++に移行しちゃおうかなと思ってしまった 何が一番嫌って計算量の見積もりミスを(これはPythonだから遅いのでは無いのか・・・?)とPythonのせいにしてしまうのが一番嫌だった。