AtCoder Beginner Contest 198 D,F問題メモ

D - Send More Money

問題

  • 英大文字からなる3つの文字列 $S_1,S_2,S_3$ が与えられる
  • $S_1+S_2=S_3$ となる覆面算として解けるかどうか判定し、解ける場合は解の1つを求めよ
  • $1 \le |S_1|,|S_2|,|S_3| \le 10$
  • 制限時間 $5$ sec.

解法

いかにもソルバがどっかに転がってそうではあるけど、まぁ総当たりすればよいので自力で書くことにする。

最大 $10! \times 10$ くらいの計算量が必要になるので、直接、文字をreplaceするなど下手な実装するとTLEになり得る。

文字毎に寄与をまとめておくとよい。

   SEND    E: S1の100の位, S2の1の位、S3の10の位に出現
+  MORE       → 100 + 1 - 10 = 91
= MONEY    E にたとえば6を当てはめると、91 x 6 = 546 の寄与

で、全文字の寄与の合計が0になると、その割り当ては覆面算の解ということになる。(先頭文字が0でないチェックも必要)

Python3

F - Cube

問題

  • 6面に1つずつ正整数の書かれたサイコロを考える
  • 6面の値の総和が $S$ になるようなサイコロへの数字の書き込み方の数を $\mod{998244353}$ で求めよ
  • 回転して同じになるものは1つと数える(数字の向きは関係ない)
  • $6 \le S \le 10^{18}$

解法

$k$ 項間線形漸化式の $S$ 項目は高速に計算する方法があるよ、という問題。

正直、それを自力で導くのは相当骨が折れるので、知識問題感が強い。
(必ずしも使わなくても、パターン分類と行列累乗で解ける。公式解説の解法2。それでも数え上げに上手な発想の転換が必要だが)

以下のあたりが、高速な実装について触れられていて、簡潔と思った。Bostan–Mori のアルゴリズムというらしい。

Python3

programming_algorithm/contest_history/atcoder/2021/0411_abc198.txt · 最終更新: 2021/04/14 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0