SRM Div2 の解説記事です。まだまだ抜けが有ります。https://github.com/motxx/SRM-Div2

#include <bits/stdc++.h> using namespace std; // rep #define REP(i,a,b) for(int i=a;i<b;i++) #define rep(i,n) REP(i,0,n) struct Edge { int to, cost; }; // typedef typedef vector<Edge> Edges; typedef long long ll; int N; Edges G[2010]; bool notuse[2010]; typedef ll Weight; typedef pair<Weight, int> R…</weight,></b;i++)></bits/stdc++.h>

問題文 本来の授業時間 d が与えられる。授業の開始を t 遅らせるとき、更に t^2 の時間だけ授業時間が少なくなる。授業時間をできるだけ少なくするための t を求めよ。解説 入力が10^18なので普通に線形探索は不可。二分探索しても良いが、整数型で探索範囲…

解答 全探索。Sの先頭からとprefixの末尾からの一致と、Sの末尾とsuffixの先頭からの一致をみるループを回せばよい。反省 誤読しまくってやばかった。

解法 誤差のない解法を目指す。 #define INF (1<<29) #define EPS (1e-9) class ArithmeticProgression { public: double minCommonDifference(int a0, vector <int> seq) { if(seq.empty()) { return 0.; } for(int i=0; i</int>

解法 開始時間の全探索なのだけれど問題文読めなくて自力で出来なかった。 class Embassy { public: int visaApplication(vector <int> forms, int dayLength, int openTime) { int N = forms.size(); int ans = INF; rep(st, dayLength) { int sum = 0; int time</int>…

問題 与えられた 整数 N(32-signed integer. 1解法 ビット化して辞書順で次に現れるビット列を持つ数字が答え。editorial解。反省 はじめビットの小さい桁から見て 1 と 0 とを一度入れ替える、みたいなことして解こうとしていた。next_permutation() を一回…

問題文 'A', 'B', 'C' のみの文字を用いて、長さ n の文字列が構成される。文字列のうち、その部分文字列において 'A', 'B', 'C' の文字が順不同で１つずつ連続しているようなものがあるものは、禁止文字列と定義する。禁止文字列でない長さ n の文字列の総…

問題 任意の文字の位置を入れ替えた部分文字列の候補が複数与えられる。 重複を許してこれらを接続して、与えられた元の文を構成するものを考える。そのために部分文字列の文字位置の入れ替えが必要であるが、その回数の総和が最小であるものを答えよ。ただ…

問題文 ある文字列の部分文字列の配列が渡される。この時元の文字列の最小の長さを求めよ。 ただし各々の部分文字列は、それらの先頭の文字の座標が一つ前の部分文字列の座標以上の位置になっている。解法 前の座標を記録しながら部分文字列の一致をみる。は…

解法 いくらかパターンをイメージすると、長いのから順に消費していけば良いことが分かる。 class OlympicCandles { public: int numberOfNights(vector <int> C) { int cnt = -1; for(int i=0; i<C.size()+1; i++) { sort(ALL(C), greater<int>()); for(int j=0; j<i; j++) { if(C[j] > 0) C[j] --; else goto EXIT; } cnt ++; } EX</i;></c.size()+1;></int>…

解法 各々についてDFSして足し合わせる。メモ化すると良い。 typedef long long ll; class CorporationSalary { public: ll memo[55]; ll dfs(vector<string> &R, int idx) { if(memo[idx]) return memo[idx]; ll& ret = memo[idx]; int cnt = 0; for(int i=0; i</string>

解法 先にstringの階層構造をvector化すると扱いやすくなる。 class RelativePath { public: vector<string> make(string str) { int N = str.size(); for(int i=0; i<N; i++) { if(str[i] == '/') { str[i] = ' '; } } stringstream ss(str); vector<string> ret; ret.push_back("ROOT"); while(ss >> str) ret.push_back(str); return ret; } st…</n;></string>

class RevealTriangle { public: vector <string> calcTriangle(vector <string> Q) { int N = Q.size(); int cnt; do { cnt = 0; for(int i=0; i</string></string>

解法 メモ化再帰 class RandomSort { public: map<vector<int>, double> mp; double getExpected(vector <int> permutation) { if(mp.count(permutation)) { return mp[permutation]; } double ret = 0.; double cnt = 0.; for(int i=0; i</int></vector<int>

class TheLuckyNumbers { private: int solve(long long n, int a, int b) { if(n > b) return 0; return solve(10*n+4, a, b) + solve(10*n+7, a, b) + (a<=n&&n<=b); } public: int count(int a, int b) { return solve(0, a, b); } };

解法 与えられたデータを用いたとき、最大の対象な分割のための線分の数を求める。 要素数が8までなので、next_permutation で回して累積和を取り+50となる要素のペアを数え上げる。 #define ALL(x) (x).begin(), (x).end() class SymmetricPie { public: in…

解法 カタラン数を求めるとよい。 http://mathworld.wolfram.com/CatalanNumber.htmlWikipediaの格子状の経路数え上げの項目が参考になる。Nを1増加して計算したうえで、はじめの経路分を引けばよい。 class FIELDDiagrams { public: ull nCr(ull n, ull r){…

解説 乗数決め打ちして二分探索で解こうとしていたけど、乗数の大きい物から計算していけばその必要はなかった。2^60 = 1.1529215e+18 > 10^18 は覚えておいたほうが良い。 また、桁落ちを考慮してEPSを挟む必要がある（正答コード見てわかりました） class …

解法 直径を大きい順にソートして(1)r,b,r,b,... or (2)b,r,b,r,...の順で貪欲でつめる。red or blue の要素で直径が H 以上のものが尽きたら -1 を出力。そうでなければ長方形の残りの幅を越えた時点で最適。(1)と(2)の小さい方が答え。 class ColoringRect…

#include <bits/stdc++.h> using namespace std; #define ALL(x) (x).begin(), (x).end() class AmebaDiv1 { public: int count( vector <int> X ) { int N = X.size(); set<int> st1(ALL(X)), st2; for(int i=0; i</int></int></bits/stdc++.h>

問題概要 K個以上の座標を完全に包含できる正方形の最小面積を求めよ。制約 座標の要素数：2〜100個 -10^9 解法 与えられた座標のうち「『1点の座標(X, Y)』または『2点の x, y それぞれの min を取った座標(X, Y)』」から一回り大きい座標(X-1, Y-1) を始点…

解法 与えられた配列をソートしたとき、要素 0 番目から順に見てある要素の猫までは右に進み、ある要素の猫からは左に進む。その区切りの位置を全探索する。 #include<bits/stdc++.h> using namespace std; #define INF (1<<29) #define ALL(x) (x).begin(), (x).end() #def</bits/stdc++.h>…

問題概要 はじめからある 1文字を「コピー」「ペースト」「1文字削除」の三操作を用いて、目的の個数にする最小操作回数を求めよ。解法 dp[i] := i個の文字が描画されるための最小操作回数 j ( 1 #include<bits/stdc++.h> using namespace std; #define INF (1<<29) class E</bits/stdc++.h>…

問題概要 'P'のみで作られる長方形区間の面積の最大値を求めよ。ただし、K回まで 'A' または 'P' を取って '.'(空) に置く操作ができる。解法 1. 全ての 'A', 'P', '.' の数を数える。 2. 全ての長方形Rを全探索する。 3-1. '.' が全体の正方形のグリッドに…

解法 ソートして累積和とった上で全探索。O(N^2) 元の配列に番号付けがされているが、全ての番号の数だけ最小のフロアを集めるので番号付けに意味がなく、いきなりソートして良い。 #include <bits/stdc++.h> using namespace std; #define INF (1<<28) class BuildingHeigh</bits/stdc++.h>…

解法 左右対称に着目して、その場合の数を求めるためにmapで数え上げた文字の数を半分にする。 奇数の文字が２つ以上あったら回文は作れない。一つの文字のみが奇数なら、中央に一文字置けば回文になる。後は同じものを含む順列を利用する。 （回文の半分の…

解法 互いに (i)場所を選び (ii)ファンの人数 a, b を選び (iii)ファンの人数が一致する（a = b）とき (iv) それぞれ 1 / (ファンの人数の範囲) を足し合わせる。 class TheFansAndMeetingsDivTwo { public: double find(vector <int> minJ, vector <int> maxJ, vector <int></int></int></int>…

解法 ソートして初めからK番目までの和反省 EasyとMediumが似たような問題だった。本番でChallengeフェーズのとき Easy の問題を Med の問題と思い込んで、無意味に Easy 落とそうとして失敗した。 #include <bits/stdc++.h> using namespace std; #define allof(c) (c).beg</bits/stdc++.h>…

解法 ソートして区間[i, i+M)を足したものをすべて調べる。heights[i+M-1]*M との差分が最小のとき、その差分を出力するだけ。 #include <bits/stdc++.h> using namespace std; #define allof(x) (x).begin(), (x).end() class BuildingHeightsEasy { public: int minimum(i</bits/stdc++.h>…