総合結果
- [Score] 1800 pts
- [Time] 62:48 + 05:00 $\times$ 1 = 67:48
- [Ranking] 469 th [Rated内: 448 th]
- [Performance] 1955
- [Rating] 1837 → 1859 (+12)
各問題ごとの詳細, 提出コード
| Question | Score | Time/Result | Penalty | During Contest | After Contest |
|---|---|---|---|---|---|
| A問題 | 300 pts | 08:28 |
■ (※Imos法のライブラリーは未使用) |
■ | |
| B問題 | 400 pts | 19:54 | 1 Penalty | ■ | ■ |
| C問題 | 500 pts | 28:47 | ■ | ||
| D問題 | 600 pts | 62:48 | ■ | ||
| E問題 | 0 pts | --:-- | |||
| F問題 | 0 pts | --:-- | |||
| Total | 1800 pts | 62:48 | 1 Penalty |
問題ごとの略解
A問題 (300pts, diff: 237) ABC
$a=\alpha$ と固定する. すると, 問題は $bc \leq \left \lfloor \dfrac{K}{\alpha} \right \rfloor$ を満たす正の整数の組 $(b,c)$ は何個か? という小問題に帰着する. この答えを $X_\alpha$ とする.
$V_t$ を $xy=t$ を満たす正の整数の組 $(x,y)$ の個数とする. $x$ を $\beta$ に固定した時, $\beta$ の倍数すべてに $V_t$ に $1$ ずつ寄与することがわかる. よって, $V_\beta, V_{2 \beta}, \dots$ に $1$ 寄与する.
このことから, 実際に $\beta=1, \dots, K$ として, $K$ 以下の $\beta$ の倍数に $1$ ずつ加算させていけば, $t=1, \dots, K$ に対して $V_t$ と求まる.
また, $xy \leq t$ を満たす正の整数の組 $(x,y)$ の組の個数 $W_t$ は $W_t=\sum_{j=1}^t V_j$ で求めることができる.
以上のことから $X_\alpha=W_{\lfloor K/\alpha \rfloor}$ なので, $\alpha=1, \dots, K$ と動かして, 求めるべき答えは
$$\sum_{\alpha=1}^K X_\alpha=\sum_{\alpha=1}^K W_{\lfloor K/\alpha \rfloor} $$
となる.
計算量は $V_1, \dots, V_K$ を求めるのに
$$O \left(\dfrac{K}{1}+\dfrac{K}{2}+\dots+\dfrac{K}{K} \right)=O(K \log K)$$
かかり1, $W_t$ を求めるのには累積和で $O(K)$, 最終解答を求めるのに $O(K)$ かかり, 全体では $O(K \log K)$ となる.
なお, 2重の ${\tt for}$ 文を回すことによっても $O(K \log K)$ で求めることができる.
B問題 (400pts, diff: 537) A^B^C
剰余に関する基本的な事実として, 整数 $\alpha, \beta$ と非負整数 $p$, 正の整数 $m$ において,
$$\alpha \equiv \beta \pmod{m} \Rightarrow \alpha^p \equiv \beta^p \pmod{m}$$
である. よって, 入力された $A$ について, 必要ならば $10$ で割った余りに変えることによって, $0 \leq A < 10$ としてもよい.
ここで, $A=0, \dots, 9$ において, $p$ を小さい値で実験すると, $A^p \pmod{10}$ は以下のように周期42で循環することがわかる.
| $A \backslash p$ | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 4 | 8 | 6 | 2 |
| 3 | 3 | 9 | 7 | 1 | 3 |
| 4 | 4 | 6 | 4 | 6 | 4 |
| 5 | 5 | 5 | 5 | 5 | 5 |
| 6 | 6 | 6 | 6 | 6 | 6 |
| 7 | 7 | 9 | 3 | 1 | 7 |
| 8 | 8 | 4 | 2 | 6 | 8 |
| 9 | 9 | 1 | 9 | 1 | 9 |
以上のことから, $A^{B^C} \pmod{10}$ は $A$ と $B^C \pmod{4}$ によって求めることができる. 計算量は $B^C \pmod{4}$ を求めるのに $O(\log C)$ である. 3
C問題 (500pts, diff: 829) String Invasion
文字列 $S$ において, $S[i]=S[i+1] \neq S[i+2]$ を満たす $i$ を昇順にならべたものを $i_1 \leq \dots \leq i_K$ とする. このとき, 操作の選択肢は $K$ 個であるが, $i_K$ を選ぶと, $i_1, \dots, i_{K-1}$ は次の回でも選ぶことができ, $i_K<|S|-2$ ならば, 選択肢に $i_K+1$ も加わり, この $i_K+1$ が次の選択の最大値になる.
この操作を繰り返すのが最善である. このときの操作の回数は次のようにして求めることができる. ただし, $X$ を解答を求める変数とし, 最初は $0$ で初期化している.
- $i=|S|-1,|S|-2, \dots,1$ 順に以下を実行する.
- $S[i]=S[i+1]$ であれば, $S[i+2], S[i+3], \dots, S[|S|]$ にある文字のうち, $S[i]$ でない文字の個数を $X$ に加算する. そして, $S[i+2], S[i+3], \dots, S[|S|]$ をすべて $S[i]$ に変更する.
ここで, $S[i]$ が何個か? という問題に答える必要があるが, これは辞書を使うことによって, 解決することができる. 計算量は $S$ に出てくる可能性のある文字 (アルファベット) の個数を $\sigma$ とすると 4, $O(\sigma |S|)$ である.
D問題 (600pts, diff: 1389) Sky Reflector
$N=1$ のとき, マスの書き方と $B=(B_j)_{j=1}^M$ に1対1の対応がとれ, 書き込みによって $A_1$ が一意に定まることから, 答えは $K^M$ である.
$M=1$ のときも同様にして, 答えは $K^N$ である.
以降では $N,M \geq 2$ とする. 列の対 $(A=(A_i)_{i=1}^N, B=(B_j)_{j=1}^M)$ になるような書き込みが存在するための必要十分条件を考えるが, 実は $(A,B)$ になる書き込みが存在することと, $\max(A) \leq \min (B)$ になることは同値である.
-
十分性: $i$ 行 $j$ 列に書き込む値を $X_{i,j}$ とする. ここで, $A, B$ の定義から, 任意の $(i,j)$ に対して, $A_i \leq X_{i,j} \leq B_j$ であることがわかる. $I,J$ をそれぞれ $I=\max A, J=\min B$ を満たすような添字 (複数あるならばそのうちの1つ)とすると, $A_I \leq X_{I,J} \leq B_J$ であり, $I,J$ の定義から, $\max A \leq \min B$ であることがわかる.
-
必要性: 以下のようにして条件を満たすように書き込むことができる. 5
-
$N \geq M$ のとき
| $\cdots$ | |||||
|---|---|---|---|---|---|
| $B_1$ | $A_1$ | $\cdots$ | $A_1$ | $A_1$ | |
| $A_2$ | $B_2$ | $\cdots$ | $A_2$ | $A_2$ | |
| $\vdots$ | $\vdots$ | $\vdots$ | $\ddots$ | $\vdots$ | $\vdots$ |
| $A_{M-1}$ | $A_{M-1}$ | $\cdots$ | $B_{M-1}$ | $A_{M-1}$ | |
| $A_M$ | $A_M$ | $\cdots$ | $A_M$ | $B_M$ | |
| $A_{M+1}$ | $A_{M+1}$ | $\cdots$ | $A_{M+1}$ | $A_{M+1}$ | |
| $\vdots$ | $\vdots$ | $\vdots$ | $\ddots$ | $\vdots$ | $\vdots$ |
| $A_N$ | $A_N$ | $\cdots$ | $A_N$ | $A_N$ |
- $N \leq M$ のとき
||||$\cdots$||||$\cdots$||
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
||$A_1$|$B_2$|$\cdots$|$B_{N-1}$|$B_N$|$B_{N+1}$|$\cdots$|$B_M$|
||$B_1$|$A_2$|$\cdots$|$B_{N-1}$|$B_N$|$B_{N+1}$|$\cdots$|$B_M$|
|$\vdots$|$\vdots$|$\vdots$|$\ddots$|$\vdots$|$\vdots$|$\vdots$|$\ddots$|$\vdots$|
||$B_1$|$A_2$|$\cdots$|$A_{N-1}$|$B_N$|$B_{N+1}$|$\cdots$|$B_M$|
||$B_1$|$B_2$|$\cdots$|$B_{N-1}$|$A_N$|$B_{N+1}$|$\cdots$|$B_M$|
よって, 問題は $\max A \leq \min B$ なる列対 $(A,B)$ はいくつか? という問題に帰着できた.
$\max A \leq \min B$ なる列対 $(A,B)$ に対する特徴量 $\chi(A,B)$ を, $\chi(A,B):=\max A$ とする. $\chi(A,B)=k$ となる列対 $(A,B)$ を数える.
一般に, $1$ 以上の整数からなる長さ $l$ の列 $A$ で $\min A \leq t$ を満たすのは $t^l$ 個であり, $\min A=t$ を満たすのは, $\min A \leq t$ であるもののうち, $\min A \leq t-1$ ではないものすべてなので, $t^l-(t-1)^l$ であることがわかる.
このことを利用すると, $\chi(A,B)=k$ となる列対 $(A,B)$ において, $\min A=k$ となるのは $k^N-(k-1)^N$ 個, $k \leq \max B$ となるのは $(K-k+1)^M$ 個であり, これらは独立に選ぶことができるので, 合計 $(k^N-(k-1)^N) (K-k+1)^M$ 個である.
これを $k=1, \dots, K$ まで動かして, 求めるべき解は
$$\sum_{k=1}^K (k^N-(k-1)^N) (K-k+1)^M$$
である. 計算量は $O(K \log NM)$ である.
E問題 (800pts, diff: 2789) Rvom and Rsrev
(正解でき次第更新)
F問題 (1000pts, diff: 3990) Social Distance
(正解でき次第更新)
感想
総評
今回のコンテストの D問題 が令和ARCでのD問題で最も簡単だったことから, スピードが重要視された. そのため, Penaltyが非常におおきな影響を与える結果になった.
良かった点
- ひさしぶりにRatingを増やすことに成功し, 昨日の失敗分をキャンセルできた.
反省点
- WAの理由
- B問題: $p:=B^C \pmod{4}$ とし, $A^p \pmod{10}$ を求めてしまった ($B^C$ が4の倍数のとき, $p=4$ とすべきである).