久々のABC埋めです。(新作ゲームと出張で中々できなかった…)
A – 高橋くんの研修
文字列の長さを比較し、長いほうを出力すればOKです。
注意はC++の場合、文字列A,Bに対してA>Bと比較しても長さの比較になりません。(辞書順の比較になります。)
A.size()等で長さを取得し、その値で比較しましょう。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
string A,B;
cin>>A>>B;
if(A.size()>B.size()) cout<<A<<endl;
else cout<<B<<endl;
}
B – 高橋くんの集計
問題文通り、0以外の総和と個数をカウントする問題です。
入力例2にありますが、小数切り上げに気を付けて下さい。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N;
cin>>N;
int sum=0;
int c=0;
while(N-->0){
int A;
cin>>A;
if(A!=0){
sum+=A;
c++;
}
}
cout<<(sum+c-1)/c<<endl;
}
切り上げは、母数-1を足すことで表現されます。
(sum%c==0の場合、c-1を足しても切り捨てられ値は変わらず、それ以外の場合はc-1を足せばcで割った値が1つ増えるため、切り上げが表現できる)
個人的にはsum/c+(sum%c!=0)みたいな書き方が好きです。
C – 高橋くんのバグ探し
N,Kの最大が5と小さく、5^5=3125通りしかありません。
全パターン確認し、xorが0になるものがあるかを見ればOKです。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int N,K;
int ask[5][5];
bool f=false;
void dfs(int n,int x){
if(n==N){
if(x==0) f=true;
return;
}
for(int i=0;i<K;i++){
dfs(n+1,x^ask[n][i]);
}
}
int main(){
cin>>N>>K;
for(int i=0;i<N;i++){
for(int j=0;j<K;j++){
cin>>ask[i][j];
}
}
dfs(0,0);
if(f) cout<<"Found"<<endl;
else cout<<"Nothing"<<endl;
}
D – 高橋くんの苦悩
見た感じナップサックっぽい問題です。
(D – ナップサック問題 (atcoder.jp) ←こんなのです。)
競プロに出るようなナップサックは動的計画法で解けることが多いです。
今回の問題も個数の最大50、幅の最大10^4とそこまで大きくないので大丈夫そうです。
メモ化再帰と、dpテーブルを更新していく方法の2通りあるのですが、dpテーブルの方で実装してみました。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int W;
int N,K;
cin>>W;
cin>>N>>K;
int A[N],B[N];
for(int i=0;i<N;i++){
cin>>A[i]>>B[i];
}
int dp[K+1][W+1];
for(int i=0;i<=K;i++){
for(int j=0;j<=W;j++){
dp[i][j]=-1;
}
}
dp[0][0]=0;
int ans=0;
for(int i=0;i<N;i++){
for(int j=K-1;j>=0;j--){
for(int k=W-A[i];k>=0;k--){
if(dp[j][k]!=-1){
if(dp[j][k]+B[i]>dp[j+1][k+A[i]]){
dp[j+1][k+A[i]]=dp[j][k]+B[i];
ans=max(ans,dp[j][k]+B[i]);
}
}
}
}
}
cout<<ans<<endl;
}
普通のナップサックと違い個数の制限もありますが、dpテーブルの次数を増やせばOKです。
注意として、次数を増やせば時間、メモリの両方が爆発的に増えることです。
例えば、幅の最大が10^9、重要度の最大が10である場合、dp[個数][重要度の合計]と持ち幅の最小で更新するなど、dpテーブルの持ち方を制約で変える必要があります。
コメント