ゲーム問題が苦手すぎる・・・・
CPSCO2019 Session2 D Two Piles
問題概要
枚のコインがある 1 つの山と、
枚のコインがある 1 つの山がある。 この2つの山を使ってAliceとBobがゲームをする。Aliceを先手として、2 人は以下の操作を交互に繰り返す。
- 1枚以上のコインがある山を選ぶ。この山の枚数を
とする
- その後2つの山から合計で
どちらの山にもコインがなくなったときの操作を終了し、最後に操作した人が勝者となる。
制約
考察
- サンプルだけでは分からないので実験してみる
- 以下に例と最適に行動したときの遷移を示す。
- 例1 初期状態が
=
の時、この後は
→
となり勝者はBob
- 例2 初期状態が
の時、この後は
→
→
となり勝者はAlice
- 例3 初期状態が
の時、この後は
→
→
→
- どうやら片方の山の枚数が1枚になるとその後は1枚ずつ取るのが最適になるっぽい
- そして片方が1枚になった時、もう片方の枚数が奇数ならば、相手に負けの状態を押し付けられるのでAliceが勝者となる（1枚の山の枚数も数えて残り枚数が偶数ならば勝利と考えても良い）（実験より分かったこと）ということで、先手が最初に片方の山を1枚にする操作をしてみる。
- ここではまず、山
を選び、
枚取る）、
からは1枚取るとする（
- この時取るコインの枚数は
枚となり、山
枚なので、残り枚数の合計は
枚となる。つまり、操作後の
- 山
- 以上をまとめると、
ソースコード
※マクロは使っていないので無視してください
#include<iostream> #include<vector> #include<algorithm> #include<cctype> #include<utility> #include<string> #include<cmath> #include<cstring> #include<queue> #include<map> #include<set> #define REP(i, n) for(int i = 0;i < n;i++) #define REPR(i, n) for(int i = n;i >= 0;i--) #define FOR(i, m, n) for(int i = m;i < n;i++) #define FORR(i, m, n) for(int i = m;i >= n;i--) #define SORT(v, n) sort(v, v+n); #define VSORT(v) sort(v.begin(), v.end()); #define llong long long #define pb(a) push_back(a) using namespace std; typedef pair<int, int> pii; typedef long long int ll; template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T, typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...)); } template<typename T, typename V> typename enable_if<is_class<T>::value == 0>::type fill_v(T& t, const V& v) { t = v; } template<typename T, typename V> typename enable_if<is_class<T>::value != 0>::type fill_v(T& t, const V& v) { for (auto& e : t) fill_v(e, v); } #define ARRAY_MAX 1005 const ll INF = 1e9 + 7; int main() { int a, b; cin >> a >> b; if ( (a % 2) == 0 || (b % 2) == 0) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0; }
タイポでWAになるのをやめなさ～い！！(BFS)
AGC033 A Darker and Darker
問題概要
縦行、横
行のマスが与えられ、
が’#’のときは黒マス、’.'のときは白マスになっている。全てのマスが黒色になるまでに各ステップごとに以下の操作を行う。
- 黒マスに隣接する白色のマスを全て黒色に変える
この操作を繰り返す時、何回で全てのマスが黒色になるか求める
制約
は'#'または'.'
- マスの初期状態に黒色のマスは必ず1つは含まれる
考察
- 黒色で埋めていく感じに見える
- こういうマスを埋めていく時にBFSは使えそう
- 今回は何回で全て黒色で埋まるのかを求めないといけないので埋めるときのステップ数が欲しい
- ん～分からん
- そこでサンプル2で実験すると、各ステップの最初の状態の黒色のマスの周辺を埋める操作になっているな～と
- ならキューの性質を上手く利用してステップ1での黒マスを全てキューに詰めておいて、そこからBFSをして、ステップ2の最初で黒マスになっているものたちをキューに詰め込んでいけばステップ数を保持できそう
- ステップ1の黒色マスを最初にキューに詰め込んでおくと何がいいのかというと、ステップ2の最初の状態で存在している黒色マス周辺を黒色で埋める操作はステップ1の最初の状態での黒色マスの周辺を黒で埋める操作が全て終わらないと開始されない（キューの構造より）
- よって最初の状態の黒色マスの座標をキューに入れてBFSをして、各マスに書かれているステップ数の最大が答えとなる
ソースコード
※piiの部分だけマクロ使ってます
#include<iostream> #include<vector> #include<algorithm> #include<cctype> #include<utility> #include<string> #include<cmath> #include<cstring> #include<queue> #include<map> #include<set> #define REP(i, n) for(int i = 0;i < n;i++) #define REPR(i, n) for(int i = n;i >= 0;i--) #define FOR(i, m, n) for(int i = m;i < n;i++) #define FORR(i, m, n) for(int i = m;i >= n;i--) #define SORT(v, n) sort(v, v+n); #define VSORT(v) sort(v.begin(), v.end()); #define llong long long #define pb(a) push_back(a) using namespace std; typedef pair<int, int> pii; typedef long long int ll; template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T, typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...)); } template<typename T, typename V> typename enable_if<is_class<T>::value == 0>::type fill_v(T& t, const V& v) { t = v; } template<typename T, typename V> typename enable_if<is_class<T>::value != 0>::type fill_v(T& t, const V& v) { for (auto& e : t) fill_v(e, v); } #define ARRAY_MAX 1005 const ll INF = 1e9 + 7; int dx[4] = { 1,0,0,-1 }; int dy[4] = { 0,1,-1,0 }; int h, w; char mp[ARRAY_MAX][ARRAY_MAX]; int cost[ARRAY_MAX][ARRAY_MAX]; int main() { cin >> h >> w; queue<pii> que; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { cost[i][j] = -1; } } for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { cin >> mp[i][j]; if (mp[i][j] == '#') { //黒のマスは最初にqueに入れておく que.push(pii(i, j)); cost[i][j] = 0; } } } while (!que.empty()) { int y = que.front().first; int x = que.front().second; que.pop(); for (int i = 0; i < 4; i++) { int ny = y + dy[i]; int nx = x + dx[i]; if (0 <= nx && nx < w && 0 <= ny && ny < h && mp[ny][nx] == '.' && cost[ny][nx] == -1) { que.push(pii(ny, nx)); cost[ny][nx] = cost[y][x] + 1; } } } int maxi = 0; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { maxi = max(maxi, cost[i][j]); } } cout << maxi << endl; return 0; }
動的計画法精進
yukicoder No.458 異なる素数の和
問題概要
Nをそれぞれ異なる素数の和で表すことができる場合，その中での最大の和の回数Mを出力してください。
制約
1≤N≤20000 (整数)
考察
ソースコード
※マクロは貼ってあるだけで使ってないので無視してください
#include<iostream> #include<vector> #include<algorithm> #include<cctype> #include<utility> #include<string> #include<cmath> #include<cstring> #include<queue> #include<map> #include<set> #define REP(i, n) for(int i = 0;i < n;i++) #define REPR(i, n) for(int i = n;i >= 0;i--) #define FOR(i, m, n) for(int i = m;i < n;i++) #define FORR(i, m, n) for(int i = m;i >= n;i--) #define SORT(v, n) sort(v, v+n); #define VSORT(v) sort(v.begin(), v.end()); #define llong long long #define pb(a) push_back(a) using namespace std; typedef pair<int, int> pii; typedef long long int ll; template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T, typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...)); } template<typename T, typename V> typename enable_if<is_class<T>::value == 0>::type fill_v(T& t, const V& v) { t = v; } template<typename T, typename V> typename enable_if<is_class<T>::value != 0>::type fill_v(T& t, const V& v) { for (auto& e : t) fill_v(e, v); } #define ARRAY_MAX 200005 const ll INF = 1e9 + 7; /*nまでの素数を列挙して配列に保持*/ vector<ll> Eratosthenes(ll n) { vector<ll> arr(n); for (ll i = 0; i < n; i++) { arr[i] = 1; } arr[0] = arr[1] = 0; for (ll i = 2; i < sqrt(n); i++) { if (arr[i]) { for (ll j = 0; i * (j + 2) < n; j++) { arr[i *(j + 2)] = 0; } } } return arr; } ll dp[ARRAY_MAX];//dp[i]:=iを作ることができる素数の最大の個数 int main() { ll n; cin >> n; vector<ll> num = Eratosthenes(n + 3); for (int i = 0; i < ARRAY_MAX; i++) { dp[i] = -1LL; } dp[0] = 0LL; for (int i = 2; i <= n; i++) { if (num[i] == 0) { //素数ではない場合 continue; } ll tmp = i;//今見ている素数 //素数の場合 for (int j = n; j >= 0; j--) { if (j - tmp >= 0 && dp[j - tmp] != -1LL) { dp[j] = max(dp[j], dp[j - tmp] + 1LL); } } } if (dp[n] == 0) { cout << "-1" << endl; } else { cout << dp[n] << endl; } return 0; }
いもす法をバグらせるのをやめなさ～い！！
AOJ 2600 Koto Distance
問題概要
南北にHメートル、東西にWメートルの長方形の領域内にN個のWifi の親機を設置する。入力で親機の座標及びその親機のカバーできるKoto範囲
が与えられるので、設置した親機によってこの長方形の領域が全てカバーできるか判定する。なお、Koto距離は任意の2地点
、
に対して
によって定義される。
制約
同一座標に親機は複数存在しない
考察
- 配列で持てないので工夫が必要になる。
- 親機の座標
が与えられた時に、
までの範囲内では親機はy方向を全てカバーでき、同様に
までの範囲内では親機はx方向を全てカバーできることが分かる。
- カバーできる範囲を塗りつぶしたいけど配列に持てない・・・・でも塗りつぶし系はいもす法が使える・・・・
- x方向とy方向に分けて見れば配列に持つことができるのでは？？これならいもす法が使えそう・・・・
- では、判定は？？？・・・・・・行か列のどちらかが全て覆われていれば全部覆われているとみなせる！！
- よって行と列で別々にいもす法で塗りつぶしてどちらか一方が全て覆われていればYes、そうでないならNoを出力すればよい。
- なお、配列の添え字周りでバグらせてしまったので反省（ア）
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<utility> #include<string> #include<cmath> #include<cstring> #include<queue> #include<map> #include<climits> #include<set> using namespace std; typedef pair<int, int> pii; typedef long long int ll; typedef pair<ll, ll> pll; int dx[4] = { 1,0,0,-1 }; int dy[4] = { 0,1,-1,0 }; #define MOD 1000000007 #define ARRAY_MAX 100005 const int INF = 1e9 + 7; int imos[ARRAY_MAX];//y方向 int imos2[ARRAY_MAX];//x方向 int main() { ios::sync_with_stdio(false); cin.tie(0); int n, w, h; cin >> n >> w >> h; for (int i = 0; i < n; i++) { int x, y, z; cin >> x >> y >> z; imos[max(y - z, 0)]++; imos[min(y + z, h + 1)]--; imos2[max(0, x - z)]++; imos2[min(x + z, w + 1)]--; } for (int i = 0; i <= h; i++) { imos[i + 1] += imos[i]; } for (int i = 0; i <= h; i++) { imos2[i + 1] += imos2[i]; } bool flag = true; bool flag2 = true; for (int i = 0; i < h; i++) { //縦方向 if (imos[i] <= 0) { flag = false; break; } } for (int i = 0; i < w; i++) { //横方向 if (imos2[i] <= 0) { flag2 = false; break; } } if (flag || flag2) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0; }
にぶたんの練習
Codeforces Round521 div3 D Cutting Out
問題概要
int型整数の配列sが与えられる。この配列sの中からk個の整数を選んだ配列tを配列sから取り除く。この取り除く回数が最大となる時の整数配列tを求める。なお、取り除く配列tの要素は毎回同じとし、複数答えがある場合はどれを出力してもいいものとする。
制約
考察
15 2
1 2 1 1 1 2 1 1 2 1 2 1 1 1 1
上記のサンプルを見た時に[1,2]の組み合わせで取ると4回取れますが、[1,1]でとる場合のほうが5回取れるのでこちらの方が最適となります。
このことから一番数の少ない数字に合わせることが最適解につながらないというこどが分かります。そこで、取り除く配列tを求めるために、何回取り除けるのかを求める必要があります。h回とり除けない場合は(h+1)回とり除くことはできません。また、h回とり除ける場合は(h-1)回取り除くこともできます。このことから、取り除くことができる回数には単調性があることが分かります。よって二分探索が使えることが分かります。
そこで、コードでは二分探索で取り除くことができる回数okを求めます。すると、配列s内の各数字について、１回の取り除く操作で取り除ける回数は
回になるので、配列tに
回 数字
を入れます。さて、この操作を行うと配列tに k 個以上の数字が入ることになります。配列 t に入る数字がk個よりも大きい場合は、解が複数存在する場合があることを示しています。しかし、問題文にあるように、解が複数存在する場合はどれを出力してもいいため、配列tの初めの k個を出力すればいいということになります。
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<utility> #include<string> #include<cmath> #include<cstring> #include<queue> #include<map> #include<climits> #include<queue> using namespace std; #define INF 1000000000007 #define MOD 1000000007 #define ARRAY_MAX 200005 int n,k; vector<int> a; int cnt[ARRAY_MAX]; bool check(int middle){ int sum = 0; for(int i = 0;i < ARRAY_MAX;i++){ sum += cnt[i]/middle; } if(sum >= k){ return true; }else{ return false; } } int solve(){ int ok = 1,ng = n; while(abs(ng-ok) > 1){ int middle = (ok+ng)/2; if(check(middle)){ ok = middle; }else{ ng = middle; } } return ok; } int main(){ cin >> n >> k; for(int i = 0;i < n;i++){ int tmp; cin >> tmp; a.push_back(tmp); cnt[tmp]++; } int ok = solve();//ok回取り除ける vector<int> ans; for(int i = 0;i < ARRAY_MAX;i++){ for(int times = 0;times < cnt[i]/ok;times++){ ans.push_back(i); } } for(int i = 0;i < k;i++){ cout << ans[i] << " "; } cout << endl; return 0; }
ABC079 D-Wallの精進
順列を全列挙して全探索
問題概要
数字にiからjに変更するのに必要なコストが与えられるので、
数字を全て1にするのに必要な魔力の最小量を求める
問題リンクは下記
https://beta.atcoder.jp/contests/abc079/tasks/abc079_d
解法
next_permutationを使って前処理で10!通りを全探索して通るのかと思いましたが10!×10くらいで最小コストは求められ、その後はO(1)でアクセスできるので
だいたい10^7くらいで求まりそうな見込みが立つので実装してみると通るという。(46msくらい)
想定解はワーシャルフロイドのようですが、ワーシャルフロイドが分かっていないのでワーシャルフロイドを今後は精進したいと思います。
#include<iostream> #include<vector> #include<algorithm> #include<cctype> #include<utility> #include<string> #include<cmath> #include<cstring> #include<queue> #include<map> #include<queue> #define REP(i, n) for(int i = 0;i < n;i++) #define REPR(i, n) for(int i = n;i >= 0;i--) #define FOR(i, m, n) for(int i = m;i < n;i++) #define FORR(i, m, n) for(int i = m;i >= n;i--) #define SORT(v, n) sort(v, v+n); #define VSORT(v) sort(v.begin(), v.end()); #define llong long long #define pb(a) push_back(a) #define INF 1000000007 using namespace std; typedef pair<int, int> P; typedef pair<llong, llong> LP; typedef pair<int, P> PP; typedef pair<llong, LP> LPP; typedef long long int ll; ll dx[4] = {1,0,0,-1}; ll dy[4] = {0,1,-1,0}; #define ARRAY_MAX 205 int mp[ARRAY_MAX][ARRAY_MAX]; int magic[ARRAY_MAX][ARRAY_MAX]; int h,w; int main(){ cin >> h >> w; REP(i,10){ REP(j,10){ cin >> mp[i][j]; } } REP(i,h){ REP(j,w){ cin >> magic[i][j]; } } vector<int> mini(10,INF);//iから1にするのに必要な最小コスト vector<int> num(10);//最小値 mini[1] = 0; REP(i,10){ num[i] = i; } do{ int power = 0; if(num[0] == 1){ //1はとばす continue; } REP(i,9){ power += mp[num[i]][num[i+1]];//順列に従って変更していく if(num[i+1] == 1){ //1にたどり着いたら終了 break; } } mini[num[0]] = min(mini[num[0]],power);//最小値の更新 }while(next_permutation(num.begin(),num.end())); int ans = 0;//全て1に変更するのに必要な魔力 REP(i,h){ REP(j,w){ if(magic[i][j] == -1){ continue; } ans += mini[magic[i][j]]; } } cout << ans << endl; return 0; }
ブログ開設しました
こんにちは。プニプニです。この度ブログを開設しました。今後競プロなど精進に関するものを投稿していきたいと思います。
