DDCC(DISCO presents ディスカバリーチャンネル コードコンテスト2019)予選
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はまだですが） 来年は受験なのでこれをやっている余裕はなさそうですが再来年は予選突破したいですね。
ARC061-C たくさんの数式
問題
考察
|S|≤10なので全ての文字列の隙間に'+'を入れるか、いれないかのO(2^n)通り試せば間に合う。
O(2^n)通りを試す方法は再帰、bit全探索の2つあるが、bit全探索の方がforループでシンプルに書けるのでbitで書く方が良いだろう。(という個人的な感想)
long long型となるのでオーバーフローしないよう気を付けたい。
(特に
コード
#include<iostream> #include<string> #include<numeric> using namespace std; string S; long long a[11]; int main(){ cin>>S; int si=S.size(); long long sum=0; //bit全探索 for(long long bit=0; bit<(1<<(si-1)); bit++){ //a[]の初期化 for(int i=0; i<si; i++)a[i]=S[i]-'0'; //どこに'+'を入れるか for(int i=0; i<si-1; i++){ if(bit & (1<<i)){ //'+'をiとi+1の間に入れない a[i+1]=a[i]*10+a[i+1]; a[i]=0; } } sum+=accumulate(a,a+si,0LL); } cout<<sum<<endl; return 0; }
ARC060-C 高橋君とカード
問題
考察
N枚のカードの平均値をちょうどAにしたい
まず、それぞれのカードについて選ぶ場合、選ばない場合を全て探索してそれらの平均がAと一致するかを判定することを考える。これはO(2^n)なのでN≤16の部分点は取れる。(①)
N≤50を満たす解を考える。 組み合わせの総数を求める問題で全探索が使えないならDPを使うとうまくいくことが多いのでDPを考える。
dp[i][j][k]:i番目までの数まででj個選んだときの総数がkとなる組み合わせの総数
dp漸化式:
dp[i+1][j][k]=dp[i][j-1][k-x[i]]+dp[i][j][k]
dp初期条件:dp[0][0][0]=1;
求める値:dp[N][N][A*N]
計算量はO(N^3 *A)これで満点を取ることができる。(②)
(選んだカードの(x[i]-A)の合計が0になる組み合わせをdpする方法でO(N2*A)で解けるようです。)
コード①(200点)
#include<iostream> using namespace std; int N,A; int x[60]; int main(){ cin>>N>>A; for(int i=0; i<N; i++)cin>>x[i]; //全てのxiについて選ぶ選ばないを判定 //bit全探索 long long ans=0; for(long long bit=0; bit<(1<<N); bit++){ int sum=0,cnt=0; for(long long i=0; i<N; i++){ if(bit & (1<<i)){ sum+=x[i]; cnt++; } } double a=(double)sum/(double)cnt; if(a==A)ans++; } cout<<ans<<endl; return 0; }
コード②(満点)
#include<iostream> using namespace std; int N,A; int x[60]; long long dp[60][60][3600]={}; int main(){ cin>>N>>A; for(int i=0; i<N; i++)cin>>x[i]; for(int i=0; i<=N; i++)dp[i][0][0]=1; for(int i=0; i<N; i++){ for(int j=1; j<=N; j++){ for(int k=0; k<=N*A; k++){ if(k-x[i]>=0){ dp[i+1][j][k]+=dp[i][j-1][k-x[i]]; } dp[i+1][j][k]+=dp[i][j][k]; } } } long long ans=0; for(int j=1; j<=N; j++){ ans+=dp[N][j][j*A]; } cout<<ans<<endl; return 0; }
ARC058-D アンバランス
問題
考察
アンバランスである条件 「tの長さが2以上」 「tの中の文字のうち過半数が同じ文字("noon"のように、半数だけではアンバランスではない)」
これを満たす文字がsの中に存在するか判定する。
"needed"では、"eede"がアンバランスな文字列
愚直に全探索を考えると、文字列sの部分文字列を全てアンバランスか試すことが思いつく。sの長さをnとすると、sには長さ2以上の部分文字列がn(n-1)/2個存在するので、それらで作られた文字列全てについてアルファベットの出現回数を数えることでO(n3)となりn≦100の部分点は解ける。(①)
しかし|s|≦105なのでもっと効率的な解き方をしなければならない。アンバランスな文字列を考えると、必ず、"XX"又は"XYX"という配置が含まれていることがわかる。
"XX"又は"XYX"という文字列がある段階でアンバランスな文字列が含まれると判断できる。よって文字列を始めから追っていって、直近の2文字を覚えておき、次に得られた文字がその2文字のどちらかに一致する場合(直近2文字を'X','Y'とすると、"XYX"又は"XYY"となる時)アンバランスであると判断できる。これを実装すれば満点解答を得られる。(②)
(メモ化するのでDP?線形探索?思いつきさえすれば実装すること自体は①よりも簡単だと思います)
コード①(部分点)
#include<iostream> #include<string> #include<algorithm> using namespace std; string s; int al[30];//各アルファベットの出現回数をカウントする int main(){ cin>>s; int si=s.size(); for(int i=0; i<si; i++){//部分文字列の初め for(int j=i+1; j<si; j++){//部分文字列の終わり //i+1と置くことで部分文字列の長さは2以上になる for(int j=0; j<30; j++)al[j]=0;//アルファベットの初期化 //文字列の探索(iから始まってjで終わる) for(int k=i; k<=j; k++){ //sのj番目の文字に対応するアルファベットをカウントする al[s[k]-'a']++; } //最頻値を得たいので降順にソートする sort(al,al+30,greater<int>()); if(al[0]>(j-i+1)/2){ cout<<i+1<<" "<<j+1<<endl;//1-indexedで答える return 0; } } } cout<<"-1 -1"<<endl; return 0; }
コード②(満点)
#include<iostream> #include<string> using namespace std; string s; int main(){ cin>>s; int si=s.size(); char a=s[0]; char b=s[1]; if(a==b){ cout<<"1 2"<<endl; return 0; } for(int i=2; i<s.size(); i++){ char c=s[i]; if(a==c){ cout<<i-1<<" "<<i+1<<endl; return 0; }else if(b==c){ cout<<i<<" "<<i+1<<endl; return 0; } a=b; b=c; } cout<<"-1 -1"<<endl; return 0; }
ARC058-C こだわり者いろはちゃん
問題
C - こだわり者いろはちゃん / Iroha's Obsession
考察
10進法表記で嫌いな数字が出ないようにしたい。N<10000なのでforループで実装できる？
ここで、Nが制約を満たすときの支払う金額の最大値を考える。N=9999,D[]={0,1,2,3,4,5,6,7,9}のとき、支払う金額は88888となり(恐らく)これが最悪の場合である。よって支払う金額はせいぜいO(10N)(100,000通り)未満。なのでNからスタートして条件を満たす数をforループで探せば間に合う。
for(int i=N; ; i++)として、iが条件を満たすかどうか判定する。これは10で割った余りを求めて10で割ってを繰り返せばよい。一桁一桁を嫌いな数字かどうか照らし合わせてlogN通り。上のforループと組み合わせてO(NlogN)程度で間に合う。
コード
#include<iostream> using namespace std; int N,K; bool ng[11]; int main(){ cin>>N>>K; for(int i=0; i<K; i++){ int t; cin>>t; ng[t]=true; } for(int i=N; ; i++){ int a=i; while(1){ int d=a%10; if(ng[d]) break; a/=10; if(a==0){ cout<<i<<endl; return 0; } } } return 0; }
