ちょっと幾何チックな問題 問題へのリンク 問題概要 考えたこと この手の問題では、 の大小関係が定まっていると考えやすい。そして、 でも でも、どちらでも一般性を失わないので、 として考えよう。 このとき、次のように整理できる。 ならば：すでに連結…

mod の練習。鉄則本の問題なので、コードのみ。 問題へのリンク 問題概要 最初、黒板に 0 という数が書かれている。以下の 回の操作を実行せよ。各操作では文字 と数 が与えられる。 = '+' のとき：黒板に書かれた数を、 を足した数に書き直す = '-' のとき…

最大公約数。鉄則本の問題なので、コードのみ。 問題へのリンク 問題概要 2 つの正の整数 の最大公約数を求めよ。 制約 コード #include <bits/stdc++.h> using namespace std; long long GCD(long long x, long long y) { if (y == 0) return x; else return GCD(y, x % y)</bits/stdc++.h>…

グリッド上の最短経路の数え上げをする DP。鉄則本の問題なので、コードのみ。 問題へのリンク 問題概要 のグリッドがあり、各マスは壁または通路である。左上マスと右下マスは通路である。 左上マスから右下マスへと、右方向と下方向の移動のみを繰り返し、…

LIS。鉄則本の問題なのでコードのみ。 問題へのリンク 問題概要 長さ の数列 の LIS の長さを求めよ。 制約 コード #include <bits/stdc++.h> using namespace std; const int INF = 1 << 29; int main() { int N, res = 0; cin >> N; vector<int> A(N); for (int i = 0; i < N; </int></bits/stdc++.h>…

dp[どこまで見たか][ビット] というタイプのビット DP。鉄則本の問題なので、コードのみ。 問題へのリンク 問題概要 のグリッドが与えられる。各マスは 0 または 1 である。いくつかの行を選んで、次の条件を満たすようにしたい。選ぶべき行数の最小値を求め…

コンテスト中最初に挑んだが解けず、その後も結局解けなかった。gcd convolution を思い出せなかった。 問題へのリンク 問題概要 長さ の正の整数からなる数列 、 が与えられる。これらの数列に対して 個のクエリが与えられる。 【クエリ】 正の整数 が与え…

すごく面白かった！ 問題へのリンク 問題概要 二次元平面上に点 と という 個の点がある。同一直線上に 3 点が乗ることはない。 の順列 であって、次の条件を満たすものが存在するかどうかを判定し、存在するならば 1 つ示せ。 【条件】 に対して、2 点 , を…

方針を立てるのは難しくないけど、とにかく重たい問題だった。 問題へのリンク 問題概要 人 に対して合計 票が集まった。これらの人のうち条件「自分よりも多くの票を集めた人が 人未満」を満たす人が当選となる。 票のうち途中まで開票されて、各人 には 票…

二部グラフ判定を書いたことがあれば、その要領で解ける！ 問題へのリンク 問題概要 頂点数 、辺数 の重み付き有向グラフが与えられる。各頂点 に値 を書き込む方法であって、どの辺 に対しても を満たすようなものを 1 つ求めよ (そのようなものが存在する…

計算量改善のことを本当に知らないと、TLE に悩むかもしれない。 問題へのリンク 問題概要 長さ の 2 つの数列 、 が与えられる。 1 以上 以下の整数 を選んで、 の最大値を求めよ。 制約 考えたこと 最も素直に考えると、次のように二重 for 文を用いて解き…

各文字がどこにあるのかを求めると楽になる。 問題へのリンク 問題概要 'A' から 'Z' までの文字を 1 つずつ含む文字列 が与えられる。 内部での 'A' から 'B' への移動距離 (index の差分) 'B' から 'C' への移動距離 (index の差分) 'C' から 'D' への移動…

文字列、配列、for 文の練習 問題へのリンク 問題概要 文字列 が与えられる。 文字列 の長さが であるような の個数を求めよ。 考えたこと for 文を使って について、 if (S[i].size() == i) というように判定していけばよい。 コード #include <bits/stdc++.h> using names</bits/stdc++.h>…