AtCoder
問題 E - Traveling Salesman among Aerial Cities 解法 巡回セールスマン問題。 ナイーブな全探索では $O(N{!})$ かかるため、 $ n=17 $ では時間切れになる。 そこでbitDPと呼ばれる手法を使う。 bitDPでは計算量が $ O(N{^2}2{^n})$ となるため今回の制約…
問題 D - Game in Momotetsu World 解法 DFSのような探索ではお互いの最適行動がわからないため解くことができない。 ポイントは、 最終地点(右下)から最適なスコアを決めていけばDPで処理できる。 takahashiくんはスコアを最大化、aokiくんはスコアを最小化…
問題 D - Poker 1-9までのカードがkセットある。 高橋くんと青木くんにランダムにカードを5枚配り、最後の一枚だけ伏せられている。 この状態で高橋くんが青木くんに勝つ確率を求める。 解法 5枚目を全探索し、高橋くんが勝つ場合の数を算出する 全事象の数…
SuntoryProgrammingContest2023(AtCoder Beginner Contest 321) - AtCoder B - Cutoff N ラウンド目に取り得る値を全探索する #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,x; cin >> n >> x; vector<int> a(n-1); REP(i,n-1) cin >> a[i]; int ans =</int></n;i++)></bits/stdc++.h>…
問題 D - Squares 解法 解説: Editorial - HHKB Programming Contest 2020 上記解説手順で解いてみる #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) typedef long long ll; const int mod = 1000000007; // mintは省略 https://github.com/atcoder/ac-library int main() { int t; cin >> t; REP(i,t) {…</n;i++)></bits/stdc++.h>
問題 D - Logical Expression 解法 DPを使った解法。入力例1で考えてみる。 2 AND OR 以下のDP配列を定義する。 dp[n][x]:= n個までの文字列で結果がx(0/1)になるケースの数 n = 0 true / false それぞれ1通りのみ dp[0][0] = 1 dp[0][1] = 1 n = 1 AND(積集…
問題 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 - Squared Error 解法 Nの制約が $ 2 ≤ N ≤ 3 × 10 ^ 5 $ のため $ i,j $ の組み合わせを全探索すると $ O ( N ^ 2 ) $ で間に合わない。 そこで制約の $ |A_i| ≤ 200 $ に注目する。$ |A_i| $ の取る値は -200〜200 の範囲となっていて小さいことが…
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>…
Denso Create Programming Contest 2023 (AtCoder Beginner Contest 309) - AtCoder B - Rotate 愚直に時計回りへずらしていった。もっと簡単な方法あるかな。 #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); REP(i,n) ci</string></n;i++)></bits/stdc++.h>…
A - Replace C or Swap AB 公式解説 を元に解いたのでメモ。 解説を見てもなかなかシュッと実装できなくて難しい #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define endl '\n' int main() { int t; cin >> t; REP(_,t) { int n; string x,y; cin >> n >> x >> y; x += 'C'; y += 'C</n;i++)></bits/stdc++.h>…
B - Make Multiples 公式解説 を元に解いたのでメモ。 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define endl '\n' using ll = long long; template<class T> void chmin(T& a, T b) { a = min(a,b); } int main() { ll n,a,b,c; cin >> n >> a >> b >> c; vector<ll> x(n); REP(i,n) cin >>…</ll></n;i++)></bits/stdc++.h>
問題 D - Leaping Tak 解法 素直にDPで解けそうだが、愚直にnに対して全ての移動を試すと $ O(N{^2}) $ となり $ 2≤N≤2×10{^5} $ の制約下でTLEしてしまう。 // このコードはTLEする #include <bits/stdc++.h> using namespace std; #define COUT(x) cout<<(x)<<"\n" #defin</bits/stdc++.h>…
問題 D - People on a Line 解法 以下の有向グラフを作り、DFSで頂点間の距離に矛盾が生じていないかを調べる。 $ L_i $ から $ R_i $ まで距離 $ D_i $ $ R_i $ から $ L_i $ まで距離 $ -D_i $ ただし、M個の入力から得られるグラフは連結していない場合が…
問題 D - Patisserie ABC 解法 公式解説が詳しいのでそこに書いてある通り。 https://img.atcoder.jp/abc100/editorial.pdf $ x,y,z $ の3要素の正方向と負方向の組み合わせは $ 2 ^ 3 $ 通り。 それぞれの組み合わせで $ x,y,z $ の合計が大きいものから $ …
問題 D - We Love ABC 解法 ? があると複雑なため、まずは ? 抜きで考えてみる。 素朴に3重ループでA->B->Cとなるパターンを総当りしてみる。 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) using ll = long long; int main() { string s; cin >> s; int n = s.size(); ll ans = 0; REP(i,n) {</n;i++)></bits/stdc++.h>…
問題 C - Shapes 解法 # か . どちらかの情報がわかれば図形は作れるので、今回は # の座標集合だけを持つようにして考える。 図形の変形は以下のように考える。 平行移動は最も左にある座標を選び、それを原点に移動させる形で全体移動させて合わせる。 90…
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>…
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>…
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>…
キーエンスプログラミングコンテスト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>…
TOYOTA MOTOR CORPORATION Programming Contest 2023#2 (AtCoder Beginner Contest 302) - AtCoder B - Find snuke 8方向全部の処理をそれぞれ記述すると行数が増えてバグらせやすい。 共通部分を考えて行数をなるべく少なくするように心がける。 #include <bits/stdc++.h> </bits/stdc++.h>…
Tokio Marine & Nichido Fire Insurance Programming Contest 2023(AtCoder Beginner Contest 304) - AtCoder B - Subscribers 問題文の通りにやる。 条件がたくさんあるが、よく見ると桁が増えて行く以外は同じ処理だとわかるのでうまくループ処理にすると…
Toyota Programming Contest 2023#8(AtCoder Beginner Contest 333) - AtCoder B - Pentagon #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define endl '\n' int main() { string s,t; cin >> s >> t; auto f = [&](string s) { int x = s[0]-'A', y = s[1]-'A'; int d = abs(x-…</n;i++)></bits/stdc++.h>
UNIQUE VISION Programming Contest 2024 Spring(AtCoder Beginner Contest 346) - AtCoder B - Piano w, b の制約が 100 以下のため十分な長さの s を用意しておいて全探索する #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define endl '\n' const string t = "wbwbwwbwbwbw"; int main() { int w,b; cin >…</n;i++)></bits/stdc++.h>
問題 C - Ubiquity 公式解説にある通り、包除原理を理解していれば数行で解ける問題。 包除原理にたどり着けず納得が行かなかったので公式解説動画で言及されていたDP解法で解いてみた。 DP解法 DPは [N][0を含んでいるかどうか][9を含んでいるかどうか] で…
問題 D - Good Grid 解法 $ (i+j) \% 3 $ なので条件を満たすために使う色は3色のみ 事前に $ (i+j) \% 3 $ を3パターンに塗ったときのそれぞれのコストを計算しておく 全ての色の組み合わせについて調べる(全探索)。$O(N{^3})$ となるが $ C=30 $ の制約に…
問題 E - Queen on Grid 解法 DP + 累積和。 dp配列は、 dp[i][j] = {i,j}地点に到達できる場合の数 で考える。 するとdp[i][j] は以下のように3方向のdpの累積を足すと求められる。 dp[i][j] = dp[i][j-1] + dp[i][j-2] ... + dp[i][0] + dp[i-1][j] + dp[i…
問題 D - AtCoder Express 2 解法 列車の区間L-Rを二次元座標として考える。 Q個のクエリを求める必要があるが、都度計算すると間に合わない。 二次元累積和を使って前計算しておくことで、Q個のクエリに対して高速に答えを出す。 #include <bits/stdc++.h> using namespace</bits/stdc++.h>…
問題 D - Decayed Bridges 解法 ぱっと見でUnionFindだろうなと思ったが、少々工夫が必要だった。 橋の削除操作は難しいため、逆順から橋を追加していく操作を考える 橋が一つもない状態の不便さは $ {}_n C_2 $ で求まる 橋を追加後の不便さは、次で求まる …