A – 世界のFizzBuzz
A問題にしては難しい…と思い、以下のコードを書いたのですが
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
cin>>N;
if(N%3==0) {
cout<<"YES"<<endl;
return 0;
}
while(N!=0){
if(N%10==3) {
cout<<"YES"<<endl;
return 0;
}
N/=10;
}
cout<<"NO"<<endl;
}
制約を見ると、1桁の数字しか入力されません。
3,6,9(%3==0)がYESとなる数字なのでif文1個で問題なしですね。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int N;
cin>>N;
if(N%3==0) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
B – トリボナッチ数列
DPの模範的な問題ですね。
a(8)を計算する場合、
a(8) =a(7)+a(6)+a(5) =a(6)+a(5)+a(4)+a(5)+a(4)+a(3)+a(4)+a(3)+a(2) =a(5)+a(4)+a(3)+.....
みたいに、a(1)、a(2)、a(3)になるまで細かくしていかないといけません。計算量も大幅にかかってしまいます。
ただ、a(4)から順に計算することで簡単に求めることができます。
a(4)=a(1)+a(2)+a(3)=0+0+1=1 a(5)=a(2)+a(3)+a(4)=0+1+1=2 ※a(4)は計算結果を利用 a(6)=a(3)+a(4)+a(5)=1+1+2=4 ※a(4),a(5)は計算結果を利用 a(7)=a(4)+a(5)+a(6)=1+2+4=7 ※a(4),a(5),a(6)は計算結果を利用 a(8)=a(5)+a(6)+a(7)=2+4+7=13 ※a(5),a(6),a(7)は計算結果を利用
と、前回の計算結果を用いて簡単に計算できます。
計算量もO(N)となり、非常に早く計算できるようになります。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
int mod=10007;
cin>>n;
int dp[n+3];
dp[1]=0;
dp[2]=0;
dp[3]=1;
for(int i=4;i<=n;i++){
dp[i]=(dp[i-1]+dp[i-2]+dp[i-3]);
dp[i]%=mod;
}
cout<<dp[n]<<endl;
}
C – スフィンクスのなぞなぞ
10点解答
単純に、大人、老人、赤ちゃんのかずを全通り試すことで解くことができます。
計算量はO(N^3)ですが、10点の制約には間に合います。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,M;
cin>>N>>M;
for(int i=0;i<=N;i++){
for(int j=0;j<=N;j++){
for(int k=0;k<=N;k++){
if(i+j+k==N&&2*i+3*j+4*k==M){
cout<<i<<" "<<j<<" "<<k<<endl;
return 0;
}
}
}
}
cout<<"-1 -1 -1"<<endl;
}
30点解答
大人の数をA、老人の数をB、赤ちゃんの数をCとしたとき
A+B+C=N 2A+3B+4C=M
という連立方定式を解くこととなります。
この時、Nの式を
C=N-A-B
とし、Mの式に代入すると
2A+3B+4N-4A-4B=M -2A-B=M-4N 2A+B=4N-M
となり、未確定の文字を2つに減らすことができました。
あとは、この2つを全探索することで計算量がO(N^2)となり、30点が得られます。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,M;
cin>>N>>M;
for(int i=0;i<=N;i++){
for(int j=0;j<=N-i;j++){
int n=2*i+j;
int m=4*N-M;
if(n==m){
cout<<i<<" "<<j<<" "<<N-i-j<<endl;
return 0;
}
}
}
cout<<"-1 -1 -1"<<endl;
}
※C++だと1489msで100点になりました＞＜
100点解答
初めのfor文でAが決まった場合、30点解答で計算した式を
B=4N-M-2A
とすると、右の文字は全て確定しているためBが取りうる値は1通りに決まります。
このときのBの値が題意通りである(B>=0&&B<=N-A)なら、その時のA,Bが答えであるといえます。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,M;
cin>>N>>M;
for(int i=0;i<=N;i++){
int j=4*N-M-2*i;
if(j>=0&&j<=N-i){
cout<<i<<" "<<j<<" "<<N-i-j<<endl;
return 0;
}
}
cout<<"-1 -1 -1"<<endl;
}
二分探索で…
もっというと、AによるBの変化は-2*iで単調減少します。
そのためAを線形探索せずに二分探索することでさらに計算量を減らすことができます。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,M;
cin>>N>>M;
int r=N+1,l=0;
while(1){
int i=(r+l)/2;
int j=4*N-M-2*i;
if(j>=0&&j<=N-i){
cout<<i<<" "<<j<<" "<<N-i-j<<endl;
return 0;
}
else if(j<0){
if(r==i) break;
r=i;
}
else{
if(l==i) break;
l=i;
}
}
cout<<"-1 -1 -1"<<endl;
}
愚直にすればO(N^3)の問題ですが、
連立方程式を解いて文字を減らす → Nが一つ減る 残り一つは一意に決まる → Nが一つ減る 二分探索する → NがlogNになる
今回の制約では二つ適応し、O(N)かO(NlogN)にすることで100点となります。
この手の問題は、色んな考えからどんどん計算量を削ることができます。
実は…
公式解答を覗きましたが、O(1)で解けるそうです。
というのも、
老人2人 = 3+3 = 6
大人1人、赤ちゃん1人 = 2+4 = 6
と、2人で同じ足の数にすることができます。
ここから、老人は2人以上にする必要がない(大人と赤ちゃんで同等のことができるため)ため、0or1で固定することができます。
よって、100点解答の式は
B=4N-M-2A (0or1)=4N-M-2A 2A=4N-M-(0or1) A=(4N-M-(0or1))/2
となり、0or1の2パターンでAが範囲内かを調べるだけでOKになります。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,M;
cin>>N>>M;
int n=4*N-M;
if(n%2==0&&n/2>=0&&n/2<=N) cout<<n/2<<" 0 "<<N-n/2<<endl;
else if(n--%2==1&&n/2>=0&&n/2+1<=N) cout<<n/2<<" 1 "<<N-n/2-1<<endl;
else cout<<"-1 -1 -1"<<endl;
}
3文字の連立方程式が、ただの1文字方程式になるのすごいですね！
D – トランプ挿入ソート
挿入を、ある値を消して好きな場所に追加すると考えます。
またN回の挿入操作を、N回値を消してから、N個の消した値を好きな位置に追加していくと、消すと追加をまとめて別々にすると考えます。
この時、消したあとの配列が昇順になっていれば適切な位置に追加することで、追加後も昇順になります。
ただし、消したあとの配列が昇順でなければどう追加しても追加後は昇順になりません。
よって、この問題は
削除した後の配列が昇順となるときの、最小の削除数 ->部分列が昇順であるときの最長の長さ
を求める問題と言い換えられます。
この問題は、最長増加部分列（Longest Increase Subsequence）を求める典型問題です。(よくLISなんて呼ばれます。)
探せばアルゴリズムなんて幾らでもあると思いうため、今回は説明をサボります。(Cで疲れた＞＜)
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
cin>>N;
set<int> s;
for(int i=0;i<N;i++){
int c;
cin>>c;
if(s.empty()||*s.rbegin()<c) s.insert(c);
else{
auto it=s.lower_bound(c);
s.erase(it);
s.insert(c);
}
}
cout<<N-s.size()<<endl;
}
コメント