Learning Algorithms

アルゴリズムの勉強メモ

やるだけ

CS Academy 050 Div. 2 Check Square

CS Academy 050 Div.2 Check Square CS Academy 感想 色々やり方がありそうだけど、頂点を見る順番で全探索した。 解法 4点の位置関係がわからないので、その関係を全探索する。順番に点をずらしながら辺を4本とって、その長さがすべて等しくなるような場合…

Codeforces Testing Round 1 C. Circular RMQ

Codeforces Testing Round 1 C. Circular RMQ Problem - C - Codeforces 感想 区間加算、区間最小値を処理する遅延セグメント木をライブラリに追加したので、貼るだけの問題で試しておいた。 解法 貼るだけ。ただし入力が親切じゃないので、getlineで入力を…

Atcoder Beginner Contest 057 D. Maximum Average Sets

Atcoder Beginner Contest 057 D. Maximum Average Sets D: Maximum Average Sets - AtCoder Beginner Contest 057 | AtCoder 感想 なぜかWAのまま放置していた。 解法 なんかやるだけ。 ただし$\ {}_n C _r \ $を求めるためにはパスカルの三角形による計算…

Atcoder Grand Contest 019 D. Shift and Flip

Atcoder Grand Contest 019 D. Shift and Flip 感想 結局やるだけだったけど、ひたすら補題の実装ができなかった。解説は自明なパートだけだらだらと書いていて最も知りたい部分が省略されていた。 解法 まず最終的に$\ a\ $のどの部分が$\ b\ $のどの部分に…

Atcoder Regular Contest 054 B. ムーアの法則

Atcoder Regular Contest 054 B. ムーアの法則 B: ムーアの法則 - AtCoder Regular Contest 054 | AtCoder 感想 はじめて三分探索を書いた。凸関数の解を求めるときに使えるやつ。零点が手で計算できるときはそっちの方が良いんだと思う。 解法 三分探索で、…

Atcoder ARC 061 D. すぬけ君の塗り絵 / Snuke's Coloring

Atcoder ARC 061 D. すぬけ君の塗り絵 / Snuke's Coloring D: すぬけ君の塗り絵 / Snuke's Coloring - AtCoder Regular Contest 061 | AtCoder 解法 最も愚直な方法は、$\ H * W\ $の配列を用意し、そこにクエリに従って色をつけていき、最後に$\ 3 * 3\ $の…

Atcoder AGC 017 B. Moderate Differences

Atcoder AGC 017 B. Moderate Differences B: Moderate Differences - AtCoder Grand Contest 017 | AtCoder 解法 数列において減少する回数を固定して、差分($\ B - A\ $)のとりうる最小最大を決めて条件を満たすものがあるかを判定する。例えば下限を考え…

Atcoder ABC 069 A. K-City

Atcoder ABC 069 A. K-City A: K-City - AtCoder Beginner Contest 069 | AtCoder 解法 $(n - 1) (m - 1)$を出力するだけ。$O(1)$。 実装 #include <bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; cout << (n - 1) * (m - 1) << endl; return</bits/stdc++.h>…

Atcoder ARC #010 D. 情報伝播

Atcoder ARC #010 D. 情報伝播 D: 情報伝播 - AtCoder Regular Contest 010 | AtCodern人の青木くんとm人のスパイが平面上にいて、青木くんは、自分を中心とする任意の半径をもつ円の内部に情報を拡散できる。スパイに情報がもれないように、青木くん全員に…

Atcoder ARC #006 D. アルファベット探し

Atcoder ARC #006 D. アルファベット探し D: アルファベット探し - AtCoder Regular Contest 006 | AtCoderある決められた図形A, B, Cの非負整数倍拡大図形が90度毎の回転を許していくつか描かれているので、A, B, Cがそれぞれ何個ずつ含まれているかを数え…

Atcoder ARC #022 B. 細長いお菓子

Atcoder ARC #022 B. 細長いお菓子 B: 細長いお菓子 - AtCoder Regular Contest 022 | AtCoder数列が与えられるので、その部分列の中で、相異なる数のみを含むもので最長のものの長さを答える問題。すごくシンプルなのだけれど、少し手こずった。いまどの区…