AtCoder Beginner Contest 363 - あるぱかのブログ

第363回は回文回

A - Piling Up
B - Japanese Cursed Doll
C - Avoid K Palindrome 2
D - Palindromic Number

A - Piling Up

概要：レート100上がるごとに^の数が増えます。次に^が増えるのはレートがいくつ上がったタイミングか数えてね

現在のレートを100で割った余りを見ることで解答できます。

100から上記の余りを引いた数を出力します。

#ABC363 A - Piling Up
R = int(input())
print(100 - R%100)

提出リンク：提出 #55882677 - AtCoder Beginner Contest 363

B - Japanese Cursed Doll

リンク：B - Japanese Cursed Doll (atcoder.jp)

概要：髪が長い上位 $P$ 番目の人形の髪の長さが $T$ 以上になるのが何日後か教えてね

どの人形も髪が伸びる速さが同じということで、スタート時点で髪が長い順に並べ替えてみます。

ソートした後で上位 $T$ 番目の人が長さ $P$ になるために必要な日数を出力します。

既に長さ $P$ 以上の場合は0を出力するように場合分けしています。

#ABC363 B - Japanese Cursed Doll
N, T, P = map(int, input().split())
L = sorted(list(map(int, input().split())), reverse = True)
if L[P-1] >= T:
    print(0)
else:
    print(T-L[P-1])

提出リンク：提出 #55882731 - AtCoder Beginner Contest 363

C - Avoid K Palindrome 2

リンク：C - Avoid K Palindrome 2 (atcoder.jp)

概要：文字列を並べ替えた時に長さ $K$ の部分文字列が回文にならないものだけを数え上げてね

制約が $N \leq 10$ と小さいので全探索できそうです。

itertoolsのpermutationsで全ての並びを試して都度回文判定をすることで題意を満たせそうです

・・・が、Pythonのpermutationsでは1～2ケースでTLEしてしまいます。

コンテスト後のtwitterを見るとmore_itertoolsの中のdistinct_permutationsを使うことでACできるようです。

こちらは重複のない順列のみを生成できるみたいです。

from more_itertools import distinct_permutations
def kaibun(s):
    n = len(s)
    judge = True
    for i in range(n//2):
        if s[i] != s[-1-i]:
            judge = False
            break
    return judge
N, K = map(int, input().split())
S = input()
ans = 0
for p in distinct_permutations(S):
    now = ''.join(p)
    judge = True
    for i in range(N-K+1):
        if kaibun(now[i:i+K]):
            judge = False
    if judge:
        ans += 1
print(ans)

提出 #55870168 - AtCoder Beginner Contest 363

D - Palindromic Number

リンク：D - Palindromic Number (atcoder.jp)

概要：回文になっている数字、回文数を小さい順に並べた時 $N$ 番目の数字を教えてね

制約が大きいので探索では不可能そうなので法則を探してみます。

0を除外すると1桁の回文数は1~9の9個、2桁は11～99の9個、3桁は101～191、201～292、・・・で90個、というように桁が2個上がるごとに9、90、900、・・・と増えていくようです。

このことから $N$ をうまいこと処理すれば何桁の回文数になるかが分かりそうです。

次に回文数の上位の桁をみると11、12、・・・のように昇順に並んでいることがわかります。

目的となる桁数より小さい桁数で作れる回文数の総数を出しておけば、出力したい数字が何らかの方法で生成できそうです。

桁数を1～40（制約内では最大35桁）で増やしながら目的の回文数の桁数に合致するか確認する。しなければ既にみた回文数の数ということでseenを加算する。
桁数が分かったので回文数の上位の数を作る。
桁数が奇数が偶数かに応じて適切な回文数を作って出力する。

#ABC363 D - Palindromic Number
N = int(input())
if N == 1:
    print(0)
    exit()
N -= 1
seen = 0
for i in range(1, 40):
    d = 9*pow(10, (i-1)//2)
    if N <= seen+d:
        break
    seen += d
t = str(pow(10, (i-1)//2) + (N-seen-1))
if i%2 == 0:
    ans = t + t[::-1]
else:
    ans = t + t[::-1][1:]
print(ans)

提出リンク：提出 #55884327 - AtCoder Beginner Contest 363