A - Potions
問題
体力 H のモンスターに対して傷薬 P を与え、体力を X 以上にしたいです。
傷薬は N 種類あり、効き目の弱い順に 1 から N までの番号がついています。
モンスターの体力が X 以上になる、最小の傷薬を探します。
制約
- $2≤N≤100$
- $1≤H<X≤999$
- $1≤P_1<P_2<⋯<P_N=999$
- 入力される値はすべて整数
詳細はこちらです。
解説
【フローチャート】
薬を1から昇順に使い、モンスターの体力が X 以上になる最小の種類を探します。
【補足】
※1
薬を与えた後のモンスターの体力Ansが X以上であるかを調べます。
X以上の場合、薬の種類iを出力します。
プログラム例
program ABC317a
implicit none
integer i, Ans, N, H, X
integer, allocatable :: P(:)
!入力
read (*, *) N, H, X
allocate (P(N))
read (*, *) P(:)
!判定
do i = 1, N
Ans = H + P(i)
if (Ans >= X) then
write (*, '(i0)') i
stop
end if
end do
end program abc317a
B - MissingNo.
問題
N+1 個の連続する整数 $A_1,A_2,...A_N$ を 1 個ずつ持っていましたが、そのうち 1 個をなくしてしまいました。なくした整数を求めてください。
制約
- $2≤N≤100$
- $1≤A_i≤1000$
- 入力は全て整数である
- なくした整数は一意に定まる
詳細はこちらです。
解説
【フローチャート】
$A_1,A_2,...A_N$ をソートし、順番に$A_1$から順に連続して並んでいるかを調べます。
【補足】
※1
入力した**$A_1,A_2,...A_N$**を降順に並び替えます。
並び替えにはマージソートを使用します。
※2
隣り合う数$A_iとA_{i+1}$が連続しているかについて、$A_i-A_{i+1}$で差を求めることで確かめます。
連続する整数であれば、差が1になり、連続する整数でなければ、差が1以上になっています。
プログラム例
program ABC317b
implicit none
integer N, i
integer, allocatable :: A(:), tmp(:)
!入力
read (*, *) N
allocate (A(N), tmp(N))
read (*, *) A(:)
!Aを昇順にソート
call margesort(A, tmp, N, 1, N)
!不連続部分を調べる
do i = 1, N
if (A(i) - A(i + 1) > 1) then
write (*, '(i0)') A(i) - 1
stop
end if
end do
contains
recursive subroutine margesort(x, tmp, N, left, right)
integer left, right, mid
integer N
integer x(N), tmp(N)
integer i, j, k
if (left >= right) return
mid = (left + right)/2
call margesort(x, tmp, N, left, mid)
call margesort(x, tmp, N, mid + 1, right)
j = 0
tmp(left:mid) = x(left:mid)
do i = mid + 1, right
tmp(i) = x(right - j)
j = j + 1
end do
i = left
j = right
do k = left, right
if (tmp(i) > tmp(j)) then
x(k) = tmp(i)
i = i + 1
else if (tmp(i) == tmp(j)) then
x(k) = tmp(i)
i = i + 1
else
x(k) = tmp(j)
j = j - 1
end if
end do
end subroutine margesort
end program abc317b
C - Remembering the Days
問題
1 から N の番号がついた N 個の街と、1 から M の番号がついた M 本の道路があります。
i 番目の道路は街 $A_i$と街 $B_i$ を双方向に結び、長さは $C_i$ です。
好きな街からスタートして同じ街を二度以上通らずに別の街へ移動するときの、通る道路の長さの和としてありえる最大値を求めてください。
制約
- $2≤N≤10$
- $1≤M≤N(N−1)/2$
- $1≤A_i<B_i≤N$
- (A_i,B_i) は相異なる
- $1≤C_i≤10^8$
- 入力は全て整数である
詳細はこちらです。
解説
【注意点】
- $N=10$の時$M=45$であるため、繋がっていない道を含め総当たりでを調べると、TLEとなってしまします。
【フローチャート】
DFSを使って接続されている道の組み合わせを全て試し、最大値を求めます。
【補足】
※1
DFSを用いて接続している道を探し、通る道路の長さの和を求めます。
併せて、通る道路の長さの最大値を随時更新していきます。
始めに通る道の進行方向はA(i)とB(i)の２通りあることに注意が必要です。
最大値の更新にはMAX関数を使用します。
DFSの実装には再帰処理を用いたsubroutineを使用します。
再帰処理は、subroutineの前にrecursiveを入れること実装できます。
プログラム例
module ABC317c_mod
implicit none
! グローバル変数
integer(16), allocatable :: A(:), B(:), C(:)
integer(16) distance_max, M, N
end module
program ABC317c
use ABC317c_mod
implicit none
integer(16) i, distance
integer(16), allocatable :: visited(:)
!入力
read (*, *) N, M
allocate (A(M), B(M), C(M), visited(N))
do i = 1, M
read (*, *) A(i), B(i), C(i)
end do
!DFS
distance_max = 0
do i = 1, M
distance = 0; visited = 0; visited(A(i)) = 1
call move(B(i), i, distance, visited)
distance = 0; visited = 0; visited(B(i)) = 1
call move(A(i), i, distance, visited)
end do
write (*, '(i0)') distance_max
contains
!深さ優先探索
recursive subroutine move(current, route, distance, visited)
implicit none
integer(16) current, route, distance, visited(N)
integer(16) i, tmp(N), tmp2
!移動先が訪問済かどうか
visited(current) = 1
distance = distance + C(route)
distance_max = max(distance_max, distance)
!次の訪問先を調べる
do i = 1, M
if (current == A(i) .and. visited(B(i)) == 0) then
tmp = visited; tmp2 = distance
call move(B(i), i, distance, visited)
visited = tmp; distance = tmp2
end if
if (current == B(i) .and. visited(A(i)) == 0) then
tmp = visited; tmp2 = distance
call move(A(i), i, distance, visited)
visited = tmp; distance = tmp2
end if
end do
end subroutine
end program abc317c
感想
- C問題のDFSを書くのにかなり苦労しました。それぞれの問題の条件に落とし込んで実装するのがどうも上手くいきません...
- ABC316は公式でスキップされているのでありません。