考え方 回答例 考え方「$\mathrm{dp}[n] = n$個から開始したときの答え（先手が取れる最大数）」とすると，（$A_{1} = 1$よりすべての石を取り尽くすことでゲームが終了するので）後手が取る石の個数は$n - \mathrm{dp}[n]$となる． $n$個ある状態で，はじめ…

考え方 回答例 考え方以下を愚直にやってみた． 計算をミスらないように実装するのが大変．．．アライグマ「F問題は算数なのだ……。行ごとの和を考えると、奇数行目と偶数行目がそれぞれ等差数列になってるから、和の公式を使ってO(1)で求められるのだ！」htt…

考え方 回答例 考え方すべての点の組み合わせをみて，隣接しているものをUnionFind（UnionFind木 - 競プロはじめました）でマージすれば良い．2点$(x_{1}, y_{1}), (x_{2}, y_{2})$の隣接条件は\begin{aligned} \begin{cases} \, \max(|x_{1} - x_{2}|, |y_{…

考え方 回答例 考え方$i$軸のうち，どの$j$座標にもルークが含まれないのは1つだけである．したがって，「$(A, B, 1, N)$を聞いたときに$B - A - 1$が帰って来ること」が「$A \leq X \leq B$」の必要十分条件である．よって，二分探索で$X$を求めることがで…

考え方 回答例 考え方コスト最低の頂点から消す． 隣接頂点に対し，消した頂点の分のコストを修正してpushする． （ダイクストラに似ている）回答例 from heapq import heappop, heappush N, M = map(int, input().split()) A = list(map(int, input().split…

考え方 回答例 考え方dp[i][j]=$i$コ目まで決めて，$j$コ選んだ場合の最大値．回答例 N, M = map(int, input().split()) A = list(map(int, input().split())) dp = [[-1<<60] * (M + 1) for _ in range(N + 1)] dp[0][0] = 0 for i in range(N): for j in r…

考え方 回答例 考え方\begin{aligned} &\sum_{i = 1}^{M} i \times A_{k + i} \\ &=\sum_{i = 1}^{M} (k + i) \times A_{k + i} - k\sum_{i = 1}^{M} A_{k + i} \end{aligned}だから，累積和を2種類計算しておけば良い．回答例 N, M = map(int, input().spli…

考え方 回答例 考え方言われたことを愚直にやる．回答例 S = list(input()) row = [[7], [4], [8, 2], [5, 1], [9, 3], [6], [10]] if S[0] != '0': exit(print('No')) for i in range(7): if all(S[x - 1] == '0' for x in row[i]):continue for j in range…