Write-up: TopCoder TCO19 Single Round Match 737 Div2

以下3問。Div2って書いてなかったけど多分Div2。

公式Editorial

Single Round Match 737 Editorials - Topcoder 2.0

 

Easy: Make737Easy 

与えられた文字列の中から"7", "3", "7"がこの順序で出てくる回数を求める。文字の間に他の文字が入る可能性がある。 反転数の数え上げを思い出したけど文字列Sの最大が737文字とべらぼうに小さいので、 Challengeフェーズに攻撃されないように分かりやすくして書いた。

class Make737Easy:
    def count(self, S):
        c = 0
        for i1, s1 in enumerate(S):
            for i2, s2 in enumerate(S):
                for i3, s3 in enumerate(S):
                    if i1 < i2 < i3 and s1 == "7" and s2 == "3" and s3 == "7":
                        c += 1
        return c

競技プログラミングアルゴリズムとプログラミングの練習であって、汚い書き方は仕事にも影響出るのでなるべく書かない。  

Medium: AliceAndBobMedium

AliceとBobの石取りゲーム。 1回に一つの山からいくらでも取ってよい。最後の石を取ったほうが勝ち。 思考パターンそのものは少し複雑になるがそれぞれの最善手の説明がある。

「すべての山のサイズのビットごとの排他的論理和」(xとする)がゼロである場合、その手番の人が負け。逆の場合、勝ち。 Aliceの手番の石の数が与えられて、Aliceが勝てる最初の1手のパターン数を考える。

いまいち思考パターンが理解できなかったが説明通りに、排他的論理和を出し、とりあえず0なら負けなので0。

全体の手としては、山の数×それぞれの石の数のパターン数だけあるが、 勝てる手とはxを0にしてターンを終了すること。 ビットコントロール上、1bitでもずれると0にならないので、一つの山に対して高々1つのパターンしかない。 かつ、xの立っているbitをピンポイントに消さないと0にならない。ので、各山に対してxの立っているbitが立っているかを調べて、 すべて立っていればその山からは取れる、立っていなければ取れない。

(コードが間違っていたので削除。)

Hard: SimpleMathProblem

解けず。でも誰も解けてなかった。 整数a, b, c, mが与えられ abc mod m を求める。 シンプルだがそれぞれの値の最大値が747474747 > 7億なので砕いていくことが求められる。

初めはa mod mのサイクル数を出すために、 aとmの最小公倍数を求めて、bcをその最小公倍数で余りにとってみたが、あまり小さくならなかった。 考えるとaとmが互いにその場合、サイクル数は7億*7億程度になってしまうのでボツ。

フェルマーの小定理を使ったとして、a, p が互いに素という条件をどうにかして作って (a ^ (p-1) % p) = 1 の状況にできたとしても、(bc) % (p - 1)は7億程度になってしまい、7億7億が残ってしまうのでボツ。

7億が残ればもうその段階でかなり厳しい戦いになるので、 因数分解で砕いていくんだろうなというところで時間切れ。

「3の100乗を19で割ったあまりは?」を4通りの方法で計算する - tsujimotterのノートブック

繰り返し二乗法あたり使うと計算量はLogで落とせそうなので試すも、pow(b, c)が7億7億になりおじゃん。 何回かけるかはa mod mのサイクル数で7億*7億に落とせそうなのだけれどいまいちテストが通らず実装できず。

class SimpleMathProblem:

    def powmod(self, x, n, M):
        res = 1
        if n > 0:
            res = self.powmod(x, n // 2, M)
            if n % 2 == 0:
                res = (res * res) % M
            else:
                res = (((res * res) % M) * x) % M
        return res

    def calculate(self, a, b, c, m):
        if m > 1:
            k = pow(b, c)
            return self.powmod(a, k, m)
        else:
            return 0

近々リベンジしたい。

Challenge フェーズで3人落としたのは良いがルールを理解してなくて、4,5回無駄なトライをした気がする。