A - 3.14
問題
1 以上 100 以下の整数 N が与えられます。
円周率を小数第 N 位まで出力してください。
制約
- $1≤N≤100$
- N は整数
詳細はこちらです。
解説
【フローチャート】
入力したNに従って、円周率を出力します。
【補足】
※1
円周率を100桁分を変数piに用意します。
100桁をreal型で管理すると桁落ちが心配です。
加えて実数で管理すると、出力時の桁数を可変にするのが大変そうなので、文字型で管理します。
※2
Nの数に関わらず、3.までは確実に出力するため、予め3.までを出力しておきます。
※3
円周率の少数点よりも後ろの数字を入力したNに合わせて出力します。
文字型で定義しているので、出力する範囲をpi(1:N)とすれば、出力時の桁数を可変にできます。
プログラム例
program ABC314a
implicit none
character(100) pi
integer N
!初期化
pi = '1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679'
!入力
read (*, *) N
!出力
write (*, '(a2)', ADVANCE='NO') '3.'
write (*, '(a)') pi(1:N)
end program abc314a
B - Roulette
問題
N 人の人がルーレットの賭けに参加しました。
ルーレットの出目は、0 から 36 までの整数です。
N 人はそれぞれ$C_i$個の目、 $A_{i,1},A_{i1},A_{i,1},…,A_{i,C_i}$ に賭けています。
ルーレットが回され、出目が X の時、 X に賭けた人たちのうち、賭けた目の個数が最も少ない人たちの番号を昇順にすべて出力してください。
制約
- $1≤N≤100$
- $1≤C_i≤37$
- $0≤A_{i,j}≤36$
- 任意の i=1,2,…,N について、$A_{i,1},A_{i,2},…,A_{i,C_i}$はすべて異なる。
- $0≤X≤36$
- 入力はすべて整数
詳細はこちらです。
解説
【フローチャート】
$N,C_i$ が十分に小さいので、N 人の結果を全て確認し、X に賭けた人で賭けた目の個数が最も少ない人を探します。
【補足】
※1
any関数を使い、$A_{i,1},A_{i1},A_{i,1},…,A_{i,C_i}$ の中にXが含まれているかを調べます。
※2
min関数を用いて、Xが含まれている最小の$C_i$を探します。
※3
結果の出力を行います。
$C_1 ~C_N$までを全て調べ、Xが含まれている最小の$C_i$を順次出力します。
プログラム例
program ABC314b
implicit none
integer i, j
integer N, X, min_C, cnt
integer, allocatable :: A(:, :), check_hit(:), C(:)
!初期化
cnt = 0
check_hit = 0
min_C = 99
!入力1
read (*, *) N
allocate (A(N, 99), check_hit(N), c(N))
A = 99
do i = 1, N
read (*, *) C(i)
read (*, *) (A(i, j), j=1, C(i))
end do
read (*, *) X
!Xを含む最小のCを調べる
do i = 1, N
if (any(A(i, :) == X)) then
check_hit(i) = 1
min_C = min(min_C, C(i))
end if
end do
!結果の出力
if (min_C == 99) then
write (*, '(i0)') 0
else
do i = 1, N
if (C(i) == min_C .and. check_hit(i) == 1) cnt = cnt + 1
end do
write (*, '(i0)') cnt
do i = 1, N
if (C(i) == min_C .and. check_hit(i) == 1) write (*, '(i0,1x)', ADVANCE='NO') i
end do
end if
end program abc314b
C - Rotate Colored Subsequence
【未ACです】
プログラム例には注意が必要です。
allocate (a(M, N))が入るタイミングでRE(実行時エラー)となるケースがあり、ACされていません。
ACになりました。修正した回答は最後に掲載しています。
問題
長さ N の文字列 S が与えられます。
S の各文字は、色 1から色 M のいずれかの色で塗られています。
文字列 S について、同じ色で塗られた文字同士で**右に 1 つ巡回シフト*を行い、最終的な文字列 S を作成します。
制約
- $1≤M≤N≤2×10_5$
- $21≤C_i≤M$
- $N,M,C_i$はすべて整数
- S は英小文字からなる長さ N の文字列
- 任意の整数 $1≤i≤M$ に対して、ある整数 $1≤j≤N$ が存在して $C_j=i$ が成り立つ
詳細はこちらです。
解説
【注意点】
- $1≤M≤N≤2×10_5$であるため、総当たりで巡回シフトを実装すると、
TLEとなってしまいます。
【フローチャート】
同じ色ごとに文字列の配列を作成し、個別に巡回シフトを行い、最後に文字列を結合して配列を作成します。
【補足】
※1
各文字を１文字ずつ調べ、色 1から色 M までの出現回数を算出します。
※2
各文字を１文字ずつ調べ、その文字が何色で何文字目かを記録します。
※1で算出した出現回数を参照して、昇順に配列に格納します。
※3
各色ごとに記録した配列において、右に1つ巡回シフトした配列番号を計算します。
基本的に右に1つずらすだけなので+1すれば良いのですが、末尾は先頭にシフトすることに注意が必要です。
今回は、各色の出現回数の総数で割ったあまりを使うことで、1つの計算式で巡回シフト先の配列番号を計算しています。
例
色Aの出現回数の総数が4の場合
元の配列 (i=1,4) は[1],[2],[3],[4]は巡回シフト後、[4],[1],[2],[3]となります。
$巡回シフト先 =mod(i,4)+1$とすれば、1,2,3の時はあまり+1になり、4の時は0+1で先頭にシフトするとができます。
※4
計算した巡回シフト先の番号を元に、各色ごとの配列に格納された出現順の記録を右に1つ巡回シフトします。
※5
文字列 S の色を順番に見ていき、色に応じた文字を１文字づつ出力します。
出力は各色ごとの出現順を記録した配列を参照し、昇順に出力していきます。
１文字づつ順次出力するので、write構文に advance='no'を追加し、改行されない様にします。
プログラム例
なぜ以前の回答はREだったのか？
以前の回答では、各色の出現位置と回数を管理する配列を考えうる最大サイズ(M,N)で確保していたことにより、必要なメモリが大きくなりすぎた結果、REとなっていました。
解決策として、typeを用いて配列の中にallocatable な配列を持たせ配列のサイズを最小限にし、メモリ不足を解消、ACとなりました。
古い回答
program ABC314c_RE
!implicit none
integer(16) N, M, i, tmp
integer(16), allocatable:: C(:), cnt(:), cnt_max(:)
character(:), allocatable :: S, list(:, :), ans(:, :)
read (*, *) N, M
allocate (character(N) :: S)
allocate (cnt_max(M), cnt(M)); cnt_max = 0; cnt = 0
allocate (character(1) :: list(M, N), ans(M, N))
read (*, *) S
allocate (C(N))
read (*, *) C(:)
!出現位置の振り分け
do i = 1, N
cnt(C(i)) = cnt(C(i)) + 1
list(C(i), cnt(C(i))) = S(i:i)
end do
!巡回シフト
cnt_max = cnt
cnt = 0
do i = 1, N
cnt(C(i)) = cnt(C(i)) + 1
tmp = mod(cnt(C(i)), cnt_max(C(i))) + 1
ans(C(i), tmp) = list(C(i), cnt(C(i)))
end do
!結果の出力
cnt = 0
do i = 1, N
cnt(C(i)) = cnt(C(i)) + 1
write (*, '(a)', advance='no') ans(C(i), cnt(C(i)))
end do
end
program ABC314c_AC
!implicit none
integer(16) N, M, i, tmp
integer(16), allocatable:: C(:), cnt(:), cnt_max(:)
character(:), allocatable :: S
type :: array
character(1), allocatable :: arr(:)
character(1), allocatable :: arr2(:)
end type
type(array), allocatable :: arr_of_arr(:), arr2_of_arr(:)
!１次元の配列(arr_of_arr)の中に1次元の配列(arr)が入っています。
!arr_of_arr(:)で縦の長さを可変長、arr(:)で横の長さを可変長にしています。
read (*, *) N, M
allocate (character(N) :: S)
allocate (cnt_max(M), cnt(M)); cnt_max(M) = 0; cnt(M) = 0
allocate (arr_of_arr(M), arr2_of_arr(M))
read (*, *) S
allocate (C(N))
read (*, *) C(:)
!各色の出現回数の取得
do i = 1, N
cnt(C(i)) = cnt(C(i)) + 1
end do
do i = 1, M
allocate (arr_of_arr(i)%arr(cnt(i)))
allocate (arr2_of_arr(i)%arr2(cnt(i)))
end do
cnt = 0
do i = 1, N
cnt(C(i)) = cnt(C(i)) + 1
arr_of_arr(C(i))%arr(cnt(C(i))) = S(i:i)
end do
!巡回シフト
cnt_max = cnt
cnt = 0
do i = 1, N
cnt(C(i)) = cnt(C(i)) + 1
tmp = mod(cnt(C(i)), cnt_max(C(i))) + 1
arr2_of_arr(C(i))%arr2(tmp) = arr_of_arr(C(i))%arr(cnt(C(i)))
end do
!結果の出力
cnt = 0
do i = 1, N
cnt(C(i)) = cnt(C(i)) + 1
write (*, '(a)', advance='no') arr2_of_arr(C(i))%arr2(cnt(C(i)))
end do
end
感想
- C問題について、allocate (a(M, N))が入るタイミングでRE(実行時エラー)となるケースがあり、ACがどうしてもACできませんでした。(下記URL)
- [該当部分のみ]https://atcoder.jp/contests/abc314/submissions/45003764
- [回答全体]https://atcoder.jp/contests/abc314/submissions/45002589
- $1≤M≤N≤2×10^5$に対して
allocate(a(M,N))をしているので、配列が大きすぎるとallocateの機能が使えないのかなと、今のところ考えています。 - 記事にするか悩みましたが、自身の勉強のために投稿していること、回答のアルゴリズム自体は間違っていないと考え投稿しています。