| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ■ | ■ | ■ | ■ |
| 結果 | AC | AC | AC | AC | AC | AC |
全体感想
全問正解で、15位（過去最高）。
くだらないタイムロスはたくさんしたし、特に会心の出来という感じはしなかったのですが、順位は高く出ました。
Fがすぐ分かりそうなら絶対解こうと思っていたので、F, Eから順に着手しました。難問が早めに解けると、どこかで一つバグはまりしてもそれなりの順位が確定する安心感があって良い。リスクも多いですが。
Fは全体で最速正解だったみたいです。
問題D – Lamp
やることは単純で、各マス目に対して上下左右の得点を集計するゲーム。
いかにもnumpyで上手いこと書けるやつだと思いましたが、時間をかけて考えた割に、あまり上手に書けなかったｗ 他の人の解法で上手に書いているやつがあれば探そう。
そもそも上下左右の4方向として解いたけれど、「左右」「上下」の得点はまとめられそうですね。連結成分上で定数です。
（後日）
https://maspypy.com/numpy%e9%80%a3%e7%b6%9a%e5%90%8c%e4%b8%80%e5%80%a4%e3%81%ae%e6%95%b0%e3%81%88%e4%b8%8a%e3%81%92-atcoder-abc-129-d
$, $の2値からなるarrayがあるときに、連続で並ぶ$の個数を数えてみましょう。つまり、次のような入出力を実現する方法を考えます。入力： x = 出力： y = それぞれ、連続...問題E – Sum Equals Xor
この手の問題は、下のbitから決めていく方法、上のbitから決めていく方法のどちらでも書けるため、少し迷いましたが、繰り上がるパターンがない問題なので上の桁から決めていきました。$1$まで使える桁を$(0,0)$と割り振ると、それ以降の桁は$(0,0), (0,1), (1,0)$の自由に割り振れます。
そこの部分は$3$のべき乗なのだけど、なぜか$2$や$4$のべき乗にしてしまって少しハマりました。import sys
sys.setrecursionlimit(10**6)問題F – Takahashi’s Basics in Education and Learning
制約条件を見るに、文字列の長さも項数もとんでもなく巨大なので、何かしらまとめて計算する必要がある問題です。
桁数が$d$で一定のところは$\sum_{i=0}^{T-1}(A+Bi)10^{d(T-1-i)}$ のように書けることはすぐに分かります。
\[ \sum_{i=0}^{T-1}r^i,\qquad \sum_{i=0}^{T-1}ir^i \]は高校数学の標準的な計算で公式が作れるので、1つにまとめて計算できます（$r^T$が必要なので計算量は $O(\log T)$。）
$r = 1$ を除けば $\sum_{i=0}^{T-1}r^i = \frac{r^T-1}{r-1}$ となりますが、これを $\bmod M$ で求めるところが少し厄介です。$r^T$を$\bmod M$ の形でのみ計算しても、除算が一意に定まりません。
そこは、$r^{T}-1$ を $\bmod M(r-1)$ で計算することで解決しました。この計算は64ビット整数を超える大きさになるので言語によってはこの方針だとちょっと作業量が増えるかもしれません。
$r=1$ が大丈夫か、とか、$r$ が $M$ の倍数のときが大丈夫か、とか、細かいミスを検証して提出。