寝るまでが8月3日。
Codeforces #736 Div1D1. Gregor and the Odd Cows (Easy)
まずは面積が整数という条件について。
ある一点からの相対座標 $(x_1, y_1), (x_2, y_2)$ を考えると、これらの値は easy の条件下では全て偶数になるので、$\frac{1}{2}|x_1 y_2 - x_2 y_1|$ は必ず整数かつ偶数になる。
従って本問では無視して構わない。
ピックの定理を知っていますか？私は知らずに敗北しました。
公式の両辺を2倍して、
$$ 2S = 2i + b - 2 $$
今、$ S $ が偶数であり、格子点の数 $ i $ は奇数を想定しているので、辺上にある格子点の数 $ b $ が $b \mod 4 \equiv 0$ になれば良い。
線分 $(x_1, y_1), (x_2, y_2)$ 上にある格子点の数は、端点が両方とも格子点であるから、$\gcd(|x_1 - x_2|, |y_1 - y_2|) + 1$ で表せる。
またこの値を4で割った余りに注目するので、$x, y$ 共に4で割り切れるか否かで4通りの座標の状態としてまとめてしまって問題がない。
(上記の値 - 1)を4で割った余りは、同じ状態同士の時 0、異なる状態同士の時 2 になることに着目すると、「同じ状態から3つ選ぶ」もしくは「同じ状態から2つ異なる状態から1つ選ぶ」という事象を数え上げに帰着され、これは簡単に求めることが出来る。
SWERC2020–2021 K. Unique Activities
本番では、文字列長二分探索+判定パートでローリングハッシュをすることで解いた。
今回は Suffix Array を用いた解法で解いた。
sa[i] から始まる文字列で何文字取れば条件を満たすかはその前後の高さ配列を見て、その $\max$ を見れば良い。
構築 $O(N {\log}^2 N)$ かけているが、元の実装の10分の1ぐらいの実行時間になった。
BAPC2012 D. Digit Sum
問題概要
$[a, b]$ の区間にある整数に登場する桁和の総和を求めよ。
$[28, 31]$ ならば、$2 + 8 + 2 + 9 + 3 + 0 + 3 + 1 = 28$
制約：$0 \leq a \leq b \leq 10^{15}$
どうみても既出だし、ICPCでも頻出っぽい見た目の問題。
$[0, N)$ に対して総和が求められれば良い。
これは下の桁から見て行って再帰関数で実装すると楽に書ける。
// xの桁和を求める ll digit_sum(ll x){ ll res=0; while(x>0){ res+=x%10; x/=10; } return res; } // calc sum[0,n) ll calc(ll n){ if(n < 10){ return n*(n-1)/2; } else{ return calc(n%10) + 45 * (n/10) + (n%10) * digit_sum(n/10) + 10 * calc(n/10); } }
