アルゴリズムの学習改善のための自身の備忘録及び学習の一環として記事を書くことにしました.
読んでくれた方で何かありましたら気兼ねなくコメントしてください.お待ちしております.
A - T-shirt
問題文
あるプログラミングコンテストでは、以下のルールに従って参加者に T シャツをプレゼントします。
- 上位 A 位までの参加者は、必ず T シャツが貰える。
- 加えて、上位 A+1 位から B 位までの参加者のうち C 人が一様ランダムに選ばれ、選ばれた参加者は T シャツを貰える。
コンテストには 1000 人が参加し、全ての参加者が相異なる順位を取りました。
このコンテストの参加者であるいろはちゃんは、X 位を取りました。
このとき、いろはちゃんが T シャツを貰える確率を求めてください。
制約
入力はすべて整数
1≤A<B≤1000
1≤C≤B−A
1≤X≤1000
入力
入力は以下の形式で標準入力から与えられる。
A B C D X
考察
- X≧Aの際、確立は1
- A＜X≦Bの際、確立は$\frac{C}{B-A}$
- X<Bの際は0
これをそのまま出力すればよい.
サンプルコード
a,b,c,x=map(int,input().split())
if x<=a:
print(1)
elif x<=b:
print(c/(b-a))
else:
print(0)
B - Minimize Ordering
問題文
文字列 S が与えられます。S の各文字を並び替えて得られる文字列 $S'$ のうち、辞書>順で最小のものを出力してください。
なお、相異なる 2 つの文字列 $s=s_1s_2\dots s_n$とt=$t_1t_2\dots t_m$について、>それらが以下の条件のいずれかを満たすとき、辞書順で s<t であるとします。
- ある整数 i (1≤i≤min(n,m)) が存在し、$s_iいて $s_j=t_j$
- すべての整数 i (1≤i≤min(n,m)) について $s_i=t_i$かつ、n<m
制約
S は英小文字のみからなる長さ 1 以上 $2×10^5$以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
考察
入力文字列を一文字ずつ格納された配列であると考える。
これを昇順に並べ替え配列を結合しながら文字列として出力することにより答えが求まる。
サンプルコード
s=list(input())
s.sort()
print("".join(s))
これは1行のコードにまとめられる
print("".join(sorted(list(input()))))
どちらも同じ答えが得られる.
C - 1111gal password
問題文
整数 N が与えられるので、以下の条件を全て満たす整数 X の個数を 998244353 で割った余りを求めてください。
- N 桁の正整数である。
- X の各桁を上の位から順に $X_1,X_2,\dots ,X_N$とする。このとき以下の条件を全て満たす
- 全ての整数 1≤i≤N に対して$1≤X_i≤9$
- 全ての整数 1≤i≤N−1 に対して$∣X_i−X_{i+1}∣≤1$
制約
N は整数
$2≤N≤10^6$
入力
入力は以下の形式で標準入力から与えられる。
N
考察
動的計画法を用いて考える
i番目はdp[i][j]=(dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1])としてn回遷移を行えば良い。
この時、j=0,j=10の場合、何も遷移しない。
最後まで遷移をさると、dp[i]の合計を計算する。
計算途中も含め適度に998244353で剰余を取り答えたい。
$10^7$程度の計算をひつようとしているので、pypyなどの高速な言語を使いたい
サンプルコード
MOD=998244353
n=int(input())
dp=[[0 for _ in range(11)] for _ in range(n)]
for i in range(1,10):
dp[0][i]=1
for i in range(1,n):
for j in range(1,10):
dp[i][j]=(dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1])%MOD
print(sum(dp[i])%MOD)