貪欲法 葉巻が作れなくなるまで順番に作っていく 一本ずつシミュレーションするとTLE public class Main { public static void main(String[] args) { final Scanner cin = new Scanner(System.in); while (cin.hasNextInt()) { long n = cin.nextLong(); fi…

作られる数の集合を見ていくとパターンがあることに気付く JavaとCで速度がだいぶ違うが、そういうものなのだと思う public class Main { public static void main(String[] args) { final Scanner scanner = new Scanner(System.in); final int S = scanner…

metaballの値を順に足していき、総和の半分と等しくなればそれが答え import java.util.Scanner; public class Main { public static void main(String[] args) { final Scanner cin = new Scanner(System.in); for (int N; (N = cin.nextInt()) != 0;) { fi…

時間制限が緩いので条件を丁寧に書けば通る static int type[256]; bool check(const string& s) { vector<int> types; for (string::const_iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it) { types.push_back(type[*it]); } if (find(types.begin</int>…

三次元の幅優先探索 広げる方向は6方向 static const int dx[] = {1, -1, 0, 0, 0, 0}; static const int dy[] = {0, 0, 1, -1, 0, 0}; static const int dz[] = {0, 0, 0, 0, 1, -1}; int main() { for (int X, Y, Z; cin >> X >> Y >> Z && (X || Y || Z);…

300x300なので幅優先探索で十分 広げる方向は8方向 static const int dx[] = {2, 2, 1, 1, -1, -1, -2, -2}; static const int dy[] = {1, -1, 2, -2, 2, -2, 1, -1}; int main() { int numberOfTests; cin >> numberOfTests; for (int testIndex = 0; testI…

幅優先探索 広げる方向は8方向 static const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}; static const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1}; int main() { for (int height, width; cin >> height >> width && (height || width); ) { static char maze[1…

数列の公式を当てはめるだけ 正負で式が微妙に変わる点に注意する 正負で分けずに解く方法もあったはず・・・ ll myabs(ll i) { return i >= 0 ? i : -i; } ll calc(ll i) { const ll sign = i / myabs(i); i = myabs(i); const ll value = (i * (i + 1)) / …

動的計画法 横方向でここからここまでの和というテーブルを作り、 縦方向でそれらを足し合わせる O(N^4) int main() { int N; scanf("%d", &N); for (int row = 0; row < N; ++row) { for (int column = 0; column < N; ++column) { int value; scanf("%d", …

制限時間が緩いので全探索を定数レベルで高速化すれば通る bool compareByConditions(const string& lh, const string& rh) { return lh.size() != rh.size() ? lh.size() > rh.size() : lh > rh; } string toString(int value, int length) { char buffer[1…

左/右に降りる場合のビットの変換にパターンがある それをそのまま書けば良い ビット演算のみで一行で書くこともおそらく出来る int main() { int numberOfTestCases; cin >> numberOfTestCases; for (int caseIndex = 0; caseIndex < numberOfTestCases; ++…

動的計画法 パスカルの三角形を定義通り書けば良い int main() { ll dp[128][128]; memset(dp, 0, sizeof(dp)); dp[0][0] = 1; for (int n = 1; n < 128; ++n) { for (int m = 0; m < 128; ++m) { if (m) { dp[n][m] += dp[n - 1][m - 1]; } dp[n][m] += dp[…

動的計画法 直前のマスの最適解を用いて現在のマスの最適解を求める int main() { int N; cin >> N; int first; cin >> first; vector<int> dp; dp.push_back(first); int bestAnswer = INT_MIN; for (int n = 2; n <= N; ++n) { vector<int> next; for (int i = 0; i </int></int>…

素直に実装するのみ 問題文を読み間違えて1WA int main() { int caseIndex = 0; for (int S, T, M; cin >> S >> T >> M && (S || T || M); ) { int counter[128][3]; memset(counter, 0, sizeof(counter)); for (int s = 0; s < S; ++s) { int Id; cin >> Id…

2点をfor文で回す 対応する残り2点が存在するかどうかをlog(N)で調べる int main() { for (int n; cin >> n && n; ) { set<pair<int, int> > positionSet; vector<pair<int, int> > positions; for (int i = 0; i < n; ++i) { int x, y; cin >> x >> y; positions.push_back(make_pair(x, y</pair<int,></pair<int,>…

全部同じ高さになるように移動するのみ int main() { int caseIndex = 0; for (int n; cin >> n && n; ) { vector<int> heights; int sum = 0; for (int i = 0; i < n; ++i) { int height; cin >> height; heights.push_back(height); sum += height; } const int</int>…

おにゅうPのクソゲー実況プレイを歌ってみました。知り合いから教えてもらったフリーの音程補正プラグインを使ってみました。自分の音程の不安定さをひしひしと感じましたorz

深さ優先探索 初めに待ちを固定して手に加えた状態から探索開始 深さ0〜3では順子・刻子を全数検査 深さ4では頭を全数検査 解となる文字列の生成ではどの順子・刻子・頭に待ちがあるかを固定して生成 重複した解が出力されないようsetを使用 途中状態をメモ…

動的計画法 以下の三つのパターンを考えれば良い 一つ前から縦のタイルを置くパターン 二つ前から横のタイル二つを置くパターン 二つ前から正方形のタイルを置くパターン 組み合わせの数が膨大になるため多倍長整数が必要となる nが64ビットまでかつmod何と…

動的計画法 次に奇数の液体を飲む場合は偶数番目の液体を飲んだ後の力の最大値+strengthに更新する 次に偶数の液体を飲む場合は上記の逆 int main() { int odd = INT_MIN / 2; int even = 0; int P; cin >> P; for (int i = 0; i < P; ++i) { int strength; …