文系ギャルが0から始める競技プログラミング#10
Intro
この記事は不定期連載です。
↓最初の一本はこちら↓
文系ギャルが0から始める競技プログラミング#0
↓直前の記事はこちら↓
文系ギャルが0から始める競技プログラミング#9
・ABC087B
引き続きAtCoder Beginners Selectionの問題を解いていきます。
このセレクション、数学力がいらない問題が多い気がしています。
助かる〜〜〜〜〜。(さらなる天才ムーブにむけて修行します)
問題文
あなたは、500円玉をA枚、100円玉をB枚、50円玉をC枚持っています。
これらの硬貨の中から何枚かを選び、合計金額をちょうどX円にする方法は何通りありますか。
同じ種類の硬貨どうしは区別できません。
2通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。
制約
0≤A,B,C≤50
A+B+C≥1
50≤X≤20,000
A,B,Cは整数である
Xは50の倍数である
入力
入力は以下の形式で標準入力から与えられる。
A
B
C
X
出力
硬貨を選ぶ方法の個数を出力せよ。
― ABC087B - Coins
2万分硬貨持ってたら重くて死ぬっしょ!
と、巷で流行りのミニ財布を使っているのでコインレス生活をしてると思います。
それはさておき、ゴールを整理します。
for文でパワープレイするしか思いつきません。
もっといい方法があれば、Twitterやコメントで教えてください!
(DMも全開放しています。先輩リスト更新中です!!)
#include <iostream>
using namespace std;
int main()
{
int A,B,C,X;
cin >> A >> B >> C >> X;
int a,b,c;
int ans = 0;
for(a=0;a<=A;++a){
for(b=0;b<=B;++b){
for(c=0;c<=C;++c){
if(X == (a*500)+(b*100)+(c*50)){
ans++;
}
}
}
}
cout << ans << endl;
return 0;
}
X円になる組み合わせがあったら、ansを足す式で無事優勝。
無きゃ無いでいいのですもんね。これぞ天才です。
次行ってみます。
・ABC083B
問題文
1以上N以下の整数のうち、
10進法での各桁の和がA以上B以下であるものの総和を求めてください。
制約
1≤N≤10^4
1≤A≤B≤36
入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N A B
出力
1以上N以下の整数のうち、
10進法での各桁の和がA以上B以下であるものの総和を出力せよ。
― ABC083B - Some Sums
和はわかるぞーーーーー!(天才)
Nが10^4らしいので、10000個の配列にそれぞれぶっこんでいきます。
それとは別に、それぞれの和を入れるための箱wa[N]を用意します。
int N,A,B;
cin >> N >> A >> B;
int x[10001]={};
int wa[N];
xには1,2,3,4,5,6...と普通に並べた整数、
waにはそれぞれの桁を足した整数を入れていきます。
そのためには、各桁を分解しないといけません。
intの小数点切り捨てを使った分解を#8で習得したのを思い出しました!
桁が多くなっても余りを使って対応できそうです。
(夫からの天の声で思い出しました)
int i = 1;
while(i<=N){
x[i]=i;
int k = i;
wa[i] = (k / 10000) + (k / 1000 % 10) + (k / 100 % 10) + (k / 10 % 10) + (k % 10);
i++;
ここまで書いて、ゴールを整理します。
A≦waと、wa≦Bを満たすxを合計して出力するのがゴールです。
答え用ボックスansに、条件を満たすwaのときにx[i]を入れていけば優勝?
int ans = 0;
for(i=1;i<=N;i++){
if(A<=wa[i] && wa[i]<=B){
ans = ans+x[i];
}
}
cout << ans << endl;
無事優勝しました!!!!(天才ムーブ)
#include <iostream>
using namespace std;
int main()
{
int N,A,B;
cin >> N >> A >> B;
int x[10001]={};
int wa[N];
x[0] = 0;
int i = 1;
while(i<=N){
x[i]=i;
int k = i;
wa[i] = (k / 10000) + (k / 1000 % 10) + (k / 100 % 10) + (k / 10 % 10) + (k % 10);
i++;
}
int ans = 0;
for(i=1;i<=N;i++){
if(A<=wa[i] && wa[i]<=B){
ans = ans+x[i];
}
}
cout << ans << endl;
return 0;
}
楽しいーーーーー!
こんな楽しい趣味が生まれてハッピー!
飽き性なのでいつ飽きるかと思ってたんですが、
記事書くモチベも込みで続いてます。
記事を読んでくれる先輩方に感謝です。
感想・アドバイスなどTwitterやコメントでお待ちしています!
いい加減そろそろコンテスト出たいー!
Outro
#11に続く!(不定期連載です。)
これは成功と挫折を繰り返し、
タピオカ片手に難問を解く、
ギャルプログラマが生まれるまでの物語である…。