キーエンスプログラミングコンテスト2022（AtCoder Beginner Contest 274） - AtCoder B - Line Sensor 二重ループでカウント #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) #define endl '\n' int main() { int h,w; cin >> h ></bits/stdc++.h>…

AtCoder Beginner Contest 272 - AtCoder B - Everyone is Friends 人iが参加した舞踏会を隣接行列で持っておいて全探索。O(N3) #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) #define endl '\n' int main() { int n,m; cin >> n</bits/stdc++.h>…

KYOCERA Programming Contest 2022（AtCoder Beginner Contest 271） - AtCoder B - Maintain Multiple Sequences 隣接リストで持つ #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) #define endl '\n' int main() { int n,q; cin </bits/stdc++.h>…

TOYOTA MOTOR CORPORATION Programming Contest 2022(AtCoder Beginner Contest 270) - AtCoder B - Hammer 場合分けをする ゴールが正の場合と負の場合を両方考えるのは面倒なので、負の場合は正に置き換えてやると楽 #include <bits/stdc++.h> using namespace std; int m</bits/stdc++.h>…

NEC Programming Contest 2022 (AtCoder Beginner Contest 267) - AtCoder B - Split? 1番のピンが立っていたらNo 各レーンで1本でもピンが立っているレーン番号の集合を取る ピンが立っているレーン番号を昇順にみていって間が空いていたらYes #include <bits/stdc++.h> us</bits/stdc++.h>…

freee Programming Contest 2022（AtCoder Beginner Contest 264） - AtCoder B - Nice Grid 法則性を数式にうまく落とし込めなかったので、15x15マスを実際に書いた。 解説にある方法ではチェビシェフ距離（チェス盤距離）で考えると $ max \lbrace |R-8|,|…

AtCoder Beginner Contest 261 - AtCoder B - Tournament Result 全探索で a[i][j], a[j][i] に矛盾がないか調べる #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) #define endl '\n' int main() { int n; cin >> n; vector<string> a(n);</string></bits/stdc++.h>…

AtCoder Beginner Contest 260 - AtCoder B - Better Students Are Needed! sortする際に 同点の場合は番号の小さい方を優先する となっていることに気をつける #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) #define endl '\n' </bits/stdc++.h>…

Aising Programming Contest 2022（AtCoder Beginner Contest 255） - AtCoder B - Light It Up Bにしては難しい #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) int main() { int n,k; cin >> n >> k; vector<int> a(k),x(n),y(n); RE</int></bits/stdc++.h>…

NOMURA Programming Contest 2022（AtCoder Beginner Contest 253） - AtCoder の参加メモ B - Distance Between Tokens 2つのoの位置を見つけてそのマンハッタン距離を計算する #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) in</bits/stdc++.h>…

AtCoder Beginner Contest 252 - AtCoder の参加メモ B - Takahashi's Failure #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) int main() { int n,k; cin >> n >> k; vector<int> a(n),b(k); int mx = -1; REP(i,n) { cin >> a[i]; mx</int></bits/stdc++.h>…

Panasonic Programming Contest 2022(AtCoder Beginner Contest 251) - AtCoder の参加メモ B - At Most 3 (Judge ver.) #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) int main() { int n,w; cin >> n >> w; vector<int> a(n); REP(i</int></bits/stdc++.h>…

AtCoder Beginner Contest 250 - AtCoder の参加メモ B - Enlarged Checker Board 適当に実装してif文だらけになるとバグらせやすいので注意する。 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) int main() { int n,a,b; cin >></bits/stdc++.h>…

Monoxer Programming Contest 2022（AtCoder Beginner Contest 249） - AtCoder の参加メモ B - Perfect String 大文字、小文字の判定 配列のユニーク判定 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) int main() { string s; </bits/stdc++.h>…

Daiwa Securities Co. Ltd. Programming Contest 2022 Spring（AtCoder Regular Contest 138） - AtCoder のメモ A - Larger Score dp配列へ dp[i] = a[i]〜a[n-1] の中で最小の値 を事前に持っておく。 a[k]〜a[n-1] の値を、それぞれ最小で何回入れ替える…

AtCoder Beginner Contest 246 - AtCoder の参加メモ C - Coupon greedy。 クーポンでX円値引きできる商品はクーポンを使えるだけ使って良い。 X円未満しか値引きできない商品だけ残ったときは、降順にソートして値段が高いものから順番にクーポンを使ってい…

m1 MacBookAir に買い替えたのでAtCoder用にC++コンパイルできる環境を構築した際のメモ $ brew install gcc $ sudo mkdir /usr/local/bin $ which gcc-11 /opt/homebrew/bin/gcc-11 $ which g++-11 /opt/homebrew/bin/g++-11 $ sudo ln -s /opt/homebrew/bi…

AtCoder Beginner Contest 245 - AtCoder の参加メモ C - Choose Elements 直前の条件を満たす数を記憶しておいて、Nまで遷移可能であればYes #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) int main() { int n,k; cin >> n >> k</bits/stdc++.h>…

AtCoder Beginner Contest 244 - AtCoder の参加メモ C - Yamanote Line Game インタラクティブ問題って珍しいね。 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) int main() { int n; cin >> n; vector<bool> used(2005); int cur = 1</bool></bits/stdc++.h>…

AtCoder Beginner Contest 243 - AtCoder の参加メモ C - Collision 2 yが同値の座標同士で右向きのx最小値、左向きのx最大値を調べて、 右向きのx最小値 < 左向きのx最大値 になっていたら Yes #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=</bits/stdc++.h>…

問題 D - Online games 解法 経路圧縮 + imos法 ログイン日を+1, ログアウト日を-1 してimos法*1で集計する。 取りうる日付が 109 x 2 あるので、座標圧縮を行う必要がある。 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);i++) </bits/stdc++.h>…

問題 C - Shapes 解法 # か . どちらかの情報がわかれば図形は作れるので、今回は # の座標集合だけを持つようにして考える。 図形の変形は以下のように考える。 平行移動は最も左にある座標を選び、それを原点に移動させる形で全体移動させて合わせる。 90…

問題 D - Pond 解法 二分探索 + 二次元累積和 という典型テクニックを組み合わせて解ける問題だった。 公式解説が詳細なので詳しくはそちらを参照 Editorial - AtCoder Beginner Contest 203（Sponsored by Panasonic） #include <bits/stdc++.h> using namespace std; #def</bits/stdc++.h>…

問題 D - Game in Momotetsu World 解法 DFSのような探索ではお互いの最適行動がわからないため解くことができない。 ポイントは、 最終地点(右下)から最適なスコアを決めていけばDPで処理できる。 takahashiくんはスコアを最大化、aokiくんはスコアを最小化…

問題 C - MAD TEAM 解法 チームの総合力値を二分探索することで解ける問題。 まず総合力は、可能な値=0、不可能な値=1e9+1(取りうる最大値の値+1) とおくことができる。 この範囲で二分探索を行う。 ある値xが成立するかどうかは次のように求めることができ…

問題 C - Squared Error 解法 Nの制約が $ 2 ≤ N ≤ 3 × 10 ^ 5 $ のため $ i,j $ の組み合わせを全探索すると $ O ( N ^ 2 ) $ で間に合わない。 そこで制約の $ |A_i| ≤ 200 $ に注目する。$ |A_i| $ の取る値は -200〜200 の範囲となっていて小さいことが…

問題 D - Poker 1-9までのカードがkセットある。 高橋くんと青木くんにランダムにカードを5枚配り、最後の一枚だけ伏せられている。 この状態で高橋くんが青木くんに勝つ確率を求める。 解法 5枚目を全探索し、高橋くんが勝つ場合の数を算出する 全事象の数…

問題 E - Come Back Quickly 解法 ダイクストラによる解法 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) using P = pair<int,int>; using Edge = struct { int to; int cost; }; const int INF = 1e9; vector<int> a,b,c; int n,m; vector<vector<Edge>> g; // s: スタート位置 vect</vector<edge></int></n;i++)></bits/stdc++.h>…

問題 C - Digital Graffiti 解法 H行W列のマス目があり、. は白、# は黒で塗られている。 黒で塗られている部分を多角形として見たとき、何角形になるかを求める問題。 まず問題文が曖昧でサンプルが1ケースしかなく、意図通りに読み取ることが難しかった。 …

問題 D - Staircase Sequences 整数からなる公差 1 の等差数列のうち、総和が N であるものはいくつあるでしょうか？ 解法 等差数列の和は以下で求められる $ s = (初項 + 末項) * 数列の長さ / 2 $ 公差が1となっているので、 $ 数列の長さ = 末項 - 初項 +…