問題概要

ある n+1 ($ n \leq 2000 $) 桁以下の数値について，隣あった桁の数字の大小関係が "=!><" の文字を含む長さ n の文字列で与えられる．

このとき，「ある n+1 桁以下の数値」としてありうる最小の数を求めよ．leading zero(s) を含んではいけない．

解法概要

(何桁目まで決定したか, 最後に決定した桁の数) の組を状態として，上の桁から順に見ていく．最小の数を求めたいので小さい数字から順番に試していき，その数字にしてもその後 (それよりも下の桁で) 矛盾が出ないとなったら OK．

全ての状態について，もう計算した/してないを管理しておけば (ソースコード中の visited)，状態の数は高々 2000 * 10 通りなので余裕で間に合う．

小さい順に試すだけではなく，「この状態はもう計算済み？」「計算済みだとしたら，この状態を使って条件を満たす数値は作れる？」この2つをフィードバックさせることが大事．

ソースコード

#include <string>
#include <iostream>

using namespace std;

bool visited[2001][10], ok[2001][10]; // true で初期化されているので注意
int next_digit[2001][10];

class ReconstructNumber {
    public:

    int n;
    string s;

    // i桁目をjと決めたとき，(i+1)桁めを決める
    bool solve(int i, int j) {
        if(i == n) return true;
        if(visited[i][j]) return ok[i][j];
        
        visited[i][j] = true;

        if(s[i] == '=') {
            if(solve(i+1, j)) {
                ok[i][j] = true;
                next_digit[i][j] = j;
                return true;
            }
        } else if(s[i] == '!') {
            for(int k=0;k<10;++k) {
                if(j == k) continue;
                if(solve(i+1, k)) {
                    ok[i][j] = true;
                    next_digit[i][j] = k;
                    return true;
                }
            }
        } else {
            int k_min = ((s[i] == '<')?j+1:0), k_max1 = ((s[i] == '<')?10:j);
            for(int k=k_min;k<k_max1;++k) {
                if(solve(i+1, k)) {
                    ok[i][j] = true;
                    next_digit[i][j] = k;
                    return true;
                }
            }
        }
        return false;
    }
    
    string smallest(string comparisons) {
        s = comparisons;
        n = s.length();
        fill(visited[0], visited[n+1]+10, false);
        fill(ok[0], ok[n+1]+10, false);
        
        for(int j=1;j<10;++j) {
            if(solve(0, j)) {
                string ans = "";
                int d = j;
                for(int i=0;i<n;++i) {
                    ans += char('0' + d);
                    d = next_digit[i][d];
                }
                ans += char('0' + d);
                return ans;
            }
        }
        return "";
    }
};

所感

tourist 氏に撃墜してもらった思い出の問題．

再帰で実装するとスマートに解けるタイプのDP，要精進．

2019-03-04

Educational DP Contest X - Tower

競技プログラミング (問題解説)

X - Tower

問題概要

N個のブロックがあり，i番目のブロックは重さ$ w_i $，価値$ v_i $であり，そのブロックには重さが計$ s_i $までのブロックを載せることができる．

これらのブロックを1列に積み上げてタワーを作るとき，タワーの価値の最大値を求めよ．

解法概要

Wは$ w_i, s_i$の取りうる最大値として， Wがそんなに大きくないので， $ dp_i = $全体の重さがiのときの全体の価値ができそう．あとは追加順序を固定できれば楽勝なのだが……．

追加順序のために，ブロック$ i$とブロック$ j$について考える．

もしや$ s_i \leq s_j $のとき，ブロックiはブロックjよりも上に置かれると考えて良いのでは？
- →入力例2が反例
かといって $ w_i \leq w_j $のときも順序の固定はできない
- めっちゃ軽くてめっちゃ力持ちなブロックは下に置かれるべき
それなら$ s_i+w_i \leq s_j+w_j $の場合はどう？
- 例えばブロックiを1番下に置いた場合，その地点での全体での重さは$ s_i+w_i$以下になるはずなので，それっぽい？
  - 証明できんの？→ということで，証明してみよう！

証明したいこと: 複数のブロックでタワーを作るとき，$ s_i+w_i \leq s_j+w_j$ であるブロックi,j について，ブロック j をブロック i の上に置けるならば，ブロック i をブロック j の上に置くことも必ずできる．

分かりづらいが，以下のメモのようなことが言いたい (図中の i と j の違いが分かりづらくてごめんなさい) ．

f:id:noimin:20190304190301j:plain

ブロック j をブロック i の上に置けるということは

$ w_0 + w_j \leq s_i$ ($ w_0$はブロック i と j よりも上に積み上げてあるブロックの重さの和) ．

したがって $ w_o \leq s_i - w_j$ (1)

また，$ s_i+w_i \leq s_j+w_j$ と仮定しているので$ s_i+w_i-w_j \leq s_j$ (2)

(1), (2) より

$ w_0 + w_i \leq s_i + w_i - w_j \leq s_j$

よって $ w_0 + w_i \leq s_j$で，ブロック i の上にブロック j を置くことができる．

以上より，ブロック j をブロック i の上に置けるとき，ブロック i をブロック j の上に置くことも必ずできる．

結論として，$ s_i+w_i$で並べ替えてナップサック問題を解くときと同様のDPをすれば良い．

ソースコード

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

const int MAX_W = 20000;

struct Block {
    ll w, s, v;    
    Block(ll w=0LL, ll s=0LL, ll v=0LL): w(w), s(s), v(v) {}
    bool operator<(const Block b) const{
        return w+s < b.w+b.s;
    }
};

ll dp[2][MAX_W+1];

int main() {
    int n;
    cin >> n;
    vector<Block> blocks(n);
    for(int i=0;i<n;++i) {
        cin >> blocks[i].w >> blocks[i].s >> blocks[i].v;
    }
    sort(blocks.begin(), blocks.end());

    // 上から置いていく
    dp[0][0] = 0LL;
    for(int i=0;i<n;++i) {
        int i_mlb = i & 1;
        for(int j=0;j<=MAX_W;++j) {
            dp[1-i_mlb][j] = max(dp[1-i_mlb][j], dp[i_mlb][j]);
            if(j+blocks[i].w <= MAX_W && j <= blocks[i].s) {
                dp[1-i_mlb][j+blocks[i].w] = max(dp[1-i_mlb][j+blocks[i].w], dp[i_mlb][j] + blocks[i].v);
            }
        }
    }

    ll ans = *max_element(dp[n&1], dp[n&1]+MAX_W+1);
    cout << ans << "\n";
}

所感

少し真面目 (※当社比) に考察 & 実装したのでメモを残しておく．

なぜその値でソートするのかや，なぜ貪欲で良いのかの証明パワーを強化したい．

2019-03-02

みんなのプロコン決勝 2019 A - Affiches

競技プログラミング (問題解説)

A - Affiches

問題概要

H×W の大きな紙 1 枚と，A×B の小さな紙 2 枚がある．小さな紙 2 枚を大きな紙の上にはみ出さないように貼る．このとき，小さな紙同士が重なっていても構わない．小さな紙の左上の座標が [0, H-A]×[0, W-B] 上の独立な一様分布に従うとしたとき，小さな紙同士が重なった面積の期待値を求めよ．

解法概要

小さな紙の左上の座標が [0, H-A]×[0, W-B] 上の独立な一様分布に従うとあるので，縦と横はそれぞれ独立に考えてあとから掛け合わせれば良い．したがって，(重なった部分の縦の長さの期待値) × (重なった部分の横の長さの期待値) を求めたい．

縦の長さのみについて考える．重なった部分の縦の長さの期待値は，(考えうるすべての場合の「重なった部分の縦の長さ」の和) / (H-A)² で求められる．小さな紙の左上の座標値は整数とは限らないため，(考えうるすべての場合の「重なった部分の縦の長さ」の和) の部分を頑張って積分で計算する．例えば，私の場合は次のような計算した．初めから 1 枚目と 2 枚目のどちらの座標が大きい場合にも対応するのではなく，まずは 1 枚目の座標が 2 枚目の座標以下だと仮定して積分を求め，後からそれを 2 枚して (考えうるすべての場合の「重なった部分の縦の長さ」の和) を求めている．

f:id:noimin:20190302233108j:plain

ソースコード

いつもの C++ ではなく，なぜか Python．

def f(H, A, a):
    return (-a**3/3 + (H-2*A)*a**2-(H-A)*(H-3*A)*a) / 2

def calc(H, A):
  ret = f(H, A, H-A)
  if H-2*A > 0:
    ret -= f(H, A, H-2*A)
    ret += A**2 * (H-2*A) / 2
  return 2*ret / (H-A)**2

H,W,A,B = map(float, input().split())

ans = calc(H, A) * calc(W, B)
print(ans)

所感

積分の計算が苦手なのに慢心してミスしまくってしんどかった

NoiminのNoise

TopCoder SRM 752 Div 1 Easy - ReconstructNumber

問題概要

解法概要

ソースコード

所感

Educational DP Contest X - Tower

問題概要

解法概要

ソースコード

所感

みんなのプロコン決勝 2019 A - Affiches

問題概要

解法概要

ソースコード

所感