超初心者が競プロに挑む

初心者からの競プロ練習記録

ARC075Eメモ

配列A[i]がある時、A[i]

ARC073Eメモ

ARC

ARC073Eで気になるところをメモ A,Bという同じ長さの配列がある時に、あるiでA[i]とB[i]を入れ替えるという操作を繰り返して A中の最大値と最小値の差を最小化するという時のアルゴリズムのこと 例 A=[8,4,4,4,1] B=[4,0,0,0,4] Aの最大値と最小値の差は8-1=…

ABC022C解いてみた

ワーシャルフロイド法は初めてでした。 #include <cstdio> #include <algorithm> #include <utility> #include <vector> #define MAX_V 305 #define INF (300*100000*10) using namespace std; int N, M; int d[MAX_V][MAX_V]; typedef pair<int,int> P; int costs[MAX_V]; int main() { for(int i=0;i</int,int></vector></utility></algorithm></cstdio>

ABC023D解いてみた

ABC023Dを解いてみました。 まずlogの計算で詰まってしまった(*_*)。最大での計算量となるはずですが、すると、を代入してで計算するとで終わるわけねーだろって思い込んでいたんですが、logの計算間違えてましたね。正しくはということで、logは要注意。 追…

ABC021D解いてみた

重複組み合わせですね...。高校の頃ひたすら苦手でした。なんとか解説を理解したので、解答を書いてみた。 #include <cstring> #include <cstdio> #define MOD (1000*1000*1000+7) using namespace std; class FactorialMOD { public: static const int MAX_N = 200000 + 100;</cstdio></cstring>…

ABC017D解いてみた

ABC017Dを解いてみました。 しゃくとり法+dpみたいなのは初めてで勉強になった。あと、dpを直接配列にしないで関数にしてやると初期条件で楽できるということに気づいた #include <cstdio> #include <algorithm> #include <cstring> #define MOD (1000*1000*1000 + 7) using namespace st</cstring></algorithm></cstdio>…

ABC025C解いてみた

ゲームの問題は初めてなので解いてみた。ゲーム木と呼ぶらしいですね。こういうの初見で解けるようになりたい。 #include <cstdio> #include <algorithm> using namespace std; int b[2][3]; int c[3][2]; int allscore=0; int getState(int state,int i, int j) { int index=i*</algorithm></cstdio>…

ABC008D解いてみた

座標圧縮はやったことなかったので練習してみます。 まず、素直に実装するとこうなる。 詰まったところ 下のような巨大な配列を何も考えずにmemsetすると凄まじい時間がかかるので、基本的にはギリギリを攻める。 #include <cstring> #include <algorithm> #include <cstdio> #define MAX</cstdio></algorithm></cstring>…

ABC017C解いてみた

一つ取らない宝石を決めた時、もっともスコアが良い取り方はその宝石を取らない区間を持つ遺跡をできるだけ訪れた時だから、これは遺跡で集められる宝石の右端がその宝石より小さい遺跡すべてと、左端がその宝石より大きい遺跡すべてを訪れれば良い。遺跡で…

ABC003D解いてみた

ARCは難しすぎるのでABCからやることにしました。ABC003Dが難しく、満点解答は思いつかなかったので、解答を見ました。包除原理というやつです。 今回のでは、をXY区画の左端にものがない並べ方の集合、をXY区画の右端にものがない並べ方の集合、をXY区画の…

セグメント木でなぜかすごい詰まったところ

セグメント木で凄まじく詰まったためメモをしておく 下記のコードで、呼び出しの時、calcMin(a,b,0,0,n)ではなくcalcMin(a,b,0,0,N)でなければならない。要するに、セグメント木の実際に使う範囲を指定するのではなく、実際のセグメントのサイズで呼び出さな…

AGC018受けてみた

AGC018受けました! 結果はAの一問しかできずに終わりました(T_T)。 A 二つの数どうしで引き算をして作れるのはその二つの数の最大公約数の倍数なので、すべての数の最大公約数を求めて、その倍数が作れる。いつかB~Fまで同じようにかけたらいいですね!

ARC021B解いてみた

解説を読んで、自分のやり方と違ったので載せておきます。 xorには結合法則が成り立つことと、自分自身にxorをすると、0になることを利用して、の高次ビットから0と決め打ちして、整合性を確認しながらビットを埋めていけば自然に辞書順で最小となります。 #…

ARC018C解いてみた

ARC

見てもわからず、答えを見て実装してみました。 なお、この手のの漸化式による、乱数生成法を線形合同法と呼びます。 #include <cstdio> #include <cstdlib> #include <vector> #include <utility> #include <algorithm> #define AT(x,y) ((x) * M + y) using namespace std; typedef pair<int,int> P; typedef pair<int,P></int,p></int,int></algorithm></utility></vector></cstdlib></cstdio>…

ARC017C解いてみた

ARC

久しぶりに自力で解ける問題見つけました。蟻本の類題ですね! このように集合を半分に分けて列挙して答えを求めることを半分全列挙と呼ぶらしいです。 #include <cstdio> #include <algorithm> #include <cstring> using namespace std; int BucketA[(1<<16) + 10]; int BucketB[(1<<16)</cstring></algorithm></cstdio>…

ARC002C解いてみた

問題A,Bは特に解説読んでわかった。 問題C L,Rの全通りについての下記の漸化式に従った動的計画法を実行して求めることができる。をi番目までの最小のコマンド入力回数とします(普通のi番目です。例えば0番目といわれたら、0文字目つまり、何の文字も指しま…