今日も独りで立ち話

ポンコツ博士課程の院生が思ったことをそのまま書くブログ

MENU

Atcoder勉強日記ー倍数判定

APG4bを一通り目を通し終わったので

AtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~ - Qiita

こちらの記事を参考に問題を解いていくことにした
(もちろんAPG4bであいまいなところも多いので、2週目にいくつもり)

 

今回、解いたのは4問

ABC 086 A - Product
ABC 064 A - RGB Cards 
ABC 088 A - Infinite Coins 
ABC 157 A - Duplex Printing 

 

 

正直、これらは特に苦労もせず解けたので、ちょっとプログラミングから離れていたので、心配だったけど一安心

 

ちなみに半年前のABC 088 A - Infinite Coins のコードはこれで

struct #include <bits/stdc++.h>
using namespace std;

int main() {
int N, A;
cin >> N >> A;
if(N <= A){


cout << "Yes" << endl;
}
else {
int x;
x = N % 500;
if(x <= A){
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
}

 

今回書いたコードがこれ


#include<iostream>
using namespace std;

int main(){
int N, A =0;
cin >> N >> A;
if(N <= A){
cout << "Yes" << endl;
}
else{
if(N % 500 <= A){
cout << "Yes" << endl;
}
else{
cout << "No" << endl;
}
}
}

 

何気ない簡単なコードだけど、前よりはすっきりとしたコードになっていて成長を感じる(自画自賛)

 

今回は切り上げが

(a + b - 1) / b

で表せる意味がちょっとよく理解できていないので、それについての備忘録

 

int型で小数点以下を切り捨てることで処理してるんだろう、というのは感じていたんだけど、この表記になる理屈はよくわかってない

 

単純に考えれば

2で割り切れるなら

a/b

2で割り切れないなら

a/b + 1

 

になるはず

 

(a + b - 1) / bも変形すると、a/b + 1 - 1/bになる

a = 10 b = 2なら5になるはずで、上記の式にいれると 1 - 1/bの項が1未満となりint型では無視される

 

a = 11 b = 2の場合は

5.5 + 1 -1/2になり、計算結果は6となって正しい値を出している

 

割り切れる場合は

1 - 1/b < 0になるとまずいのだけど、bが整数である場合は必ず1/b < 1になるので大丈夫そう

 

割り切れない場合は

a/b + 1の小数部分が1/bより大きくないといけないんだけど、その証明がわからなかった

 

色々調べると、それに関してまとめてある記事を見つけたので引用

C++でa/bの除算の切り上げが(a+(b-1))/bでできる理由 | Now Loading...

 

 

1)a<bの場合

 a<bなので、計算結果は0<a/b<1になります。また、欲しい答えは1になります。この場合、aは整数型なので、1以上の値をとります。従って、a/b≧1/bとなります。従って、(a/b)+1-(1/b)≧1となるため、正しく切り上げられることがわかります。

2)a=bの場合

 (a/b)+1-(1/b)=2-(1/b)となります。b=1の場合にはa=1であり、欲しい計算結果は1です。b>1の場合には0<1/b<1であるため、1<(a/b)+1-(1/b)<2となるため、計算結果として1が得られることがわかります。

3)a>bの場合

 a>bなのでc、kを整数(cはb未満の整数)としてa=kb+cで表せます。よって、(a/b)+1-(1/b)=((kb+c)/b)+1-(1/b)=k+1+(c/b)-(1/b)となります。 ここで、kがa/bの整数部分、c/bがa/bの小数部分になります。cは整数であるため、1以上の値をとります。従って、a/bの小数部分は1/b以上の値をとります。

 なるほど、超わかりやすい

 

割り切れる、割り切れないではなくて

計算結果がどの範囲に収まっているかを示すだけでいいんだね

(int型は小数部分が切り捨てられるので)

うまいこと切り捨てられるのを利用している感じがする

 

特にa>bの証明が欲しかったところなので、かなり参考になった

 

次回は競技プログラミングで必須の全探索をやってみる予定