プログラミング学習記録【24日目】/ AtCoder Beginners Selection -3

ABC083B Some Sums

問題文
1以上N以下の整数のうち、10進法での各桁の和がA以上B以下であるものの総和を求めてください。
入力は以下の形式で標準入力から与えられる。
N A B

まずはコードの外形を考えていく。
1-Nまでの数字を考えていくから引き続きrepを用いる。前回同様、使いたい数字はNも含まれ、i=0は計算を行わなくて良いので、repではなくiを1追加する。構文内でiをいじってしまうと正しくループが機能しないので、別の変数に入れてから処理を行う。

int main()
{
 int N, A, B;
 cin >> N >> A >> B;
 int count = 0;
 rep(i, N)
 {
   int x = i + 1;

で、このxの各桁の合計がA以上B以下なら良い。N<10^4だったので、パワープレイしようとしていたのだが、これが勘違いだった。勘違いしていた内容は、%の処理とか、int型であってdouble型ではない意味など。要するに、

int y;
y  = x/1000 + x/100 + x/10 +x%10;

とか、

y  = x%1000 + x%100 + x%10 +x%10;

で、出力できると思ってしまったのだ。
あとになって考えてみたら、なぜこれで良いと思ったのかわからないが、これで処理を続けていて結果が合っていたのは当然2桁の数字までである。
それでおかしいと思って、改めて%の使い方について調べて、自分の勘違いに気づいた。
1桁ずつ足すなら、

y = x%10 + x/10%10 + x/100%10 + x/1000%10;

で、これはすごく記述がかっこ悪いので、whileを使う。

while (x > 0)
   {
     y += x % 10;
     x /= 10;
   }

コードの全形はこちら。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main()
{
 int N, A, B;
 cin >> N >> A >> B;
 int count = 0;
 rep(i, N)
 {
   int x = i + 1;
   int y = 0;
   while (x > 0)
   {
     y += x % 10;
     x /= 10;
   }
   if (y >= A && y <= B)
     count = count + i + 1;
 }
 cout << count << endl;
}

ABC088B Card Game for Two

問題文
N枚のカードがある。i枚目のカードにはaiという数字が書いてある。AliceとBobが交互に一枚ずつカードを取っていく。すべてのカードが取り終わったとき、取ったカードの数の合計がその人の得点になる。2人共得点が最大になるように最適な戦略をとった場合、AliceはBobより何点多く得点を取れるか求めよ。

最適な戦略は、大きい得点から取っていけば良い。
ループを組むなら、iが偶数ならAlice、iが奇数ならBobが得点するようにコードを組めば良い。
大きい順にカードを取っていきたいので、そういう操作が得意な配列で数を受け取り、それを小さい順に並び替えるsort,逆順にするreverseで大きい順に並び替える。

 int N;
 cin >> N;
 vector<int> ver(N);
 rep(i, N)
         cin >> ver.at(i);
 sort(ver.begin(), ver.end());
 reverse(ver.begin(), ver.end());

あとは偶数のときAliceの、奇数のときBobの得点となればいいので、そのとおりにコードを組む。コードの全形は以下の通り。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main()
{
 int N;
 cin >> N;
 vector<int> ver(N);
 rep(i, N)
         cin >>
     ver.at(i);
 sort(ver.begin(), ver.end());
 reverse(ver.begin(), ver.end());
 int A = 0, B = 0;
 rep(i, N)
 {
   if (i % 2 == 0)
     A += ver.at(i);
   else
     B += ver.at(i);
 }
 cout << A - B << endl;
}

ABC085B - Kagami Mochi

問題文
X段重ねの鏡餅とは、X枚の円形の餅を立てに積み重ねたもので、どの餅もその真下の持ち寄り直径が小さい。
ダックスフンドのルンルンはN枚餅を持っていて、i枚目の餅の直径はdi[cm]だ。
この餅で何段の鏡餅を作ることができるか。

餅の直径が同じものを除いて、残った餅が何枚あるかを出力すればいい。
これもそういう操作が得意な配列で受け取る。

 int N;
 cin >> N;
 vector<int> ver(N);
 rep(i, N)
     cin >>ver.at(i);
 sort(ver.begin(), ver.end());

ループ文は、ver.at(i) が ver.at(i + 1)と等しいときにカウンタを1進め、このカウンタをNから引けば最終的な餅の枚数がわかる。

rep(i, N)
 {
   if (ver.at(i) == ver.at(i + 1))
     count++;
 }

このままだと、ずっとエラーを吐いてしまう。
いろいろ考えた結果、ループがNまでだと、配列が1つ足りないことに気がついたので、ループ条件をN-1とする。最終的なコード外形は以下の通り。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main()
{
 int N;
 cin >> N;
 vector<int> ver(N);
 rep(i, N)
         cin >>
     ver.at(i);
 sort(ver.begin(), ver.end());
 int count = 0;
 rep(i, N - 1)
 {
   if (ver.at(i) == ver.at(i + 1))
     count++;
 }
 cout << N - count << endl;
}

これでAtCoder Beginners Selection のB問題は片付いた。次回はついにC問題に手を付けてみる。