SRM624 div1easy BuildingHeights
考えたこと
題意がよくわからなかったのでサンプルを試してみると、同じ高さのビルをi個(1<=i<=N)つくるために必要なコストをA[i]としたとき、A[1]^A[2]^…A[N]を出力すればよさそう。離れた階層のビルの高さを同じにする利点はないのでソートして考える。
dp[i][j] = (i+2個同じ高さのビルをつくる際にheights[j]の高さに合わせるときのコスト)をO(N^2)で計算できれば解けそう。i=0のときは階差数列を求めれば良い。DPテーブルを書いていると累積和っぽくやればできそうなことに気づく。i=0以外のときはdp[i][j] = dp[i-1][j] + (heights[j+i+1] - heights[j])でdpの更新を行えるのでO(N^2)でできる。
あとは各iについて最も小さいdp[i][j]の値を求めそのxorを出力すれば良い。
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typedef vector<VL> VVL; typedef pair<int, int> PII; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define IN(a, b, x) (a<=x&&x<b) #define MP make_pair #define PB push_back const int INF = (1LL<<30); const ll LLINF = (1LL<<60); const double PI = 3.14159265359; const double EPS = 1e-12; const int MOD = 1000000007; //#define int ll template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; int dp[4010][4010]; class BuildingHeights { public: int minimum(vector <int> heights) { int n = heights.size(); sort(ALL(heights)); int ret = 0; REP(i, n-1) { int mi = INF; REP(j, n-i-1) { dp[i][j] = heights[j+i+1] - heights[j]; if(i > 0) dp[i][j] += dp[i-1][j+1]; chmin(mi, dp[i][j]); } ret ^= mi; } return ret; } };
SRM623 div1easy UniformBoard
考えたこと
PをAに置き換えるためにはPをどこか別の空マスに移し、Aをどこかから持ってくるため2手かかる。.をAに置き換えるためには1手かかる。
ある長方形の範囲を条件を満たす範囲とできるかを考える。Aが2個、Pが1個、.が1個ある範囲を全てAに置き換えるためには、
* Aが他の部分に2個以上存在する
* Pが1個→2手 .が1個→1手 より 3手 <= K
の条件を満たす必要がある。したがって、長方形の範囲内のP、A、.の数を高速に求める必要がありこれは累積和で前計算しておくことでO(1)でできる。長方形はO(N^4)個存在するため合計O(N^4)で解くことが出来る。
考察はすぐにできたが実装でバグらせて時間を掛けて反省。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } int cnt[25][25][3]; class UniformBoard { public: int getBoard(vector <string> board, int K) { int n = board.size(); memset(cnt, 0, sizeof(cnt)); FOR(i, 1, n+1) FOR(j, 1, n+1) { cnt[i][j][0] = cnt[i-1][j][0] + cnt[i][j-1][0] - cnt[i-1][j-1][0]; if(board[i-1][j-1] == 'A') cnt[i][j][0]++; } FOR(i, 1, n+1) FOR(j, 1, n+1) { cnt[i][j][1] = cnt[i-1][j][1] + cnt[i][j-1][1] - cnt[i-1][j-1][1]; if(board[i-1][j-1] == 'P') cnt[i][j][1]++; } FOR(i, 1, n+1) FOR(j, 1, n+1) { cnt[i][j][2] = cnt[i-1][j][2] + cnt[i][j-1][2] - cnt[i-1][j-1][2]; if(board[i-1][j-1] == '.') cnt[i][j][2]++; } int all = cnt[n][n][0]; if(cnt[n][n][0] == 0) return 0; int ret = 0; FOR(sx, 1, n+1) FOR(sy, 1, n+1) FOR(gx, sx, n+1) FOR(gy, sy, n+1) { int apple = cnt[gy][gx][0] - cnt[sy-1][gx][0] - cnt[gy][sx-1][0] + cnt[sy-1][sx-1][0]; int pear = cnt[gy][gx][1] - cnt[sy-1][gx][1] - cnt[gy][sx-1][1] + cnt[sy-1][sx-1][1]; int emp = cnt[gy][gx][2] - cnt[sy-1][gx][2] - cnt[gy][sx-1][2] + cnt[sy-1][sx-1][2]; int menseki = (gy-sy+1)*(gx-sx+1); // 交換不可能 if(cnt[n][n][2] == 0) { if(menseki == apple) chmax(ret, apple); continue; } if(all - apple < menseki - apple) continue; if(pear*2 + emp <= K) chmax(ret, menseki); } return ret; } };
SRM621 div1 easy RadioRange
考えたこと
中心が(0, 0)で半径がrの円と中心が(X, Y)で半径がRの円が共有する部分を持つ条件について考える。半径rが （2円が外接する半径r_1）<= r < （2円が内接する半径r_2）の条件を満たすときと言い換えられる。
r_1 = max(0, sqrt(XX+YY)) (円の中に(0, 0)が存在する場合0)
r_2 = min(Z, sqrt(XX+YY))
とできるのでそれぞれの円について[r_1, r_2]を求めこの範囲の和集合を取ることで共有部分を持つ区間を求めることができる。
和集合を取る部分をバグらせまくったりオーバーフローさせたりいろいろ反省。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) pair<double, double> p[105]; class RadioRange { public: double RadiusProbability(vector <int> X, vector <int> Y, vector <int> R, int Z) { int n = X.size(); REP(i, n) { double l = sqrt((double)X[i]*X[i]+(double)Y[i]*Y[i]); p[i] = {max(l-R[i], 0.0), min(l+R[i], (double)Z)}; } sort(p, p+n); double sum = 0; double l = 0, r = 0; REP(i, n) { if(p[i].first >= Z) break; if(p[i].first>=r) { l = p[i].first, r = p[i].second; sum += r-l; } else if(p[i].second>=r) { sum += p[i].second - r; r = p[i].second; } } return 1-sum/Z; } };
SRM619 div1easy SplitStoneGame
考えたこと
ゲームで石の山だしgrundy数かなあと思いつつ問題文を読む。敗北条件を考えると石の数が1個以下の山しか存在しない場合か山が2個以下しかない場合になる。サンプルを読んでいると山の石の数は2個以上か1個の2パターンしか考慮しなくていいことに気づく。1個の山の数をA、2個以上の山の数をBと置く。
それぞれの手番でのA, Bの遷移がどうなってるか考えると
* Bがマイナス1 (B>=3)
* Aがマイナス1 (A>=1, B>=2)
* Bがプラス1、Aがマイナス2 (A>=2, B>=1)
の3通りになる。
AとBからwinとloseの状態を一意に決めることができ、メモ化再帰で求めることでできる。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) int dp[55][55]; int dfs(int A, int B) { if(dp[A][B] != -1) return dp[A][B]; if(A+B <= 2 || B == 0) return dp[A][B] = 0; bool res = true; if(B >= 3) res &= dfs(A, B-1); if(A >= 1 && B >= 2) res &= dfs(A-1, B); if(A >= 2 && B >= 1) res &= dfs(A-2, B+1); return dp[A][B] = !res; } class SplitStoneGame { public: string winOrLose(vector <int> number) { int a = 0, b = 0; REP(i, number.size()) { if(number[i] == 1) a++; else b++; } memset(dp, -1, sizeof(dp)); if(dfs(a, b) == 0) return "LOSE"; return "WIN"; } };
SRM618 div1 easy Family
考えたこと
サンプルのグラフを書いてみると、parent1[i]とparent2[i]が2つの異なる値で分類できれば可能であると判定できそうなことに気づく。これはparent1[i]とparent2[i]をつないだグラフが2部グラフであるかどうか判定すればできる。提出したら通った。
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define PB push_back VI g[105]; int color[105]; bool dfs(int v, int c) { color[v] = c; for(int i: g[v]) { if(color[i] == c) return false; if(color[i] == 0 && !dfs(i, -c)) return false; } return true; } class Family { public: string isFamily(vector <int> p1, vector <int> p2) { int n = p1.size(); REP(i, n) { if(p1[i] == -1) continue; g[p1[i]].PB(p2[i]); g[p2[i]].PB(p1[i]); } REP(i, n) { if(!color[i]) { if(!dfs(i, 1)) { return "Impossible"; } } } return "Possible"; } };
SRM617 div1 easy MyLongCake
概要
長さnのケーキがあり友人に配るためケーキを切っておきたい。友人には同じ長さの連続したピースのケーキを渡せるようにしたい。来る友人の人数はn以外のnの約数の人数ということしかわかっていない。この条件を満たすような最小のピースの数を出力しろ。
解法
a人来るときは{n/a, 2n/a, 3n/a, …, (a-1)*n/a}の位置を切るしかない。 約数の列挙はO(sqrt(n))でできるので解ける。
#include <bits/stdc++.h> using namespace std; class MyLongCake { public: int cut(int n) { set<int> st; for(int i=2; i*i<=n; ++i) { if(n%i==0) { for(int j=n/i; j<n; j+=n/i) st.insert(j); for(int j=i; j<n; j+=i) st.insert(j); } } return st.size()+1; } };
Tenka1 Programmer Contest C - 4/N
問題ページ C - 4/N
考えたこと
何かうまい構成方法でO(1)？と思ったがよくよく考えると全探索できる。誤差死とオーバーフローに気をつけつつ算数をすると通った。
時間かけすぎで反省。
解法
hとnを決めるとwは一意に決まるのでO(35002)の探索をする
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typedef vector<VL> VVL; typedef pair<int, int> PII; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define IN(a, b, x) (a<=x&&x<b) #define MP make_pair #define PB push_back const int INF = (1LL<<30); const ll LLINF = (1LL<<60); const double PI = 3.14159265359; const double EPS = 1e-12; const int MOD = 1000000007; #define int ll template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; signed main(void) { int n; cin >> n; FOR(i, 1, 3501) FOR(j, 1, 3501) { if(4*i*j-n*i-n*j == 0) continue; int k = n*i*j/(4*i*j-n*i-n*j); if(1 <= k && 4LL*i*j*k == n*(i*j+j*k+k*i)) { cout << i << " " << j << " " << k << endl; return 0; } } assert(false); return 0; }
