文系ギャルが0から始める競技プログラミング#5

Intro

この記事は不定期連載です。
↓最初の一本はこちら↓
文系ギャルが0から始める競技プログラミング#0

↓直前の記事はこちら↓
文系ギャルが0から始める競技プログラミング#4

・今日の一問

今日はABC120のB問題に手を付けていこうと思います。
初期の初期に手を付けた問題なんですが解けずで放置していて…
そろそろいけるかな？と行ってみたいと思います！

まずそもそもとして、「問題文を理解できるかどうか」がわたしの場合問題の多くを占めている気がします。
なんか数列っぽいの言われてもよくわからないし…と考えたときに、
この問題は問題文がとてもシンプルでした。

問題文
正整数A,Bが与えられます。
AもBも割り切る正整数のうち、
K番目に大きいものを求めてください。
なお、与えられる入力では、AもBも割り切る正整数のうち
K番目に大きいものが存在することが保証されます。

制約
入力は全て整数である。
1≤A,B≤100
Aも Bも割り切る正整数のうち、K番目に大きいものが存在する。
K≥1

入力
入力は以下の形式で標準入力から与えられる。
A B K

出力
AもBも割り切る正整数のうち、K番目に大きいものを出力せよ。
― B - K-th Common Divisor

うん、これならなんとなく分かる気がする。
まず1≤A,B≤100に着目します。
１から100までということは、求めている答えもその間に入るだろうということで、
100から順番に割っていってイイ感じのところで止めるって戦法を思いつきます。

#include <iostream>
using namespace std;
int main()
{
   int A,B,K;
   cin >> A >> B >> K;
   
   int n = 100;

100から用意して、条件を考えます。

while(K>0){
       if(A%n == 0 && B%n == 0){
           --K;
   
   }
       --n;
   }

イイ感じの数を見つけたらKを減らして、時が来たらループを抜けます。

   cout << n << endl;
   
       return 0;

そして出力して終わり！！！！！！！
と思ったら。
想定している答えより1足りないのです。。。
なんでだろ？と思ったら、
イイ感じになったあと、nを減らしてからループ抜けてんじゃん！
ということに気づいてしまいました。これは間違いなく天才。
というわけで、最後に1を足して優勝です。

#include <iostream>
using namespace std;
int main()
{
   int A,B,K;
   cin >> A >> B >> K;
   
   int n = 100;
   
   while(K>0){
       if(A%n == 0 && B%n == 0){
           --K;
   
   }
       --n;
   }
   
   cout << n+1 << endl;
   
       return 0;
}

天才なのでACです。優勝！
またB問題が解けました。やったね！
やっぱり問題文が理解できるかどうかがポイントのようです。

Outro

面白そうな本を買ったので、次にでも紹介します。
#6に続く！(不定期連載です。)

これは成功と挫折を繰り返し、
タピオカ片手に難問を解く、
ギャルプログラマが生まれるまでの物語である…。