2018-08-02

AtCoderの Typical DP Contestを解いてみた (F 準急)

競技プログラミング

F 準急
- 問題の概要
(自分が思いついた)解法
(調べてわかった)解法
実装上の注意
ソース

今回もTypical DP Contest のアウトプットに関する記事です.

今回解いた問題はF 準急です

前回までの記事は以下の通りです.

F 準急

今回は「F 準急」という問題を解きました.

(かなり難しくなってきたように感じ、自分では解くことが困難になってきました.

修行が必要ですね...)

問題の概要

ある路線には駅 $1 \sim N$ 駅までの $N$ 個の駅がある.

A君は、下の制約のもと、この路線に準急を走らせることにした.

制約

に止まり、の部分集合に止まり、駅に止まる.
- 連続する $K$ 個以上の駅に止まることはない.

(自分が思いついた)解法

まずはじめに、計算量を考慮せずに、自分が思いつける範囲でDPに落としこむことを考えました.

少し考えて思いついたのが、

$$ dp[i][j] : i駅までで現在j連続で止まっているときの場合の数 $$

です. (明らかにこれだと間に合いませんが、一応実装したのでアウトプットします.)

このとき、漸化式は

$$ \begin{cases} dp[i + 1][j + 1] += dp[i][j] & (i + 1駅目で止まる) \\ dp[i + 1][0] += dp[i][k] & (i + 1駅目は通過する) \end{cases} $$

となります.

通過する場合は、連続して停車した駅の数が0にリセットされます.

最終出力は、

$$ ans += dp[N][k] \, (k = 0, \cdots K - 1) $$

です.

このDPだと、状態数が $N \times K$ ですので、もう少し状態を減らすことが考えます.

(現在いる駅の数 $0 \sim K - 1$ 回連続で止まれる、遷移数が $2$ なので、計算量は $O(NK)$ となって、到底間に合いません.

(調べてわかった)解法

DPでは状態数を減らすことを考えるのが定石らしいので、状態数を減らすことを考えます.

先ほどは何駅連続で止まったかと言う状態を保持していましたが、今回は $i$ 駅を通過するか停車するかの2つだけを考えることにします.

したがって、 $$ \begin{cases} dp[i][0] : 駅iで止まる \\ dp[i][1] : 駅iを通過する \end{cases} $$

となります.

漸化式は、 $$ dp[i][j] = dp[i - 1][0] + dp[i - 1][1] $$ です.

この式が表しているのは、 $i$ 駅で通過または停車するときの場合の数は、 $i-1$ 駅通過または停車したときの場合の数を足し合わせたものです.

しかし、 $i$ 駅で停車したときはもう少し考える必要があります.

それは、 $i$ 駅で $K-1$ 連続停車した回数は、 $i - K$ 駅を通過したときに等しいことになります. (その区間だけ各駅停車になるので場合の数は変わらない.)

重複した分を引く必要があるので、 $$ dp[i][0] -= dp[i - K][1] $$ とする必要があります.

これで、状態数は $N \times 2$ なので、計算量は $O(N)$ で、間に合います.

その他にも状態数を減らすテクニックとして累積和を用いる方法があるそうです.

この記事が非常にわかりやすかったので、リンクをあげておきます.

(内部を見る限り上で説明した手法とほぼ同じことをやっていると思います. (多分))

shindannin.hatenadiary.com

実装上の注意

$mod$ の扱い方には少し注意が必要です.

$dp[i][0]$ から $dp[i - K][1]$ を引くとき、ふになってしまう可能性があり、負の値を $mod$ で割った余りを更新する値としては不具合が生じます.

したがって、 $dp[i][0] = (dp[i][0] - do[i - K][0] + mod) % mod$ と、 $mod$ を足した後で割ってあげます.

ソース

使用言語はC++です.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
// ascending order
#define asort(array, N) sort(array, array + N)
// descending order
#define asort_r(array, N) sort(array, array + N, greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(n, init, end) for(int n = init; n < end; n++)
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

int main(){
cin.tie(0);
ios::sync_with_stdio(false);

int N, K;
cin >> N >> K;
int mod = 1e9 + 7;

int dp[N + 1][2];
dp[0][0] = dp[0][1] = 1;

rep(i, 1, N + 1) {
if(i == 1) {
dp[i][0] = 1;
dp[i][1] = 0;
continue;
}

rep(j, 0, 2) dp[i][j] = (dp[i - 1][0] + dp[i - 1][1]) % mod;

if(i - K >= 0) dp[i][0] = (dp[i][0] - dp[i - K][1] + mod) % mod;
}
cout << dp[N][0] << endl;

}

2018-08-01

AtCoderの Typical DP Contestを解いてみた (E 数)

競技プログラミング

E 数
- 問題の概要
解法
- 寄り道 (桁DPの勉強)
解法 (本題に戻る)
ソース

今回もTypical DP Contestのアウトプットに関する記事です.

今回解いた問題はE 数です

前回までの記事は以下の通りです.

E 数

今回は「E 数」という問題を解きました.

問題の概要

$N$ 以下の正整数であって、10進数表記したときの各桁の数の和が $D$ の倍数であるものの個数を $mod 1,000,000,007$ で求めよ.

制約

$1 \leq N \leq 10^{10000}$
$1 \leq D \leq 100$

解法

愚直にループを回すと、 $N$ が $10^{10000}$ のケースが考えられるので到底間に合いません.

したがってDPで解くことを考えます.

試行錯誤して漸化式をたてようと試みたのですが、うまくたてられませんでした.

なので、（他の人が解いたこの問題の解法は避けるように）ググってみた結果、桁DPというものが使えそうなので、そちらの勉強から始めました.

(桁DPはよく使う手法らしいのですが恥ずかしながら初めて聞きました... 勉強不足ですね...)

寄り道 (桁DPの勉強)

私は、こちらの記事を参考にさせていただき、一通り実装することで、桁DPの考え方を学びました.

pekempey.hatenablog.com

非常にわかりやすくまとまっているので、桁DPってなんぞやって方は、本記事の続きを見る前に一読することをお勧めします.

(桁DPについての解説などは本記事では省きます.)

解法 (本題に戻る)

(ほとんど上記の参考記事に記載されているプログラムの書き方で、アルゴリズムを含め自分で考えたのはほんの少しの部分です.)

桁DPの紹介記事にあった通り、 $$ dp[i][j] : \begin{cases} i : 上からi桁目まで参照している \\ j : N未満であることが確定しているかどうか\\ (j = 1 で確定、j = 0で確定していない) \end{cases} $$

というところから考え始めます.

本問題では各桁の和が $D$ である数の総数を求めなければいけないので、追加要素として、 $D$ で割った余りという状態を持たせます.

つまり、 $$ dp[i][j][k] : \begin{cases} i : 上からi桁目まで参照している \\ j : N未満であることが確定しているかどうか\\ (j = 1 で確定、j = 0で確定していない)\\ k : 各桁の和をDで割った余り \end{cases} $$

とします.

漸化式は、まず桁DPの基本のところから考えると、 $dp[i][j]$ に対して、 $$ dp[i + 1][j \,|| \, d < lim] += dp[i][j] $$

となります.

ただし、 $lim$ という数字はそれまでに $N$ を超えていたら次の桁の数に制限が加わるので、その次の桁に使える数の上限を表しています.

例えば、 $N = 123$ に対して、現在 $12?$ とみていたら、?には0~9の全ての数を使えません.

$N$ を超えていはいけないので、?には0 ~ 3のいずれかしか入れることができないからです.

したがって、この例で言うと $lim = 3$ です.

次に本問題のために拡張したDPの漸化式をたてます. $$ dp[i + 1][j \,||\, d \,< \, lim][(k + d) \, \% \, D] += dp[i][j][k] $$

3つめの要素では1桁前の総和に使用可能な数を足し合わせ、それを $D$ で割った余りで分類しています.

最終出力は、 $dp[N][j][0] - 1\, (j = 0, 1)$ です.

（なぜなら、今回は各桁の総和を $D$ で割った余りが0となる正整数の個数を求められているからです.)

ちなみに最後にマイナス1をしているのは $0$ も $D$ の倍数であるとして数え上げているためです.

ソース

使用言語はC++です.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int D;
    string N;
    cin >> D >> N;
    ll n = N.length();
    ll mod = 1e9 + 7;

    int dp[n + 1][2][D];
    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;
    
    rep(i, 0, n) rep(j, 0, 2) rep(k, 0, D) {
        int lim = j ? 9 : N[i] - '0';
        rep(d, 0, lim + 1) (dp[i + 1][j || d < lim][(k + d) % D] += dp[i][j][k]) %= mod;
    }

    int ans = 0;
    rep(j, 0, 2) (ans += dp[n][j][0]) %= mod;
    cout << (ans - 1) << endl;
}

2018-07-31

AtCoderの Typical DP Contestを解いてみた (D サイコロ)

競技プログラミング

D サイコロ
- 問題の概要
解法
実装上の注意
ソース

今回もTypical DP Contestのアウトプットに関する記事です.

今回解いた問題はD サイコロです

前回までの記事は以下の通りです.

D サイコロ

今回は「D サイコロ」という問題を解きました.

問題の概要

サイコロを $N$ 回振ったとき、出た目の積が $D$ の倍数となる確率を求めよ.

解法

今回はサイコロを一回振ったときに、 $1 \sim 6$ の値しか取らないことに着目します.

(ここに気づけたら本問題の9割は解けたようなもんだと思っています.)

$1 \sim 6$ の値をそれぞれ素因数分解すると、素因数としては $2, 3, 5$ の3つしか出現しません.

したがって、これらの値の積で表される値の素因数も $2, 3, 5$ のみです.

要するに、サイコロを $N$ 回振ったときの出目の積を $P_N$ とすると $$ P_N = 2^{a} * 3^{b} * 5^{c} $$ で表すことができます.

逆に、7以上の素因数を含む値はサイコロの出目の積で表すことができません.

以上のことから、今回はサイコロを $n$ 回振ったときに素因数 $2, 3, 5$ の個数 $a, b, c$ で場合分けをして漸化式を作っていきます.

$$ \begin{cases} dp[n + 1][a][b][c] += \frac{dp[n][a][b][c]}{6} & (n + 1回目に1が出たとき) \\ dp[n + 1][a + 1][b][c] += \frac{dp[n][a][b][c]}{6} & (n + 1回目に2が出たとき) \\ dp[n + 1][a][b + 1][c] += \frac{dp[n][a][b][c]}{6} & (n + 1回目に3が出たとき) \\ dp[n + 1][a + 2][b][c] += \frac{dp[n][a][b][c]}{6} & (n + 1回目に4が出たとき) \\ dp[n + 1][a][b][c + 1] += \frac{dp[n][a][b][c]}{6} & (n + 1回目に5が出たとき) \\ dp[n + 1][a + 1][b + 1][c] += \frac{dp[n][a][b][c]}{6} & (n + 1回目に6が出たとき) \\ \end{cases} $$ 例えば、 $n + 1$ 回目に $2$ が出たときは素因数 $2$ の個数が $1$ 個増えるので、 $dp[n + 1][a + 1][b][c]$ となります.

また、初期値は、 $dp[0][0][0][0] = 1$ 、最終出力は、 $dp[N][A][B][C]$ です.

実装上の注意

サイコロの出目が4のとき素因数2の個数が2つ増えます.

これは $dp[n + 1][a + 2][b][c]$ に相当しますが、 $a = A - 1, A$ のときに $a + 2$ の部分が配列の範囲を超えてしまうので、 $$ dp[n + 1][min(a + 2, A)][b][c] $$ と上限を超えないように制御しています.

他の出目のときも同じようにしています.

ソース

使用言語はC++です.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N;
    ll D;
    cin >> N >> D;

    int A, B, C;
    A = B = C = 0;
    while(D % 2 == 0) {A++; D /= 2;}
    while(D % 3 == 0) {B++; D /= 3;}
    while(D % 5 == 0) {C++; D /= 5;}

    if(D != 1) {cout << 0 << endl; return 0;}

    long double p = 1.0 / 6.0;
    long double dp[N + 1][A + 1][B + 1][C + 1];
    memset(dp, 0, sizeof(long double) * (N + 1) * (A + 1) * (B + 1) * (C + 1));
    dp[0][0][0][0] = 1;
    rep(n, 0, N) {
        rep(a, 0, A + 1) {
            rep(b, 0, B + 1) {
                rep(c, 0, C + 1) {
                    dp[n + 1][a][b][c] += p * dp[n][a][b][c];
                    dp[n + 1][min(a + 1, A)][b][c] += p * dp[n][a][b][c];
                    dp[n + 1][a][min(b + 1, B)][c] += p * dp[n][a][b][c];
                    dp[n + 1][min(a + 2, A)][b][c] += p * dp[n][a][b][c];
                    dp[n + 1][a][b][min(c + 1, C)] += p * dp[n][a][b][c];
                    dp[n + 1][min(a + 1, A)][min(b + 1, B)][c] += p * dp[n][a][b][c];
                }
            }
        }
    }

    cout << dp[N][A][B][C] << endl;

}

2018-07-27

AtCoderの Typical DP Contestを解いてみた (C トーナメント)

競技プログラミング

C トーナメント
- 問題の概要
解法
ソース

今回もTypical DP Contestのアウトプットに関する記事です.

今回解いた問題はC トーナメントです

前回までの記事は以下の通りです.

C トーナメント

今回は「C トーナメント」という問題を解きました.

問題の概要

(問題自体はAtCoderで確認してください.)

$2^{K}$ 人が参加するトーナメントがあり、以下の形式で試合を行う.

1回目は1と2, 3と4, ... が試合を行う.
2回目は (1と2の勝者) と (3と4の勝者), ... が試合を行う.
以下同様にK回行う.

K回後に優勝者が決定する. $i$ が優勝する確率を求めよ.

ただし、各人には強さが定義されていて $i$ の強さは $R_{i}$ である.

$i$ と $j$ が戦ったときに、 $i$ が勝つ確率は

$$ F(i, j) = \frac{1}{(1 + \frac{10^{R_j - R_i}}{400})} $$

と定義される.

解法

$dp[i][j]$ : $i$ が $j$ 試合連続で勝ち続ける確率

最終的な出力は $dp[i][K]$ です. ( $i = 0 \cdots 2^{K} - 1$ )

(全プレイヤーの優勝 (K連勝) する確率を出力することを求められているので)

DPの漸化式は以下の通りです.

$$ dp[i][j] = dp[i][j - 1] * \sum_{k \in S} F(i, k) $$

ただし、 $j$ 試合目に $i$ と戦うことができる相手の集合を $S$ とします.

例えば、1試合目に1と戦うことができる相手の集合は $S = \{2\}$ です.

また、2試合目に1と戦うことができる相手の集合は $S = \{3, 4\}$ です.

さらに、 $F(i, k)$ は上で定義された $i$ が $k$ に勝つ確率です.

ここまでは、普通のDPと同じです.

しかし、今回はトーナメントなので、戦う相手に制限があります. (誰とでも戦えるわけではありません.)

要は集合 $S$ をどうするかが少し工夫がいるところです.

今回はビット演算を用いた方法で $i$ が $j$ 試合目に戦う相手であるかどうかを判別する方法を紹介します.

(ビット演算の使い方についてはQiitaのページが非常に参考になります.

(DPの記事も書いてくださった人っぽくてほんとお世話になりっぱなしです...)) qiita.com

具体例として、参加者が8人とします.

各参加者に割り当てられた番号を2進数に変換します. (便宜上0番目から数えることにします)

$0 : 000\\ 1 : 001\\ 2 : 010\\ 3 : 011\\ 4 : 100\\ 5 : 101\\ 6 : 110\\ 7 : 111$

1試合目は(0, 1), (2, 3), (4, 5), (6, 7)が戦います.

これらは1bit目が異なり2bit目以降は一致しています.

したがって、右に1bitシフトすると1試合目に戦うプレイヤー同士のbit列は一致します. (例えば、2と3はそれぞれ右に1bitシフトすると001となる)

2試合目についても考えてみます.

2試合目は(0, 2 or 3), (1, 2 or 3), (2, 0, or 1), (3, 0 or 1), (4, 6 or 7), (5, 6 or 7), (6, 4 or 5), (7, 4 or 5)が戦います.

これらは2bit目が異なり3bit目以降が一致します. (1bit目は無視)

例えば、(0, 2 or 3)をみてみると、

$000\\ 010 \, or \, 011$

です.

0と2, 0と3のどちらをみても2bit目が異なり3bit目以降が一致しています.

したがって、右に2bitシフトすると2試合目に戦うプレイヤー同士のbit列は一致します.

ただし、一個前の試合で戦った相手とは戦うことができないので、右に1bitシフトしたときに一致したプレイヤー同士は無視します. (0と1も2bit右シフトすると000で一致するが、1試合目で戦っているので無視する)

一般化すると、

$i\mbox{と}k\mbox{が}j\mbox{試合目で戦う} = \\ \{ i\mbox{と}k\mbox{を}j\,bit\mbox{右シフトしたものが一致する}\} \cap \{i\mbox{と}k\mbox{を} \,j-1 \, bit\mbox{右シフトしたものが一致しない}\}$

で表すことができます. (多分)

C++でこれを実装すると

(i >> j) == (k >> j)

が $j$ bitシフトしたときに一致しているかを判別していて、

(i >> (j - 1) != (k >> (j - 1))

が一つ前の試合で戦った相手は無視していることに相当します.

これらをまとめると

if((i >> j) == (k >> j) && (i >> (j - 1)) != (k >> (j - 1))) 勝率の計算

となります.

ソース

使用言語はC++です.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

double returnProbability(int rp, int rq) {
    return (double)(1.0 / (1.0 + pow(10.0, (rq - rp) / 400.0)));
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int K;
    cin >> K;
    int p = pow(2, K);
    int R[p];
    rep(i, 0, p) cin >> R[i];

    double dp[p + 1][K + 1];
    rep(i, 0, p + 1) rep(j, 0, K + 1) dp[i][j] = 0;
    rep(i, 0, p + 1) dp[i][0] = 1;

    rep(j, 1, K + 1) {
        rep(i, 0, p + 1) {
            double tmp = 0;
            rep(k, 0, p) {
                if((i >> j) == (k >> j) && (i >> (j - 1)) != (k >> (j - 1))) tmp += returnProbability(R[i], R[k]) * dp[k][j - 1];
            }
            dp[i][j] = dp[i][j - 1] * tmp;
        }
    }

    rep(i, 0, p) cout << dp[i][K] << endl;

}

2018-07-26

AtCoderの Typical DP Contestを解いてみた (B ゲーム)

競技プログラミング

B ゲーム
- 問題の概要
解法
ソース

今回もTypical DP Contestを解いたのでアウトプットします.

今回解いた問題はB ゲームです

前回までの記事は以下の通りです.

A コンテスト

B ゲーム

今回は「B ゲーム」という問題を解きました.

問題の概要

(問題自体はAtCoderで確認してください.) 二人のプレイヤーがゲームをしている.

山が二つ用意されていて、左の山には $A$ 個の物が、右の山には $B$ 個の物が積まれている.

それぞれ上から $i$ 番目の物の価値は $a_i, b_i$ である.

二人のプレイヤーは交互に以下の操作を繰り返す.

両方の山が空であれば、ゲーム終了
片方の山が空であれば、もう片方の山の一番上の物を取る.
両方の山が空でなければ、好きな方の山を選び、一番上の物を取る.

両者が最善を尽くした時の先攻の獲得した物の価値の合計を求めよ.

解法

$dp[i][j]$ : 左の山が $i$ 個、右の山が $j$ 個残っている状態でゲームをはじめた時の先攻が得られる最大の価値

最終的な出力は $dp[A][B]$ です. (左の山に $A$ 個, 右の山に $B$ 個残っている状態がゲーム開始時点なので)

今回の問題は、各プレイヤーが最善を尽くすので、先攻のターンと後攻のターンで場合分けをする必要があります.

先攻のターンのとき

先攻は残っている山の中で、一番価値の高いものを取ろうとします.

したがって、 $$ dp[i][j] = max(dp[i - 1][j] + a[A - i], dp[i][j - 1] + b[B - j]) $$ となります.

後攻のターンのとき

後攻のプレイヤーにはなるべく価値の低いものを選んでもらうようにするのが最善手です.

なお、相手が物を取っても、先攻の得点には関係ないので加算しません. $$ dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) $$

初期値

$dp[0][j]$ は左に山が残っておらず、右の山からしか物を取れないことを表しています.

したがって右の山の一番上を取った得点を初期値として格納します.

右の山が残っていない時も同様です.

$$ \begin{cases} dp[0][j] = dp[0][j - 1] + b[B - j] & (先攻) \\ dp[i][0] = dp[i - 1][0] + a[A - i] & (先攻) \\ dp[0][j] = dp[0][j - 1] & (後攻) \\ dp[i][0] = dp[i - 1][0] & (後攻) \end{cases} $$

ソース

使用言語はC++です.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int A, B;
    cin >> A >> B;
    int N = A + B;
    ll a[A], b[B];
    rep(i, 0, A) cin >> a[i];
    rep(i, 0, B) cin >> b[i];
    ll dp[A + 1][B + 1];

    dp[0][0] = 0;

    rep(i, 0, A + 1) {
        rep(j, 0, B + 1) {
            if(i == 0 && j == 0) continue;
            if((N - i - j) % 2 == 0) {
                if(i == 0) dp[0][j] = dp[0][j - 1] + b[B - j];
                else if(j == 0) dp[i][0] = dp[i- 1][0] + a[A - i];
                else dp[i][j] = max(dp[i - 1][j] + a[A - i], dp[i][j - 1] + b[B - j]);
            } else {
                if(i == 0) dp[0][j] = dp[0][j - 1];
                else if(j == 0) dp[i][0] = dp[i - 1][0];
                else dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    cout << dp[A][B] << endl;
}

2018-07-26

AtCoderの Typical DP Contestを解いてみた (A コンテスト)

競技プログラミング

問題を解く前に動的計画法の勉強
実際に問題を解いてみる
A コンテスト
- 問題の概要
ソース

競技プログラミングにハマってから避けてきた動的計画法 (Dynamic Programming, DP)を本格的に取得したいと思ったので、このブログでアウトプットしていこうと思います.

まず、DPって聞いたことあるしナップザック問題とかでやったことあるけど、他の問題に適用できないし...って状態だったので基本的なところの学習から始めました.

問題を解く前に動的計画法の勉強

私は、Qiitaのページを参考に一通り実装しました. qiita.com

このページではナップザック問題に入る前に簡単な最大和問題を例にDPについて説明してくれています.

この最大和問題はDPを使うまでもない問題なのですが、敢えてDPで解くことで、DPに慣れることができるという良問となっています.

この問題を解くことによって、ナップザック問題を含む他の問題が、最初から自分で実装できないまでも、解説を見て納得ができるようになりました.

実際に問題を解いてみる

今回練習問題として用いるのはAtCoderのTypical DP Contestです.

このコンテストはDPの練習を目的としたものらしいので取り掛かることにしました.

中身はまだ見てないのですが20問あり、どれもが典型的なDPの問題らしいです.

上で紹介したQiitaのページで一通り勉強した後に数をこなして慣れるためには適していると思います.

A コンテスト

今回は「A コンテスト」という問題を解きました.

(ちなみにDP初心者なので、もっと良いアルゴリズムがあるかと思いますがご了承ください. ソースもだいぶ汚いですが...)

問題の概要

(問題自体はAtCoderで確認してください.)

N問の問題があり、i問目の問題の配点は $p_{i}$ 点である.

この問題を何問か解いて、解いた問題の配点の合計が得点となる.

得点は何通り考えられるか.

$dp[i + 1][j]$ : i番目までのテストを解きj点にすることができるか (できればtrue, できなければfalse)

最終的な出力は $dp[n][0] \sim dp[n][100000]$ の中のtrueの数です.

( $n$ 個のテストで0点から100000点にすることができる数を求めています.)

$i$ 番目のテストを選ぶ時は $dp[i][j - a[i]]$ がtrueであれば $dp[i][j]$ もtureになります.

( $j - a[i]$ 点から $a[i]$ 点を加算するので)

選ばないときは $dp[i][j]$ と同じ値になります.

したがってDPの漸化式は以下のようになります.

$$ dp[i + 1][j] = \begin{cases} dp[i][j - a[i]] \, || \, dp[i][j] & (j >= a[i])\\ dp[i][j] & (else) \end{cases} $$

また、初期値は $dp[0][0] = 0$ です. 0個のテストで0点を取るのは0通りだからです.

ソース

使用言語はC++です.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int p[n];
    rep(i, 0, n) cin >> p[i];
    bool dp[n + 1][100001];
    rep(i, 0, n + 1) rep(j, 0, 100001) dp[i][j] = false;
    dp[0][0] = true;
    
    rep(i, 0, n) {
        rep(j, 0, 100001) {
            if(j >= p[i]) dp[i + 1][j] = (dp[i][j - p[i]] || dp[i][j]);
            else dp[i + 1][j] = dp[i][j];
        }
    }
    
    ll ans = 0LL;
    rep(i, 0, 100001) if(dp[n][i]) ans++;
    cout << ans << endl;

}

2018-05-29

vimでMarkdown記法をローカルでプレビューしたい

その他の忘備録

MarkdownでgithubのREADMEやはてなブログの記事をMarkdownで書いているとプレビューしたくなります。

今まではgithubであれば、addしてcommitしてpushしてブラウザで更新して間違っている箇所を修正という非常にめんどくさい作業を繰り返してました。。。

そこで、vimで編集してローカルでプレビューしたくなり、色々調べたら良いプラグインを見つけたので紹介したいと思います。

vimにプラグインを導入したいのですが、プラグインを管理するためにNeoBundleを使った方法を紹介します。もしNeoBundleがインストール済みであれば2節から読んでください。

1. NeoBundleのインストール方法
2. vimにプラグインを導入
3. 実行方法
4. 結果

1. NeoBundleのインストール方法

NeoBundleはプラグインの導入やアップデートが簡単になります。

$ mkdir ~/.vim/bundle
$ git clone https://github.com/Shougo/neobundle.vim ~/.vim/bundle/neobundle.vim

また、vimrcに以下の記述を追加します。

" Note: Skip initialization for vim-tiny or vim-small.
if 0 | endif

if &compatible
set nocompatible " Be iMproved
endif

" Required:
set runtimepath+=~/.vim/bundle/neobundle.vim/

" Required:
call neobundle#begin(expand('~/.vim/bundle/'))

" Let NeoBundle manage NeoBundle
" Required:
NeoBundleFetch 'Shougo/neobundle.vim'

" My Bundles here:
" Refer to |:NeoBundle-examples|.
" Note: You don't set neobundle setting in .gvimrc!

call neobundle#end()

" Required:
filetype plugin indent on

" If there are uninstalled bundles found on startup,
" this will conveniently prompt you to install them.
NeoBundleCheck

2. vimにプラグインを導入

必要なプラグインをインストールします。 NeoBundleをインストールしていれば、

NeoBundle 'plasticboy/vim-markdown'
NeoBundle 'kannokanno/previm'
NeoBundle 'tyru/open-browser.vim'

と記述して保存するだけで大丈夫です。その後

:NeoBundleInstall

でプラグインを導入するか、次にvimを開いたときにインストールするか聞かれるのでyesと答えればインストールが始まります。

最後に.md拡張子ファイルもmarkdownとなるように

au BufRead,BufNewFile *.md set filetype=markdown

と記述して終わりです。

3. 実行方法

vimでMarkdown記法で編集します。その後

:PrevimOpen

と打つとローカルで表示されます。

4. 結果

2018-05-29

matplotlibのインストールにつまずいたお話

その他の忘備録

新しいmacbookにmatplotlibをインストールしようとした時に少しつまずいたので備忘録として記事にします。

1. 吐き出したエラー達
2. 解決策

1. 吐き出したエラー達

まず普通に

pip install matplotlib

でインストールしようとすると

Command "python setup.py egg_info" failed with error code 1 in /private/tmp/pip-build-oeUHU7/matplotlib

と出ました。

もう少し上の文を見ると

* The following required packages can not be built :
* freetype
* Try installing free type with `brew install
* freetype` and pkg-config with `brew install pkg-
*config

と書いてあったので

brew install freetype
brew install pkg-config

でそれぞれインストールしました。

その後、(念のためpipをupgradeする)

pip install --upgrade pip
pip install marplotlib

とすると、先ほどとは違う感じになってうまく行きそうになるがやっぱり失敗します。

原因を探ると、

Uninstalling six-1.4.1:
(略)
OSErro: [Errno 1] Operation not permitted (hoge hoge)

つまり、すでにインストールされていたsixをアンインストールしようとしてるけど権限がなくてエラーが起きているそうです。

2. 解決策

なので、sixを無視するために、

pip install matplotlib --ignore-installed six

というオプションをつけました。

その結果、無事インストールに成功しました。