問題 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となっているので、 $ 数列の長さ = 末項 - 初項 +…

問題 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(積集…

問題 D - equeue 解法 操作A-D(問題文より) 操作 A: D に詰められた宝石のうち、左端の宝石を取り出して手に入れる。 操作 B: D に詰められた宝石のうち、右端の宝石を取り出して手に入れる。 操作 C: 持っている宝石を 1 つ選んで D の左端に詰める。 操作 …

Amazon検索URLの末尾に &emi=AN1VRQENFRJN5 を追加することでAmazon以外の販売会社の商品が表示されなくなる(マーケットプレイス出品が非表示になる)と聞いた。実際に試してみた。 イヤホンの検索結果(通常) イヤホンでの検索結果URLに&emi=AN1VRQENFRJN5を…

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