競プロのーと

私が解いた競プロの問題をまとめていきます。性質上問題のネタバレもあるのでご了承ください

DDCC(DISCO presents ディスカバリーチャンネル コードコンテスト2019)予選

AtCoder DDCC

DDCC予選に参加しました。ABの2完でした。もっと精進します。

A:チップ・ストーリー　～無色編～

A: チップ・ストーリー ～無色編～ - DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選 | AtCoder

Nが与えられるので4Nを計算するだけ。

コード

#include<iostream>
using namespace std;
 
int main(){
    int n;
    cin>>n;
    int ans=1;
    for(int i=0; i<n; i++)ans*=4;
    cout<<ans<<endl;
    
    return 0;
}

B:チップ・ストーリー　～漆黒編～

B: チップ・ストーリー ～漆黒編～ - DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選 | AtCoder

問題概要は文章で説明しずらいのでリンク先見てください。

考察

すぐに思いつくのは難しいですが簡単な場合分けでできます。まずN=3のときを考えて、このような図を作ります。
0 0 0
0 3 0
0 0 0
中心の3は新たに黒に塗りつぶされているマスなのでそこを3と置きます。同様に5を考えると、
00000
00500
05350
00500
00000
このように、5において新たにカウントされるマスは4マスです。同様に7,9でやると、
000000000
000090000
000979000
009757900
097535790
009757900
000979000
000090000
000000000
このようになります。ここで5の数、7の数、11の数に着目すると、(5の個数)=(3の個数)+4のような関係が成り立っていて、Nが奇数の時、一般に(Mの数)=(M-2の数)+4となります。Nが偶数の時も同様に考えると、(4の個数)=4で、(Mの個数)=(M-2の個数)+4の関係が成り立つことがわかります。
簡単な階差数列であることがわかったので、あとはNを偶奇で場合分けして、forループで足していけばACできます。

コード

#include<iostream>
using namespace std;
 
int main(){
    
    int n,ans;
    cin>>n;
    int m=n/2;
    if(n%2==0){
        for(int i=0; i<m; i++){
            ans+=i*4;
        }
    
    }else if(n%2==1){
        ans=1;
        for(int i=0; i<m; i++){
            ans+=i*4;
        }
    }
    cout<<ans<<endl;
    
    return 0;
}

（それぞれのマスに対して黒いかどうか判定することもできるようです。）

C:チップ・ストーリー　～白銀編～

C: チップ・ストーリー ～白銀編～ - DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選 | AtCoder

問題概要:

要素数10の二つの配列P,Qを掛け合わせて10*10=100マスのマス目を埋めたい。マス目のうちどこにもNを超える数が含まれないとき、P,Qの組み合わせは何通り考えられる？(mod1,000,000,007)

考察

テストケースでは2の出力結果が2047=211-1なので、(配列Pのi番目の要素iに1~Nの全ての数字が入る可能性があり、要素数は10なのでN10通り、Qでも同じことが言えるが、Qは全て1でないと掛け合わせたときにNを超える数が現れるので、N10+N10-1(全ての要素が1の時は重複する))
という嘘解法を生やしがちです。（私もはまりました）この解法では、「Pに1以外の何かしらの数が入っているときQは必ずすべての要素が1である。(P,Qが逆でも同じ)」という仮定をもとに成り立っていますが、これはN=2,3の時のみ有効です。N=4のときはN=2*2と置けますが、P、Q両方の要素に2が含まれていても掛け合わせたら4で大丈夫ですよね。（よりにもよってテストケースが2,3なのでまた難易度上がります）

ここで、(Pの要素の最大値)×(Qの要素の最大値)≤Nという関係が成り立てばよいことに気付きます。（素因数分解とか考えてはいけません）
ここで決め打ちを考えます。Pの要素の最大値がk以下のとき、組み合わせは上の嘘解法と同様に考えるとk10通り、Pの要素の最大値がk-1以下の時も(k-1)10通りなので、よってPの最大値がkとなる組み合わせはk10-(k-1)10通りです。
よってPの最大値を決め打ちして、(Pの最大値)×(Qの最大値)≤NとなるQの最大値を試せばよいです。Pの最大値がkとなったとき、Pの組み合わせはk10-(k-1)10通り、このときQは最大値が(N/k)以下でなくてはならないので(N/k)10通り、これらを掛け合わせて、求める組み合わせは{k10-(k-1)10}×(N/k)10通り。kを1からNまでで全て求めてその合計が求める値です。

コード

#include<iostream>
using namespace std;

const int MOD=1000000007;

int fun(long long n){//nの10乗を求める
    long long res=n;
    for(int i=1; i<10; i++){
        res*=n;
        res%=MOD;
    }
    return res;
}
 
int main(){
    
    int N;
    long long ans=0;
    cin>>N;
    for(int k=1; k<=N; k++){
        //{k^10-(k-1)^10}×(N/k)^10通りを全探索
        long long p=(fun(k)-fun(k-1)+MOD)%MOD;
        long long q=fun(N/k);
        ans+=p*q;
        ans%=MOD;
    }
    cout<<ans<<endl;
    
    return 0;
}

べき乗をpow関数で作るとオーバーフローとかいろいろ起こるので関数で計算しました。MODを一桁間違えて30分ぐらい悩んでました

D:チップ・ストーリー　～黄金編～

D: チップ・ストーリー ～黄金編～ - DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選 | AtCoder

考察

JOI予選終わった後にでも考えます（すみません）

感想

真面目に企業コンに取り組んだのは初めてだったのですが200点問題まで解けたので個人的にはまずまずの結果でした。 DPやデータ構造というより数学的な考察の比重が大きかったと思います。（Dはまだですが） 来年は受験なのでこれをやっている余裕はなさそうですが再来年は予選突破したいですね。