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の証明が欲しかったところなので、かなり参考になった
次回は競技プログラミングで必須の全探索をやってみる予定
