【CODEFORCES】Molly's Chemicals

CODEFORCESの問題

Problem - C - Codeforces

参考書

プログラミングコンテストチャレンジブック [第2版]

難しさ（初心者目線）

・考え方****

・実装**

・面白さ****

ヒント(カーソル合わせると見れます)

問題概略

・n個の異なった薬品を持っている
・薬品iの効果はである
・n個の薬品が並べられるので連続した薬品を選んで混ぜて整数kの累乗になるようにしたい
・この時の混ぜ方は何通りあるか

入力

n k

1≦n≦
1≦|k|≦10
≦≦

例

Input

4 2
2 2 2 2

Output

8

n=4, k=2の問題
になるのは左から1個目のみ,2個目のみ,3個目のみ,４個目のみ選んだ場合
になるのは左から[1,2]と[2,3]と[3,4]のセットを選んだ時
同様に,になる場合も調べたら8通りになる

Note

であることに注意

考え方

左からの合計値sumをmapに保存していきsum-k^x（図中黄色い丸）が存在すれば残りはk^x（図中青い丸）である
forは太い青い矢印とk^xを求める部分
愚直な実装は青い太い矢印の2重ループだと思うが、0(N²)で間に合わない
k^xは10¹⁵程度まで調べれば良いので数回であるから早い

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

//方針
//愚直に全探索（2重のfor）でやるとO(N^2)でTLEしてしまう
//[1,i](i=1~N)で作れる薬品の効果をmap[効果]=1としておく
//1~Nで見ていく
//map[1~iの和-k^x]==1だと作れる(ans++)

int main(){
    int n, k;
    cin >> n >> k;

    //map用意αが大きいのでllとしておく
    //0は何も使わない時なので作れるので1としておく
    map<ll, int> MAP;
    MAP[0] = 1;

    ll int ans = 0;
    ll int sum = 0;
    FOR(i, 0, n){
        int input;
        cin >> input;

        //これまで調べた薬品を全て使用した時の和
        sum += input;
        //k=1の時は1を何乗しても1なので1を引く
        if(k == 1){
            ans += MAP[sum-1];
        }
        //k=-1の時は1と-1になるかどうか調べる
        else if(k == -1){
            ans += MAP[sum-1] + MAP[sum+1];
        }
        else{
            //|k|>1の時は十分大きな数まで調べる
            int j = 0;
            while(1){
                ans += MAP[sum-pow(k,j)];
                j++;
                if(abs(pow(k, j))>pow(10,15)) break;
            }
        }
        //これまで調べた薬品を全て使用した時の和を保存
        MAP[sum]++;
    }
    cout << ans << endl;
}

コメント

連続した値の和がxになるかどうかという問題があったらこの方法を用いたいと思う.