目次
A - 202<s>3</s>
問題
英小文字と数字からなる文字列 S が入力されます。
S は 2023 で終わることが保証されます。
S の最後の文字を 4 に変更し、変更後の文字列を出力してください。
制約
- S は英小文字と数字からなる長さ 4 以上 100 以下の文字列
- S は 2023 で終わる。
詳細はこちらです。
解説
末尾以外にも2023は出てくるため、1文字から順に調べ置き換える場合、不要な箇所を置き換えてしまう可能性があります。
Sを100文字分の文字列として扱い、100文字目から逆順で1文字づつ調べ、はじめに3が出たところを4に変更します。
プログラム例
program abc335a
!S:文字列S
implicit none
integer i
character(100) S
!入力
read (*, *) S
!送料の計算
do i = 100, 1, -1
if (S(i:i) == "3") then
S(i:i) = "4"
exit
end if
end do
!結果の出力
write (*, *) S
end program abc335a
B - Tetrahedral Numbe
問題
整数 N が与えられます。
非負整数の組 (x,y,z) であって x+y+z≤N を満たすものを辞書順で小さい方から順に全て出力してください。
制約
- $0≤N≤21$
- N は整数である
詳細はこちらです。
解説
do文
を用いてx,y,zを変化させ、$x+y+z≤N$未満となる組み合わせのみ出力します。
出力する順番は辞書順の昇順である必要があるので、「$k→j→i$」 の順番に値を変化させます。
なおプログラム上はdo文
の3重ループになりますが、$x,y,z$ は最大でも $N=21$ であるためTLEになることはありません。
プログラム例
program abc335b
!N:整数N
implicit none
integer N, i, j, k
integer arr(4, 4)
!入力
read (*, *) N
!N以下の非負整数の組 (x,y,z)の計算
do i = 0, N
do j = 0, N
do k = 0, N
if (i + j + k <= N) then
write (*, *) i, j, k
end if
end do
end do
end do
end program abc335b
C - Loong Tracking
問題
1 から N までのパーツがついた龍が2次元座標上にいます。パーツ 1 を頭 と呼びます。
最初パーツ i は座標 (i,0) にあります。
上記の状態において、以下のクエリを Q 個処理してください。
クエリ
- クエリ【1,C】
頭を方向Cへ 1 移動させる。
C は R, L, U, D のいずれかであり、それぞれ 「R:x軸+方向」、「L:x 軸ー方向」、「U:y軸+方向』、『D:y軸ー方向』を意味します。
また、移動時には頭以外の全てのパーツは前のパーツに追従するように動く。- クエリ【2,p】
パーツ p のある座標を求める。
制約
- $2≤N≤10^6$
- $1≤Q≤2×10^5$
- 1 種類目のクエリにおいて、C は R, L, U, D のいずれか
- 2 種類目のクエリにおいて、$1≤p≤N$
- 入力に含まれる数値は全て整数
詳細はこちらです。
解説
$2≤N≤10^6$であるため、N 個のパーツ全ての動きを逐一記録するとTELとなります。
頭を除く全てのパーツの位置は頭のパーツの動きに追従して決定するため、頭のパーツの過去の動きから知ることができます。
従ってパーツの動きは頭のパーツのみを記録し、それ以外のパーツは頭のパーツの過去の位置から求めます。
プログラム例
program abc335c
!N :パーツの数
!Q :処理するクエリの数
!query:クエリの内容
!arr :頭パーツの過去の位置(x,y)
!x,y :頭パーツの現在の位置(x,y)
implicit none
integer(16) N, Q, i, cnt, tmp, x, y
integer(16), allocatable::query_1(:), arr(:, :)
character(100000), allocatable::query_2(:)
!読み込み
read (*, *) N, Q
allocate (query_1(Q), query_2(Q), arr(N + Q, 2))
do i = 1, Q
read (*, *) query_1(i), query_2(i)
end do
arr = 0; cnt = N
do i = 1, N
arr(i, 1) = N + 1 - i
arr(i, 2) = 0
end do
x = 1; y = 0
do i = 1, Q
if (query_1(i) == 1) then
select case (query_2(i))
case ("R")
x = x + 1
case ("L")
x = x - 1
case ("U")
y = y + 1
case ("D")
y = y - 1
end select
cnt = cnt + 1
arr(cnt, 1) = x; arr(cnt, 2) = y
else
read (query_2(i), *) tmp
write (*, *) arr(cnt - (tmp - 1), 1), arr(cnt - (tmp - 1), 2)
end if
end do
end program abc335c