AtCoder Beginner Contest 105
AtCoder Beginner Contest 105 - AtCoder
A - AtCoder Crackers
考察
個のものを人で分けるときの個数の差の最小値。ちょうど割り切れれば0、割り切れなければ1…?(証明せず)
コード
int main(){ ll n,k; cin >> n >> k; if(n%k==0){ cout << 0 << endl; }else{ cout << 1<< endl; } return 0; }
B - Cakes and Donuts
考察
をみたす0以上の整数の組が存在するかどうかの判定。が大きければ4と7が互いに素であることを利用してうにゃうにゃしそうだが、今回はが小さいので考えうるの範囲で全探索。
コード
int main(){ ll n; cin >> n; bool ans = false; REP(i,26){ REP(j,16){ if(i*4+j*7==n){ ans = true; } } } if(ans){ cout << "Yes" << endl; }else{ cout << "No" << endl; } return 0; }
C - Base -2 Number
考察
与えられた整数の進数表現を求める。進数表現の桁をどのように求めればよいかを考える。分かれ道は上の桁から決めていくか、下の桁から決めていくかのいずれかだが、少し考えると下の桁からのほうが容易であることがわかる。例えば、一番下の位は2で割り切れるかどうかで決まり、下か2番目の位は一番下の位を差し引いたあと、4で割り切れるかどうかで決まる。これを繰り返していけば、順次桁が求まりそうだ。
コード
int main(){ ll n; cin >> n; str s; ll pw = 1; if(n==0){ cout << 0 << endl; return 0; } ll power = 2; while(n!=0){ if(n%power==0){ s += '0'; }else{ s += '1'; n -= (power/2)*((pw%2)?1:-1); } pw++; power *= 2; //cout << n << endl; } reverse(s.begin(),s.end()); cout << s << endl; return 0; }
疑問
最初にシフトビットを利用したコードを書いたが、TLEになってしまった。なぜこうなったのかが未だに不明(コメントください)。
D - Candy Distribution
考察
サイズの数列に対して、がの倍数となるような整数の組の個数を求める。数列の要素の和という時点で、累積和を使いそうな予感がする。
によって数列を定めると、結局で割ったあまりが等しいような2つの要素を取ってくればはの倍数となる。したがって、の要素をで割ったあまりによって分類し、で割って余るの個数をとしたとき、2つの数の選び方を考えての和を取ればよい。
ただし、がまで大きくなりうるのでを配列として保持することができない。そこで連想配列を使用してオーダを抑えればよさそう。
コード
const ll max_n = 100000; ll a[max_n]; ll sum[max_n+1]; int main(){ ll n,m; cin >> n >> m; map<ll,ll> count; fill(sum,sum+n+1,0); count[0]++; REP(i,n){ cin >> a[i]; sum[i+1] += sum[i]+a[i]; count[sum[i+1]%m]++; } ll ans = 0; for(pair<ll,ll> cnt :count){ ans += cnt.second*(cnt.second-1)/2; } cout << ans << endl; return 0; }
雑感
C問題に結構苦戦させられましたが、なんとか時間内に全完できました。不具合でUnratedになってしまったのが残念(笑)。
あと、以前の記事
nexusuica.hatenablog.jp
に掲載していた、蟻本初級編の部分をほぼ終わらせることができました。その結果だいぶ考え方になれることができたように思います。中級編の方も進めていきたいです。