自力で解けなかった 問題 n人の候補者がいる選挙が行われ、i人目の得票率は四捨五入するとp[i]パーセントだったらしい しかしこの情報が嘘である可能性がある この得票率になるような投票人数と投票の仕方が存在する場合は投票人数の最小値を、存在しない場…

問題 L xor L+1 xor L+2 xor ... xor r を求めよ1 解法 実験すると↓のコードのような法則があることがわかる class EllysXors { public: ll x(ll n) { if (n%4==0) return n; if (n%4==1) return 1; if (n%4==2) return n+1; return 0; } ll getXor(ll l, ll…

問題 x*yのグリッド上の3点a,b,cの選び方で、(ab間の距離)+(bc間の距離)+(ca間の距離)がmn以上mx以下になるようなものは何通りあるか ただしa,b,cは全てx座標もy座標も異なる必要がある3 1 解法 (ab間の距離)+(bc間の距離)+(ca間の距離) ってのは、abcを内側…

問題 n匹のアリがいて、i匹目の座標は (x[i], y[i]) である i匹目のアリはd[i]方向に毎秒1だけ進み、2匹以上のアリがどこかでぶつかるとそれらは全て消える いつまでも消えないアリは何匹いるか求めよ1 |x[i], y[i]| 解法 座標を2倍すればぶつかる場所が必ず…

問題 長さn+1で各要素が自然数であるような数列aと長さnの文字列opがあった opの各文字は '+' か '-' である op[i] = '+' のとき) b[i] = a[i]+a[i+1] op[i] = '-' のとき) b[i] = a[i]-a[i+1] という風にして作った長さnの数列bとopが与えられる 元の数列a…

問題 石を無限に持っていて、9001個以上の石を箱に詰めたい n個の箱があり、i番目の箱にはx[i]個以上y[i]個以下の石を詰めることができる 詰める石の個数が何通りあり得るか求めよ1 1 解法 2^15通り全列挙して使う箱の組み合わせを全部試す 使うと決めた箱た…

問題 自然数a, b, xが与えられる 任意の(p,q)に対して pa+qb = rx+sy を満たす(r,s)が存在するような(x,y)の組の個数を求めよ (ただしp, q, r, sは非負整数でyは自然数) 答えが無限に存在する場合は-1を返せ1 a ≠ b 解法 aもbもxの倍数の場合、yの値によらず…