211 C-問題

問題文
文字列 S が与えられます。このうち8 文字を選び下線を引き、
下線を引いた文字が左から順に c , h , o , k , u , d , a , i となるようにする方法は何通りありますか？
ただし答えは非常に大きくなる可能性があるので、(10 9乗 +7) で割った余りを出力してください。

ポイント
DPを理解することが、今の自分の力量では難しい

211C.py

import math,sys,datetime,random,glob,os,re

# 入力
s = input()
MOD = 10 ** 9 + 7

# DP表を用意
# 9列のうち先頭は1とし、残り8列(chokudai 8文字)を0が初期値

dp = [0] * 9
dp[0] = 1

# 一文字ずつ判定し、一致する場合は　dp[i-1]に加算する
for c in s:
    if c == 'c':
        dp[1] = (dp[0] + dp[1]) % MOD
    elif c == 'h':
        dp[2] = (dp[1] + dp[2]) % MOD
    elif c == 'o':
        dp[3] = (dp[2] + dp[3]) % MOD
    elif c == 'k':
        dp[4] = (dp[3] + dp[4]) % MOD
    elif c == 'u':
        dp[5] = (dp[4] + dp[5]) % MOD
    elif c == 'd':
        dp[6] = (dp[5] + dp[6]) % MOD
    elif c == 'a':
        dp[7] = (dp[6] + dp[7]) % MOD
    elif c == 'i':
        dp[8] = (dp[7] + dp[8]) % MOD

print(dp[8])

メモ
類似の問題が出たときに、このDPを活用できれば御の字かと思う(2023/10/15)

アルゴ式：動的計画法ってなに？　(導入)
https://algo-method.com/descriptions/44

212 C-問題

問題文
それぞれ N 個、M 個の正整数からなる 2 つの数列が与えられます。
それぞれの数列から 1 つずつ要素を選んだときの2 つの値の差の最小差を求めてください。

ポイント
・２つの数列をソートして差を順番に求める
・小さい値のインデックスを進めることで無駄な計算を行わない

212C.py

# 入力
N,M = map(int,input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# リストをソートする
A.sort()
B.sort()

# 最小値を求めるため、答えをものすごく大きい数を設定しておく
ans = 10**10

# インデックス
i = 0
j = 0

while i < N and j < M:
    
    # 二つのリストの値を比較して最小値をもとめ、ans と比較する
    ans = min(ans,abs(A[i]-B[j]))

    # 次のループで上で計算したときの小さい値が格納されていたリストの次の値と比較するため、i のインデックスを進める
    if A[i] < B[j]:
        i += 1
    
    elif  A[i] > B[j]:
        j += 1
    
    else:
        print(0)    # 一致する場合は、ゼロが最小値となる
        exit()

print(ans)

214 C-問題

ポイント
・回ってくる宝石か、高橋君から宝石をもらうか早い時刻でリストを更新する
・1番目のすぬけ君は、前周のN番目のすぬけ君から宝石をもらうので、%Nをインデックスとする

214C.py

# 入力
N = int(input())
S = list(map(int, input().split())) # となりから宝石をもらう時刻
T = list(map(int, input().split())) # 高橋君がすぬけ君に渡す時刻

# 高橋君が渡す時間リスト　をより早く宝石を受け取った時間で更新する
for i in range(N):
    T[(i+1)%N] = min(T[(i+1)%N] ,T[(i)%N] + S[(i)%N])

# 円周なので、もう一周する。インデックスはNで割った余り
for i in range(N):
    T[(i+1)%N] = min(T[(i+1)%N] ,T[(i)%N] + S[(i)%N])

print(*T)

215 C-問題

問題文
文字列 S の各文字を並べ替えて作ることが可能な文字列を辞書順にすべて列挙したとき、前から
K 番目にくる文字列を求めてください。

ポイント
・順列を全列挙するライブラリ「from itertools import permutations」を使う
・set で重複をなくす
・関数　「 ''.join 」を使って各文字を結合する
・ソートするために　set から list に置き換える

215C.py

# permutationsというライブラリで列挙する
from itertools import permutations
import math,sys,datetime,random,glob,os,re

# 入力 
S, K=map(str, input().split())
K = int(K) # まとめて受け取ってから　Kを整数に変換

# セットを使って文字列の重複をなくす
ST=set()

# S を構成する文字で　tmpに全列挙する　a,b,c  b,c,a  a,a,a 
for tmp in permutations(S):

    # joinで結合した文字列をセットに格納していく
    word = ''.join(tmp)
    ST.add(word)

# セットをリストに変換してから辞書順にするためソート
ans = list(ST)
ans.sort()

# K-1番目の要素を出力
print(ans[K-1])

AtCoder初心者振り返りメモ ABC211～

211 C-問題

212 C-問題

214 C-問題

215 C-問題