Atcoder
ABC344 C
3重ループでも10^6なので素朴にやればいいのでは
と思ったけどQが10^5なのでだめ
いや普通に10^6の配列からlogNで見つけられるから大丈夫か
=> https://atcoder.jp/contests/abc344/submissions/51641147
ABC345 C
問題を言い換えるとiとjの選び方の問題になる
iとjはSから2個順番を気にせずに選ぶのでSの長さをLとすると L*(L-1)/2 通りの選び方がある
ただしiとjに同じ文字を選ぶ場合を引き算しないといけない
そしてiとjが同じ時は1通りだけプラスしないといけない
S=aabbで(i,j)=(a,a)のときにaabbになるがこれを+1しないといけない
この問題もintで計算しているところがあってWAになっていた…
=> https://atcoder.jp/contests/abc345/submissions/51639228
ABC346 C
はじめ愚直に配列を並べて調べようとしていた
そんな事する必要なくて現れるものから引き算すればいいと気付いた
Kまでの総和は 1+2+...+K なので (1+K)/2 * K
Kが最大 2*10^9 なので 10^18 を格納できる必要がある
ここまで気付いて uint64_t にしていたけど桁溢れしている
Kを保存するときにintにしていて暗黙的な型変換で桁溢れしていた…
あとはAに現れている数の総和を求めて引き算すればいい
ただし、同じ数の場合は重複して引き算してはいけない
=> https://atcoder.jp/contests/abc346/submissions/51631932