解説つき！競ってわかる　はじめてpythonプログラミング

競プロの情報発信と備忘録を兼ねている

ABC238C

AtCoder Python

ABC238C の解説

atcoder.jp


解答コード

https://atcoder.jp/contests/abc238/submissions/29083168

 

問題

少し条件が入った数列の総和の問題です．
f(x)は，x以下の正整数で，xと桁数が同じものの数を表すとき，
与えられた整数Nについて，
f(1)からf(N)の総和を求めます．

例えば f(16)は，16以下の正整数
[1, 2, ,3, ..., 9, 10, 11, 12, 13, 14, 15, 16]
のうち，16と桁数が同じものは，
[10, 11, 12, 13, 14, 15, 16]
の7つですので，
f(16) = 7
となります．

 

解説

Nが10^18のオーダーですので，単純なループで総和を求めることは不可能です．

そこで，規則性について理解するために，例としてN=16の時の場合を，手を動かして考えます．

f:id:nodashin_jpn:20220208123845j:plain

ABC238C_ex1

上図のように考えると，10から16についての和を考えるとき，9を7回引いてあげれば良いことがわかります．

 

では，次の例を見てみます．

f:id:nodashin_jpn:20220208123855j:plain

ABC238C_ex2

このように，99ないしは，9のように小さい桁の数字の分だけあとから引いてあげれば良いです．

 

コードにします．

 

標準入力を読み込みと，MODを定義します．

N = int(input())
MOD = 998244353

 

まず，1からNまでの総和を計算します．

x = N*(N+1)//2

 

ここから，9999, 999, 99, 9のような数字を個数分だけ引いていきます．for分の最初のループだけ，139個=238-99 のように，9000個，900個，90個，9個のようなキリのいい数字にはならない点に注意してください．

l = len(str(N))
for i in range(l-1, 0, -1):
    y = 10**i - 1
    if i == l-1:
        num = N - y
    else:
        num = 9 * 10**i
    x = x - num*y

 

最後にMODを計算して，出力します．

print(x % MOD)

 

以上，ABC238Cの解法でした．

 

 

＜参考解説リンク＞

1) 【AtCoder解説】PythonでABC238のA,B,C,D,E問題を制する！ - Qiita

 

ABC238B

AtCoder Python

ABC238B の解説

atcoder.jp


解答コード

https://atcoder.jp/contests/abc238/submissions/29074032

 

問題

ピザに切り込みを入れていって，最大のピースの角度を求める問題です．

 

解説

「ピザを時計回りにに回転させる」とありますが，「カッターを"反"時計回り」に回転させます．
（問題文で正の角度を時計回りに回転させているので，時計回りを正として計算しています，ご了承ください．）

 

概要図です．

f:id:nodashin_jpn:20220208082843j:plain

ABC238B_overview

 

まず，標準入力の読み取り，[0, 360] の入ったリストを作成します．

N = int(input())
L = [0, 360]
A = list(map(int, input().split()))

 

前のカッターの位置から反時計回りに移動させた位置を記録します．角度の値がマイナスになったり，360度を超えたりするときは，余りを計算すると良いです．

d = 0
for a in A:
    d = (d - a) % 360
    L.append(d)

 

ソートします．

L = sorted(L, reverse=True)

 

最後に前後の差を計算して，最大となる値を出力します．

ans = 0
for lh, ll in zip(L[:-1], L[1:]):
    ans = max(ans, lh-ll)
print(ans)

 

以上，ABC238Bの解法でした．

 

 

<参考解説リンク>

1) 【AtCoder解説】PythonでABC238のA,B,C,D,E問題を制する！ - Qiita

ABC238A

AtCoder Python

ABC238A の解説

atcoder.jp

 

解答コード

https://atcoder.jp/contests/abc238/submissions/29069165

 

問題

正の整数nについて 2^n と n^2 の大小を比較する問題です．

 

解説

「与えられた問題文の通りそのまま実装すれば良い」問題がほとんどのA問題ですが，この問題は一筋縄では実装できません．なにせ，2^n が非常に大きな数字になってしまうからです．

そこで，指数関数の方が，nが十分大きな値では爆発的に増加する数学的性質を用います．言い換えれば，nが小さな値，1, 2, 3, ..., 10 あたりでは大小の比較が必要にしても，それよりnが大きくなれば，指数関数の方が勝ちます．

 

そこで手元で，以下のようなコードを実行して，nが小さいときどうなるか確かめます．

print('n', '2^n', 'n^2', 'left>right', sep='\t')
for i in range(1, 10):
    x = 2**i
    y = i**2
    print(i, x, y, x > y, sep='\t')

# n	2^n	n^2	left>right
# 1	2	1	True
# 2	4	4	False
# 3	8	9	False
# 4	16	16	False
# 5	32	25	True
# 6	64	36	True
# 7	128	49	True
# 8	256	64	True
# 9	512	81	True

 

すると，nが 2, 3, 4 の時だけFalse であることがわかります．
よってそのときだけ'No'を出力すれば良いです．

n = int(input())
if n in (2, 3, 4):
    print('No')
else:
    print('Yes')

 

以上，ABC238Aの解法でした．

ABC237C

AtCoder Python

ABC237C の解説

atcoder.jp


解答コード

https://atcoder.jp/contests/abc237/submissions/29052747

 

問題

文字列の先頭に，任意の数だけ'a'をつけることで，与えられた文字列を回文にできるかどうか判定する問題です．

 

解説

考え方は，４つのステップからなります．

  1. 文字列Sの先頭と語尾にいくつのaが連続しているか調べる
  2. 先頭にある連続したaの個数が語尾に連続するaの個数以下である
  3. Sの先頭と語尾にある連続するaを除く
  4. 残った文字列Sが回文か調べ，回文であれば題意を満たす

概要は下図．

f:id:nodashin_jpn:20220205170418j:plain

ABC237C_overview

 

まず，文字列Sについて回文かどうかの判定をする関数を作成します．
回文かどうかということは，文字列を逆順にしても同じであることを意味します．
厳密には，文字列の半分の長さまでを判定すればよいです．

def is_palindrome(s):
    """回文かどうか判定"""
    return s == s[::-1]

 

標準入力を読み込みます．

S = input()


文字の先頭と語尾のaの長さを数えます．

right_len_a = len(S) - len(S.rstrip('a'))
left_len_a = len(S) - len(S.lstrip('a'))

 

もし，語尾（右側）のaの長さが先頭（左側）より短い場合は，題意を満たしません．
なぜなら，aを追加できるのは先頭だけだからです．

さらに，先頭にあるaと語尾のaを除いた残りのブロックが回文である必要があります．

if right_len_a >= left_len_a and is_palindrome(S.strip('a')):
    ans = 'Yes'
else:
    ans = 'No'
print(ans)

 

以上，ABC237Cの解法でした．

 

コメント，ブックマークよろしくお願いします！！

ABC237E

AtCoder Python

ABC237E の解説

atcoder.jp



解答コード

https://atcoder.jp/contests/abc237/submissions/28967250

 

問題

f:id:nodashin_jpn:20220205102544j:plain

ABC237E_overview


移動する際に発生するコストが最大となるルートを探す問題です．

 

解説

幅優先探索を用いて，全ての地点に移動した後，どの地点で終了した方が最もコストが大きくなるか探します．

最終的に得られるリストのイメージは，上図（例１）の場合，
[0, 2, -4, 3]
となります．

リストの4番目（ゼロインデックスで3番目）の数字が3であるのは，
地点1から地点4まで適切なルートで移動した場合，コスト（楽しさ）が3であることを示しています．

この際，どんなルートで移動したら良いかといった具体的な道順は，保存していません．

 

実装します．

 

幅優先探索を行うので，dequeを使います．

from collections import deque

 

標準入力を読み込みます．
地点を示す番号は，ゼロインデックスで処理します．

N, M = map(int, input().split())
H = list(map(int, input().split()))

G = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(lambda x: int(x)-1, input().split())
    G[u].append(v)
    G[v].append(u)

 

幅優先探索をしながら，コストの計算を書くと煩雑になるので，
あらかじめ高低差に応じて楽しさを計算する関数を作ります．

def calc_cost(hs, he):
    if hs >= he:
        return hs-he
    else:
        return 2*(hs-he)

 

地点0から処理を開始します．各地点の初期値は-infにします．

x = 0
costs = [float('-inf')]*N
costs[x] = 0
dq = deque([0])


幅優先探索を実行します．
ルートを探索する条件は，以前のルートでその地点に来た時のコストの最大値を，今回移動して来たことでコストの最大値を更新できるかどうかになります．

最後にコストの最大値を出力すると終了です．

while dq:
    x_now = dq.popleft()
    cost_now = costs[x_now]

    for x_next in G[x_now]:
        # 以前の他のルートでその地点に来た時の最大値
        cost_next = costs[x_next]
        # 今回移動して来たときのコストの計算値
        cost_calced = cost_now + calc_cost(H[x_now], H[x_next])
        if cost_calced > cost_next:
            costs[x_next] = cost_calced
            dq.append(x_next)
print(max(costs))

 

以上，ABC237Eの解法でした．

ABC237D

AtCoder Python

ABC237D の解説

atcoder.jp

 

解答コード

https://atcoder.jp/contests/abc237/submissions/28965017

 

問題

1からNまでの数字をリストに挿入していく問題です．
各数字ごとに"L" or "R" の文字列が与えられて，
Lの時は直前の数字の左に，
Rの時は直前の数字の右に数字を挿入していきます．

 

解説

0, 1, ,2, ..., Nの順に挿入していくのではなく，逆順のN, N-1, N-2, ..., 0 を挿入して実装しました．
公式解説ページのユーザー解説にある「両端キュー」の発想はなかった...> <

まず，dequeをimportします．

from collections import deque

 

標準入力を読み込みます．

N = int(input())
S = list(input())

 

deque には，はじめNが含まれています．ここにN-1以降の数字を挿入していきます．

dq = deque([N])

 

N-1の挿入について考えます．文字列が"L"であれば，N-1の左側にNが挿入されることを意味します．[N] -> [N-1, N]
つまり，今，逆順で考えていますので，文字列が"L"のとき，Nの右側にN-1を挿入していきます．

この点に留意して，キューに数字を追加していきます．

for i in range(N-1, -1, -1):
    s = S[i]
    if s == 'L':
        dq.append(i)
    else:
        dq.appendleft(i)

 

最後にdequeをlist型にもどして，出力します．

ans = list(dq)
print(*ans, sep=' ')

 

リストにせずともで同様の結果になりますが，明示的にansに代入しています．

print(*dq, sep=' ')

 

以上，ABC237Dの解法でした．

ABC235D

AtCoder Python

ABC235D の解説

atcoder.jp

 

解答コード

https://atcoder.jp/contests/abc235/submissions/28827750

 

問題

初期値1にaをかけるか下一桁を先頭に移動させる（ただし桁数が変わってはならない）かのどちらかの操作を繰り返し行い，Nになるまでの最短の回数を考える問題です．

 

解説

幅優先探索で解くことができます．
数字を先頭に移動させる操作で桁数が変わらない制約のことを見落としていて，正解に辿りつくのに苦戦しました．

初期値1に操作を加えてNになる最短手数を考える問題ですが，
逆に，Nからスタートして，1になるまでの最短手数を考えようと思います．
Nから逆順に操作をするため，末尾を先頭に移動させる操作も逆になり，先頭を末尾に移動させる操作になりますので注意が必要です．

概要図です．

f:id:nodashin_jpn:20220128184943j:plain

ABC235D_overview

 

幅優先探索の相棒のdequeのインポートと標準入力を読み込みます．

from collections import deque

a, N = map(int, input().split())

 

ここで，数字の先頭を末尾に移動させる操作を行う関数を定義します．この時桁数が変わらないように気をつける必要があります．桁数が変わったり，桁数が1で移動させる操作ができない時は，Noneをreturnするようにします．

def head_to_suffix(x):
    if x > 9 and x%10 > 0:
        s = str(x)
        if s[1] != '0':
            return int(s[1:] + s[0])
    return None

 

一度みた数字を再度探索することは無駄ですので，seenで管理して初めてみる数字のみ探索します．ansは最小手数が見つからないことを考慮して，-1で定義します．
dequeにはリストを入れるようにして，[現在の値, 現在の手数]で管理します．

seen = set([])
ans = -1
dq = deque([[N, 0]])

 

while文でBFSを行います．

すでにxが1であれば，これ以上の探索をする必要はありません．また幅優先探索なので，初めて1に到達した時の手数がそのまま最小手数になります．またelifですでに見た数字は探索しないようにします．初めての数字であれば，次から探索しないようにsetに加えておきます．

 次に２つの探索を行います．

  1. 現在の値xをaで割りきれる場合は，aで割る．
  2. 先頭を末尾に移動する操作ができる場合，すなわち上記の関数を実行して，return がNoneではないときは，その操作を行う．

操作をした値は，操作回数cntに+1をして，キューにappendします．

while dq:
    x, cnt = dq.popleft()
    if x == 1:
        ans = cnt
        break
    elif x in seen:
        continue
    else:
        seen.add(x)
    if x%a==0:
        dq.append([x//a, cnt+1])
    xh = head_to_suffix(x)
    if xh:
        dq.append([xh, cnt+1])

 

このwhile文のループを抜け出したとき，もし最小手数があればansはすでに更新されています．
あとはそのまま出力をすれば終了です．

print(ans)

 

以上，ABC235Dの解法でした．