競プロ参加記036 AtCoder Regular Contest 113(ARC113)

Atcoder

はじめに

AtCoder Regular Contest 113 – AtCoder

A～Dの4完でした。
今回はC,Dが易しめでした。

早解きにやや成功したので、レートも上がって1569(+21)になりました。青が目前ですね！

A – A*B*C

A – A*B*C (atcoder.jp)

感覚からA*B*C<=KはKの最大2*10^5であってもそんなに多くないと感じました。
こんな時に便利なのがコードテストです。

コードテスト – AtCoder Regular Contest 113

計算量が分からない場合、ここに最大入力を投げて何msで返ってくるか観察することでACかTLEかを見極めることができます。
A*B*C全探索コードを入力200000で投げたところ18msで返ってきました。問題なさそうです。

#include<bits/stdc++.h>

using namespace std;

int main(){
    long long K;
    cin>>K;

    long long ans=0;
    for(long long A=1;A<=K;A++){
        for(long long B=1;;B++){
            if(A*B>K) break;
            for(long long C=1;;C++){
                if(A*B*C>K) break;
                ans++;
            }
        }
    }
    cout<<ans<<endl;
}

B – A^B^C

B – A^B^C (atcoder.jp)

10進法の1の位のため、A%10を考えれば良さそうです。
また与えられる数はAを複数回掛けた数です。A%10は規定回数でループする(A%10=2の場合、2->4->8->6->2と周期4でループする)ため、B^Cによって何回掛けるかを求めれば良さそうです。

B,Cの最大が10^9であるため、B^Cを単純に計算できません。
A%10が周期mでループする場合mの倍数回掛けると元に戻ります。
なので、(B^C)%mを求めれば計算できそうです。(mを一定回かけた後に、あぶれた数が知りたい)

#include<bits/stdc++.h>

using namespace std;
// https://algo-logic.info/calc-pow/
long long MOD = 1000000007;
long long mpow(long long x, long long n) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1) ret = ret * x % MOD;  // n の最下位bitが 1 ならば x^(2^i) をかける
        x = x * x % MOD;
        n >>= 1;  // n を1bit 左にずらす
    }
    return ret;
}

int main(){
    long long A,B,C;
    cin>>A>>B>>C;
    A%=10;

    vector<int> v;
    v.push_back(A);
    int fA=A;
    A*=fA;
    A%=10;
    while(1){
        if(A==v[0]) break;
        v.push_back(A);
        A*=fA;
        A%=10;
    }

    if(v.size()==1) cout<<v[0]<<endl;
    else{
        MOD=v.size();
        long long nx=mpow(B,C);
        nx--;
        if(nx==-1) nx=v.size()-1;
        //cout<<nx<<","<<v.size()<<endl;
        cout<<v[nx]<<endl;
    }
}

B^Cの計算はmod付きの繰り返し二乗法を使いました。

繰り返し二乗法によるべき乗(pow(x,n))の計算のアルゴリズム | アルゴリズムロジック
多くのプログラミング言語でサポートされてる \(x^n\) を計算する関数のアルゴリズムです。 Input : pow(2,4) (x=2, n=4)Output : 16 べき...
algo-logic.info

こちらのサイトのものをお借りしています。
powはO(乗数)かかるため、C=10^9のときにTLEします。繰り返し二乗法の場合、O(log乗数)になるので十分高速です。

C – String Invasion

C – String Invasion (atcoder.jp)

bccdaaeのときにccで置き換え処理を行うと、
bccccccとなります。このとき、後ろにあるaaが消えてしまい本来できる置き換えが消えてしまいます。
aaを先にすると、bccdaaaとなりccは消えないのでbccccccとできます。

上記操作例の通り、操作が後ろにしか影響を与えないため、後ろから操作できる順にやっていった方がお得です。
(一番後ろの操作は前の文字に影響はない)

#include<bits/stdc++.h>

using namespace std;

int main(){
    string S;
    cin>>S;

    long long c[1000]={0};
    long long ans=0;
    for(long long i=(long long)S.size()-1;i>=1;i--){
        if(S[i]!=S[i-1]){
            c[S[i]]++;
        }
        else{
            char n=S[i];
            long long num=(long long)S.size()-1-i-c[n];
            //cout<<num<<","<<c[n]<<endl;
            if(num>=0) ans+=num;
            for(long long j='a';j<='z';j++) c[j]=0;
            c[n]=(long long)S.size()-1-i+1;
        }
    }
    cout<<ans<<endl;
}

500点にしてはかなり簡単なので無駄に反例を探していました。
B問題の方が難しい…ですよね…。

D – Sky Reflector

D – Sky Reflector (atcoder.jp)

列対(A,B)について考えます。

N=2 M=3
x x x
x x x
で考えたときに
Aiがn,mのとき
n n以上 n以上
m m以上 m以上
や、これの各行の数字同士を入れ替えたマスが該当する。
このとき、Bjは最大をとるため最小はmax(n,m)になる。最大はn以上、m以上が好きに置けるのでKまで取れる。

となります。
そのため、Amaxが1の場合、各Bは1～KになれるのでK^Mになります。
Amaxが2の場合、各Bは2～KになれるのでK^(M-1)になります。
Amaxがnであるときの組み合わせの個数が分かれば解けそうです。

Amaxがnのとき、A1～ANは少なくとも1つはnで、それ以外はn以下でなくてはいけません。
“少なくとも1つは”が出た場合、包除原理で求めることができます。
具体的には、1～nを自由に組み合わせた通りn^Aから1～n-1を自由に組み合わせた通りn^(A-1)を引けばいいです。(1～n-1だけの組み合わせが除かれるので、残ったものにはnが1つはあるはず)

nは1～Kの好きな範囲が取れるため、上記考察を纏めて

∑(i=1～K)(pow(i,N)-pow(i-1,N))*pow(K-i+1,M)

となります。

これで終わり！ではなく、NかMが1の場合は別処理が必要になります。
というのも、上記式はnとn以上の2つがあることを前提にしているため、NかMが1のときは2つ作れず破綻します。
NかMが1のときは、各マスにKを好きに置ける(N=1なら、Bjは各列にある数字がそのまま入る)ので、どちらかが1によってB^MかA^Nになります。

#include<bits/stdc++.h>
//#include<boost/multiprecision/cpp_int.hpp>
#include<atcoder/all>

using namespace std;
//using namespace boost::multiprecision;
using namespace atcoder;

int tn,tmm;
int ta[100];
set<vector<int>> ts;
void testdfs(int n){
    if(n==tn*tmm){
        vector<int> v;
        for(int i=0;i<tn;i++){
            int mn=1000;
            for(int j=0;j<tmm;j++){
                mn=min(mn,ta[i*tmm+j]);
            }
            v.push_back(mn);
        }
        for(int i=0;i<tmm;i++){
            int mx=0;
            for(int j=0;j<tn;j++){
                mx=max(mx,ta[i*tn+j]);
            }
            v.push_back(mx);
        }
        ts.insert(v);
    }
    else{
        for(int i=0;i<2;i++){
            ta[n]=i;
            testdfs(n+1);
        }
    }
}
//16 +12+8+4+ 27+14+
void test(){
    tn=2,tmm=2;
    testdfs(0);
    cout<<ts.size()<<endl;
    auto it=ts.begin();
    while(it!=ts.end()){
        vector<int> v=*it;
        for(int i=0;i<v.size();i++){
            cout<<v[i]<<" ";
        }
        cout<<endl;
        it++;
    }
}

// https://algo-logic.info/calc-pow/
int MOD = 998244353;
long long mpow(long long x, long long n) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1) ret = ret * x % MOD;  // n の最下位bitが 1 ならば x^(2^i) をかける
        x = x * x % MOD;
        n >>= 1;  // n を1bit 左にずらす
    }
    return ret;
}

int main(){
    //test();
    long long N,M,K;
    cin>>N>>M>>K;

    if(N==1&&M==1) cout<<K<<endl;
    else if(N==1){
        cout<<mpow(K,M)<<endl;
    }
    else if(M==1){
        cout<<mpow(K,N)<<endl;
    }
    else{
        modint998244353 ans=0;
        for(long long i=1;i<=K;i++){
            long long nn=mpow(i,N)-mpow(i-1,N);
            long long mm=mpow(K-i+1,M);
            ans+=nn*mm;
        }
        cout<<ans.val()<<endl;
    }
}

test()関数がありますが、この考察をする前に愚直解を作って答えを眺めて法則性を探していました。
分からなければ取り合えず愚直解を作って眺めるのは、大事な気がします。(多分)

おわりに

青になればAGCが解放されるので、AGCの練習もしたいところです…。
AGCにはあんまりいい思い出がないので少し怖いですね。

コメント

タイトルとURLをコピーしました