SRM416: CustomDice
ほとんど毎日考えてたけど結局わからなかったのでeditorial見た
(問題概要)
目の平均値がM以下になるようなサイコロの作り方は何通りあるか。
ただし全ての目は異なる。
(解法)
差分形式に式変形していくとDPに落とせるようだ。
これは難しいけど、汎用的に使えそうなテクニックなのでしっかりと理解したい。
#define REP(i,n) for(int i=0; i<(int)(n); i++) #include <queue> #include <set> #include <iostream> #include <sstream> using namespace std; class CustomDice { public: int countDice(int M); }; int CustomDice::countDice(int M){ const int m = 6 * M - 21; const int mod = 1000000007; if(m < 0) return 0; vector<int> dp(m + 1, 1); for(int i = 1; i <= 6; i++){ vector<int> next(m + 1); REP(j,m + 1){ next[j] = dp[j]; if(j >= i) next[j] += next[j - i]; next[j] %= mod; } dp.swap(next); } return (30ll * dp[m]) % mod; }
C++0xのラムダのインライン化
インライン化されるのか調べた。
されるっぽい(g++ 4.6.3調べ)。すばらしい。
まあ関数オブジェクト作ってるだけらしいので当たり前かもしれないけど。
int func(int x){ const auto inc = [](int x){ return x + 1; }; return inc(x); }
これが
_Z4funci: .LFB0: .cfi_startproc movl 4(%esp), %eax addl $1, %eax ret .cfi_endproc
こんな感じになる。
当然以下のような少し複雑なケースでも大丈夫。
struct apply{ template<typename F> inline int operator () (F f) const { return f(0); } }; int func(int x){ return apply()([](int x){ return x + 1; }); }
こうなる
_Z4funci: .LFB1276: .cfi_startproc movl $1, %eax ret .cfi_endproc
SRM415: CollectingPostmarks
(問題概要)
n (<=32) 個のポストカードがあり、価格(<= 30000000)と価値(<= 30000000)が与えられる。
幾つかのポストカードをすでに持っている。
持っているポストカードは同じ価格で売ることができる。
価値Kを得るにはいくら追加でお金がいるか。
(解法)
とりあえず持ってるのは全部売って、一から考えると楽。
問題形式的には典型的ナップザック問題に見えるが、価格と価値が高すぎてDPができない。
半分に分けてそれぞれ全列挙してやることでn * 2 ^ (n / 2)くらいの計算量になり解ける。
前回との難易度のギャップがやばい。
コーディングミスでめっちゃ時間かかった。
#include <algorithm> #include <cstdio> #include <cassert> #include <map> #include <climits> #define REP(i,n) for(int i=0; i<(int)(n); i++) #include <numeric> typedef long long ll; #include <queue> #include <set> #include <iostream> #include <sstream> using namespace std; class CollectingPostmarks { public: int amountOfMoney(vector <int> prices, vector <int> have, vector <int> values, int K); }; int CollectingPostmarks::amountOfMoney(vector <int> prices, vector <int> have, vector <int> values, int K){ const ll sum = accumulate(values.begin(), values.end(), 0ll); if(sum < K) return -1; const int n = prices.size(); int pp = 0; REP(i,have.size()) pp += prices[have[i]]; const int nn = (n + 1) / 2; const int mm = n - nn; map<int, int> memo1; REP(i, 1<<nn){ int p = 0; int v = 0; REP(j,nn) if(i & (1 << j)){ p += prices[j]; v += values[j]; } if(memo1.count(v)){ memo1[v] = min(memo1[v], p); }else{ memo1[v] = p; } } map<int, int> memo2; REP(i, 1<<mm){ int p = 0; int v = 0; REP(j,mm) if(i & (1 << j)){ p += prices[nn + j]; v += values[nn + j]; } if(memo2.count(v)){ memo2[v] = min(memo2[v], p); }else{ memo2[v] = p; } } vector<pair<int, int> > m1(memo1.begin(), memo1.end()); vector<pair<int, int> > m2(memo2.begin(), memo2.end()); sort(m1.begin(), m1.end()); sort(m2.begin(), m2.end()); for(int i = m1.size() - 1; i > 0; i--) m1[i - 1].second = min(m1[i - 1].second, m1[i].second); for(int i = m2.size() - 1; i > 0; i--) m2[i - 1].second = min(m2[i - 1].second, m2[i].second); int ans = INT_MAX; REP(i,m1.size()){ const int p = m1[i].second; const int v = m1[i].first; if(v >= K){ ans = min(ans, p); }else{ const int idx = lower_bound(m2.begin(), m2.end(), make_pair(K - v, 0)) - m2.begin(); if(idx != (int)m2.size()){ ans = min(ans, p + m2[idx].second); } } } return max(0, ans - pp); }
SRM414: StringInterspersal
(問題概要)
文字列が幾つか与えられる。
すべての文字列が空になるまでどれかの文字列の先頭文字をくっつける操作を繰り返す。
辞書順最小の文字列を作りなさい。
(解法)
貪欲に最小なのをとっていく。
文字列がなくなるケースはあまり嬉しくないのを考慮。
最後にZをいっぱいつけておけば実装が簡単。
多分開いてから解くのに５分かかってない。
#define REP(i,n) for(int i=0; i<(int)(n); i++) #include <queue> #include <set> #include <iostream> #include <sstream> using namespace std; class StringInterspersal { public: string minimum(vector <string> W); }; string StringInterspersal::minimum(vector <string> W){ const string suffix(51, 'Z'); REP(i,W.size()) W[i] = W[i] + suffix; priority_queue<string, vector<string>, greater<string> > q(W.begin(), W.end()); stringstream ss; while(q.size()){ const string s = q.top(); q.pop(); ss << s[0]; if(s.size() > 1 + suffix.size()) q.push(s.substr(1)); } return ss.str(); }
SRM413: InfiniteSequence2
(問題概要)
A_i = 1 for all i <= 0;
A_i = A_[i/p]-x + A_[i/q]-y
A_nを求めよ。(n < 10^13)
(解法)
メモ化再帰。
ただし全部をmap等でメモるとMLEでセグるので、部分的にメモる。
なんかチーター本で見たような気もする。
typedef long long ll; #include <queue> #include <set> #include <iostream> #include <sstream> using namespace std; class InfiniteSequence2 { public: long long calc(long long n, int p, int q, int x, int y); }; ll memo[1000000]; int p; int q; int x; int y; ll solve(ll n){ if(n <= 0) return 1; if(n < 1000000 && memo[n] != -1) return memo[n]; ll ret = solve(n / p - x) + solve(n / q - y); if(n < 1000000) memo[n] = ret; return ret; } long long InfiniteSequence2::calc(long long n, int p, int q, int x, int y){ ::p = p; ::q = q; ::x = x; ::y = y; memset(memo, -1, sizeof(memo)); return solve(n); }
幾何での手抜き手法
※この記事はCompetitive Programming Advent Calendar Div2012 の19日目の記事です。
競技プログラミングにおいて、時間内に正しい答えを出せる限り手を抜く(簡単なプログラムを書くの意)のが定石。
ということでとある問題を題材に探索っぽくして幾何で手を抜く方法でも紹介してみます。
問題
AOJ1093を題材にします。
詳しくは本家で読んでもらうとして概要はこんな感じ↓
N (≦ 100)個の点 p[i] = (x[i], y[i]) と速度 v[i] (0 ≦ i ≦ N - 1)が与えられます。
適当な座標を選び、(x[i], y[i]) に速度 v[i] で移動する時間の0 ≦ i ≦ N - 1での最大値を最小化する。
その時の最小値を出力しなさい。
解法
数学的な解法は私には思い浮かばないので、探索していくことにしましょう*1。
探索方法
点を移動させていって、解っぽいところを探す探索を考える。
今(x, y)にいるとして、よりよい点を探すにはどうすれば良いか。
自然に、一番移動に時間がかかる点の方に少しすすめば良い気がする。
実はこの問題はこの解法で良く、擬似コードにすると以下のようになる。
実際のコード見たい方はこちら。
r := (0.5 〜 (1.0 - ε) の間の適当な数) (x, y) <- 適当な点 d <- ある程度大きい数 while 収束するまで (x, y) <- ((x, y) を 一番移動に時間がかかる点 p[i] の方向に d だけ近づけた点) d <- d * r print ((x, y) から一番移動に時間がかかる点 p[i] に移動するのにかかる時間)
これで通ってしまう。
幾何系の問題の解法には見えないすっきりさで素晴らしい(当社比)。
考察
これで終わりだと面白く無いのでほんの少しだけ考察。
おそらくこの手法は山登り法の一種だと思われる。
一般には局所解に陥る場合があり、厳密な解を出すような問題には不向きだが、今回のような局所解となるような点が他にない問題では使える*2。
サンプルケースだと以下のような評価関数(= (x, y) から一番移動に時間がかかる点 p[i] に移動するのにかかる時間)になっていて、局所解が他に無いことや、山登り(図だと谷下り？？)法で綺麗に解けそうな様子が見える(見難くてごめんなさい)。
今回は、評価関数として問題に書かれているものをそのまま利用したが、本当の解と評価関数の極大/極小の位置さえ一致していれば良いので評価関数を工夫することで色々な問題に応用できるはず。
まとめ
探索っぽくして幾何で手を抜く方法を紹介しました。そんなに汎用的に使える手法でもないですが、何度かこの種の解法を書いた記憶はあるので、たまには使える手法のはずです。(最近だとUTPC2012 D-地図が２枚)
一見難しそうな幾何問題に出会っても、このような簡単な探索で解けないか考えてみると良いかも知れません。
明日はDarseinさんとnatrium11321さんの番です。皆様楽しみに待ちましょう！
