h3mky0's blog

主に競プロについて書きます

Educational Codeforces Round 49 E. Inverse Coloring

問題リンク
Problem - E - Codeforces

問題概要
n*nの正方形を白か黒のどちらかで塗りつぶすとき, 次の条件を満たすものの組み合せ数を答える
・隣接する行および列は同じ色か異なる色でなければならない. （言い換えると, 白に縦1*横3と塗っている場合, その下の行には白の1*3か黒の1*3しか来ないみたいな感じ）
・塗った時にできる長方形の大きさがk未満

続きを読む

AOJ1161 Verbal Arithmetic

問題概要
覆面算を解く.
なお以下の条件を満たしているものとする.

  • String_{1} + String_{2} + ... + String_{N-1} = String_{N}
  • それぞれの文字はそれぞれ独立した数字を表す
  • |String|が2以上のとき, Leading zeroは不可
  • 与えられる文字列数は3以上12以下, 文字列全体に含まれる文字の種類数は1以上10以下

解法
適当な全探索コードを書くとTLEした.
定数倍高速化したコードを投げたら8.2sで通ったが, 他の方のコードだとmsで通っているみたいなので別の方針を考える.

各文字について次のように分解する
例：ICPC ⇔ 1000*I + 100*C + 10*P + C

そして, 左辺から右辺を引くことで方程式を解く問題に帰着できる.
各変数は0から9の値を取ることや同じ値を持たないことに注意しながら半分全列挙をすることで高速に解くことができる.

ACコード

map<int, vector<ll>> han;
map<int, vector<ll>> han2;
bool lead[26];
void dfs(int d, int mask, int end, ll val, vector<pair<ll, char>>& v){
    if(d == end){
        han[mask].push_back(val);
        return;
    }

    int word = v[d].second - 'A';

    for(int i=0; i<10; i++){
        if((mask & (1<<i)) != 0) continue;
        if(i == 0 && lead[word]) continue;
        dfs(d+1, mask | (1<<i), end, val + v[d].first*i, v);
    }
}

void dfs2(int d, int mask, int end, ll val, vector<pair<ll, char>>& v){
    if(d == end){
        han2[mask].push_back(val);
        return;
    }
    int word = v[d].second - 'A';

    for(int i=0; i<10; i++){
        if((mask & (1<<i)) != 0) continue;
        if(i == 0 && lead[word]) continue;

        dfs2(d+1, mask | (1<<i), end, val + v[d].first*i, v);
    }
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(18);
    int N;
    while(cin >> N, N){
        han.clear();
        han2.clear();
        map<char, int> mp;
        for(int i=0; i<26; i++)lead[i] = false;
        for(int i=0; i<N-1; i++){
            string s; cin >> s;
            ll cur = 1;
            for(int j=s.size()-1; j>=0; j--){
                mp[s[j]] += cur;
                cur *= 10; 
            }
            if(s.size() != 1){
                lead[s[0]-'A'] = true;
            }

        }
        {
            string s; cin >> s;
            ll cur = 1;
            for(int j=s.size()-1; j>=0; j--){
                mp[s[j]] -= cur;
                cur *= 10;
            }
            if(s.size() != 1){
                lead[s[0]-'A'] = true;
            }
        }

        vector<pair<ll, char>> v;
        for(auto e: mp){
            v.push_back(make_pair(e.second, e.first));
        }

        int n = v.size()/2;
        int n2 = v.size()-n;

        dfs(0, 0, n, 0, v);

        dfs2(n, 0, v.size(), 0, v);
        int ans = 0;
        for(auto e: han){
            int mask = e.first;

            for(auto f: han2){
                int mask2 = f.first;
                if((mask & mask2) != 0) continue;
                
                for(int i=0;i<e.second.size(); i++){
                    for(int j=0;j<f.second.size(); j++){
                        if(e.second[i]+f.second[j] == 0) {
                            ans++;
                        }
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

CODE FESTIVAL 2014 Easy D - 枕決め

atcoder.jp

典型的な貪欲問題

問題概要
N人の人とM個の枕がある。
N人はそれぞれA_i以上B_i以下高さの枕が好みである。
それぞれの枕がせいぜい一度しか選べないとき、好みの枕を使用できる人の最大数を求める。

考えたこと
制約からO(N)かO(NlogN)が見える。とりあえず貪欲で考えてみる。

初めにA_iとB_iの間隔が小さい順にソートして、条件を満たす枕を小さい順に二分探索で探すような処理をする→WA

確かにこれは,
3 3
1 2
1 2
2 3
のケースで落ちる。

終点を固定して、その終点までの最大値を貪欲に求めていけばよさそう。
区間スケジューリングの要領でB_iの小さい順にソートして、条件を満たす枕を小さい順に二分探索で探すような処理をする→AC

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);
  
  int n, m; cin >> n >> m;
  vector<pair<int, int>> vp(n);
  vector<int> a(m);

  REP(i,n){
    int x,y;cin >>x >> y;
    vp[i] = make_pair(y, x); 
  }
  sort(all(vp));
  BIT<int> bit(100010);
  REP(i,m)cin>>a[i], bit.add(a[i], 1);
  int ans = 0;
  REP(i,n){

    int lb = vp[i].second-1, ub = vp[i].first+1;
    int aba = bit.sum(lb+1);
    while(ub-lb>1){
        int mid = (ub+lb)/2;
        if(bit.sum(mid+1)-aba >= 1){
            ub = mid;
        }else{
            lb = mid;
        }
    } 
    if(ub == vp[i].first+1) continue;
    ans++;
    bit.add(ub,-1);
  }
  cout << ans << endl;
  return 0;
}

priority_queueは全く思いつかなかった。実質的にやってることは同じだと思います

Codeforces Round #494 (Div. 3) F. Abbreviation

問題リンク
https://codeforces.com/contest/1003/problem/F

問題概要
n個の単語が与えられる。単語同士の間に空白をおいて連結した文字列sについて、2つ以上の単語を連結したものを略語で表すとき最小の長さはいくつになるか。
例えば、to be or not to be なら, to be を略語に置き換えて（to be を TB）, TB or not TBとなり, 18字から12字になる。

考えたこと
（ある文字の長さ）* （文字の頻度）が最も大きいものを略字で表せばよい。
文字の出現回数及び出現するindexはKMP法を使えばO(|S|)求めることができるので, i < jを満たす(i, j)についてチェックすればよい
全体の計算量はO(n^3) でn \leq 300なので十分間に合う
文字で扱うといろいろ面倒なので数字に変換する。

ACコード

感想
stringがキーのmapを持つとTLEしたので注意したい。大小比較でO(|S|), 検索でO(logN)。

AOJ2608 Minus One

問題概要
無向グラフGについて2点s, tの最短経路をd_{\min }としたとき、 e = \left( u,v\right) （ただし, u\not=v ）を満たす辺を追加したときのs, t間の最短経路がd_{\min }-1となるような辺はいくつ存在するか。
各辺の重みは1とする。

考えたこと
いま e = \left( u,v\right)を考えた時, d_{s,u} + d_{u,v} + d_{v,t} = d_{\min }-1 を満たせばよい。
すなわち, d_{v,t} = d_{\min }-1 - d_{s,u} - d_{u,v}を考えればよく, これは頂点s, tについて各点の最短経路を求め, sからの距離を固定して条件を満たす辺を全探索すればよい。
計算量はO(n)

ACコード

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
 
typedef long long ll;
vector<vector<int>> g(100010);
int ds[100010];
int dg[100010];
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    
    
    int N, M, s, t; cin >> N >> M >> s >> t;

    s--; t--;

    REP(i,M){
        int x, y; cin >> x >> y;
        x--; y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    REP(i,N) ds[i] = dg[i] = INT_MAX;

    {
        queue<int> q;
        q.push(s);
        ds[s] = 0;
        while(q.size()){
            int v = q.front();
            q.pop();

            for(int i=0; i<g[v].size(); i++){
                if(ds[g[v][i]] == INT_MAX){
                    ds[g[v][i]] = ds[v] + 1;
                    q.push(g[v][i]);
                }
            }
        }
    }

    
    {
        queue<int> q;
        q.push(t);
        dg[t] = 0;
        while(q.size()){
            int v = q.front();
            q.pop();

            for(int i=0; i<g[v].size(); i++){
                if(dg[g[v][i]] == INT_MAX){
                    dg[g[v][i]] = dg[v] + 1;
                    q.push(g[v][i]);
                }
            }
        }
    }

    map<ll, ll> mp, mp2;
    REP(i,N){
        mp[ds[i]]++;
        mp2[dg[i]]++;
    }

    int e = ds[t]-2;
    ll ans = 0;
    for(int i=0; i<=e; i++){
        int v = e-i;
        
        ans += mp[i] * mp2[v];
    }
    cout << ans << endl;
    return 0;
}

使ったサイト
入力した数式をtex形式に変換してくれる
webdemo.myscript.com