e-Log

e271828のブログだお

AtCoder ARC176 (2024-04-21)

競プロ AtCoder ARC Python

ARC176 に参戦．前回 ARC175 に続いて NoSub……

問題Ａはコンテスト終了間際に，列ごとの合計値を持たせておいて上から貪欲で決めていく実装を思いついたが，間に合わず（のちに嘘解法と判明）．問題Ｂは式変形がポイントだとすぐにわかったけれど，思いつかず……

  • パフォーマンス：347
  • レーティング：156 (+27)

問題Ｂ - Simple Math 4 (400 点)

【問題ページ】 Difficulty: 1298

問題の概要

2^{N} を 2^{M} - 2^{K} で割ったあまりの 1 の位を求める．

制約条件

  • 1 \leq N \leq 10^{18}
  • 1 \leq K \lt M \leq 10^{18}

解き方

N \geq K のとき，2^{N} \equiv 2^{N} - 2^{N - M} (2^{M} - 2^{K}) \equiv 2^{N - (M - K)}(\mathrm{mod}\ 2^{M} - 2^{K}) と式変形させる．あとは場合分け．

以下，コンテスト終了後に解説を見ながら組んだ AC コード (Python)．CPython 3.11.4 だと 1 ケースで TLE，PyPy3.10-v7.3.12 で AC.

t = int(input())
for _ in range(t):
  n, m, k = map(int, input().split())
  if m - k == 1:
    if n >= m - 1:
      print(0)
    else:
      print(pow(2, n, 10))
  else:
    while n >= m:
      n = k * (n // m) + n % m
    
    if n == k and k == m - 1:
      print(0)
    else:
      print(pow(2, n, 10))

ARC，さすがに一筋縄ではいかない．がんばる．

Best regards, e271828.