AtCoder Beginner Contest 322 - AtCoder B - Prefix and Suffix 問題文通りに愚直にやる #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 >> m; string s,t; cin >> s >> t; auto t1 = t.substr(0,n); auto t2 = t.substr(m-n); int ans</n;i++)></bits/stdc++.h>…

NS Solutions Corporation Programming Contest 2023（AtCoder Beginner Contest 303） - AtCoder B - Discord 隣接行列で 人 i が 人 j と前後で並んでいたか？を持っておいて、一度も並んでいない二人組の数を集計する #include <bits/stdc++.h> using namespace std; #de</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>…

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>…

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

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>…

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>…

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 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>…

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

問題 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 - Peddler N個の町がある。 町を結ぶM本の道がある。 それぞれの道は $ X_i $ から $ Y_i $ への一方通行になっている。 $ 町_i $ では $ A_i $ 円の金(gold)を買ったり売ったりできる。 ある町で金を買い、いくつかの道を使った後、買った町とは別の…

問題 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 - 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>…

問題 E - Traveling Salesman among Aerial Cities 解法 巡回セールスマン問題。 ナイーブな全探索では $O(N{!})$ かかるため、 $ n=17 $ では時間切れになる。 そこでbitDPと呼ばれる手法を使う。 bitDPでは計算量が $ O(N{^2}2{^n})$ となるため今回の制約…

問題 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>…

問題 C - Ubiquity 公式解説にある通り、包除原理を理解していれば数行で解ける問題。 包除原理にたどり着けず納得が行かなかったので公式解説動画で言及されていたDP解法で解いてみた。 DP解法 DPは [N][0を含んでいるかどうか][9を含んでいるかどうか] で…