読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

yukicoder 15/16/17

- 15 カタログショッピング

  • 問題概要

合計金額と、各商品の金額が与えられます。
何を買ったのか答えてくださいという問題です。

  • 解説

商品の金額が小さければDPの典型です。
DPで解きたいのですが商品の金額が大きすぎるためTLEになってしまいます。
商品数が31であることに着目します。
1~15の商品の組み合わせは2^15通り、16~31の商品の組み合わせは2^16通りです。
この二つを求め、二つを合わせた金額が合計金額と一致する組み合わせを求めれば良さそうです。
両側探索ですね。

Indeedなうで両側探索が出て結構衝撃だったのでそれ以来割とすぐに思いつくようになりました。

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>
#include<functional>
using namespace std;
vector<int> ans;
#define LL long long
map < LL, list<int>> memo;
int N, half;
LL S;
LL P[40];
void left(int n,LL val,int bit){
    if (n == half){
        memo[val].push_back(bit);
    }
    else{
        left(n + 1, val, bit);
        left(n + 1, val + P[n], bit + (1 << (N - 1 - n)));
    }
}

void right(int n, LL val, int bit){
    if (n == N){
        if (memo.count(S - val) > 0){
            for (auto &b : memo[S - val])
                ans.push_back(b + bit);
        }
    }
    else{
        right(n + 1, val, bit);
        right(n + 1, val + P[n], bit + (1 << (N - 1 - n)));
    }

}

int main(void){
    ans.reserve(50);
    cin >> N >> S;
    for (int i = 0; i < N; i++)
    {
        cin >> P[i];
    }
    half = N / 2;
    left(0, 0, 0);
    right(half, 0, 0);
    sort(ans.begin(), ans.end(), greater<int>());
    for (auto &bit : ans){
        list<int> tmp;
        for (int i = N - 1; i >= 0; i--)
            if (bit&(1 << i))tmp.push_back(N - i);
        for (auto it = tmp.begin(); it != tmp.end(); ++it){
            if (it != tmp.begin())cout << " ";
            cout << *it;
        }
        cout << endl;
    }

    return 0;
}

- 16 累乗の加算

  • 問題概要
  • 解説

各項についてpowmodをして加算してmodをとるだけです(雑)
powmodが分からない人はmodの四則演算と繰り返し二乗法(バイナリー法)について要チェックです。
もっと高速化する方法がありますが今回は間に合うのでpowmodだけです。
modが小さいので周期性を求めてうんぬんって手法があります。

#include<iostream>


#include<functional>
using namespace std;
#define LL long long
#define mod 1000003
inline LL powmod(LL x, int a){
    LL res = 1;
    for (int i = 0; i < 31; i++){
        if (a&(1 << i))res = (res*x) % mod;
        x = (x*x) % mod;
    }
    return res;

}
int main(void){
    LL x,res=0;
    int N;
    int a;
    cin >> x >> N;
    for (int i = 0; i < N; i++)
    {
        cin >>a;
        res = res + powmod(x, a);
    }
    cout << res%mod << endl;
    return 0;
}

- 17 2つの地点に泊まりたい

  • 問題概要

問題文が都市なのか地点なのかブレブレ
0からN-1のN個の都市があって、移動コストが存在するM個の辺が存在します。
また、各都市には滞在コストが存在します。
0からN-1まで二日間かけて移動したいので、2カ所泊まる場所を決めなくてはなりません。
0とN-1以外の異なる二都市で宿泊をするとき滞在コストと移動コストの合計の最小値を求めてくださいという問題です。

  • 解説

ワーシャルフロイドで全頂点間最短距離を求めておけば、ある異なる二地点ijを決めたとき、かかるコストは移動コストd(0,i)+d(i,j)+d(j,N-1)と滞在コストt(i)+t(j)の合計値の最小値が解になります。全てのi,jについて求めればいいので、全体の計算量はO(N^3)となります。

#include<iostream>
#include<algorithm>
using namespace std;

int d[50][50];
int rest[50];
const int INF = 1e9;
int main(void){
    int N,M, res = INF;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> rest[i];
        for (int j = 0; j < N; j++)
        {
            if (i != j)d[i][j] = INF;
        }
    }
    cin >> M;
    for (int i = 0; i < M; i++)
    {
        int x, y, c;
        cin >> x >> y >> c;
        d[x][y] = d[y][x] = c;
    }
    for (int k = 0; k < N; k++)for (int i = 0; i < N; i++)for (int j = 0; j < N; j++)
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    for (int i = 1; i < N-1; i++)
        for (int j = 1; j < N-1; j++)
            if (i != j){ 
                res = min(res, rest[i] + rest[j] + d[0][i] + d[i][j] + d[j][N - 1]);
            }
    cout << res << endl;
    return 0;
}