目次
A - Tomorrow
問題
AtCoder 国では1年の暦が1 月から M 月までの M ヶ月間あり、１ヶ月は 1 日から D 日までの D 日間あります。
y 年 m 月 d 日の翌日は何年何月何日であるか求めてください。
制約
- $1000≤y≤9000$
- $1≤m≤M≤99$
- $1≤d≤D≤99$
- 入力は全て整数である
詳細はこちらです。
解説
現在の年月日が月末、年末であるかを順に調べ、該当する場合は年月日の繰り上げ処理を行います。
プログラム例
program abc331a
!MM ：1年間の月数
!DD ：1ヶ月の日数
!y,m,d： y 年 m 月 d 日
!cnt ：桁上がりの判定
implicit none
integer(16) MM, DD, y, m, d, cnt
!入力
read (*, *) MM, DD
read (*, *) y, m, d
!出力
cnt = 0
if (d >= DD) then
d = 1
m = m + 1
cnt = 1
end if
if (m >= MM) then
m = 1
y = y + 1
cnt = 1
end if
if (cnt == 0) then
write (*, '(i0,1x,i0,1x,i0)') y, m, d + 1
else
write (*, '(i0,1x,i0,1x,i0)') y, m, d
end if
end program abc331a
B - Buy One Carton of Milk
問題
卵 6 個入りのパックが S 円、卵 8 個入りのパックが M 円、卵 12 個入りのパックが L 円で売られています。
どのパックも何パックでも購入できるとき、N 個以上の卵を買うために必要な最小の金額を求めてください。
条件
- $1≤N≤100$
- L 以上、R以下であるどの整数Yでも$|X_i - A_i| ≤ |Y_i - A_i| $を満たす。
- A_1 ,A_2 ,…,A_N がすべて等しいということはない
制約
- $1≤N≤100$
- $1≤S,M,L≤10^4$
- 入力は全て整数である
詳細はこちらです。
解説
考えられる組み合わせを全て試し、最小の個数を求めます。
do文の３重ループを使い解きますか、N は最大でも１００と小さいためTLEにはなりません。
プログラム例
program abc331b
!S,M,L ：各パックの値段
!sn,mn,ln：各パックの購入個数
!N ：卵の必要個数
!nn ：購入した卵の個数
!p ：卵をnn個購入した際の金額
!minp ：条件を満たす最小の購入金額
implicit none
integer(16) N, S, M, L
integer(16) sn, mn, ln, minp, p, i, j, k, nn
read (*, *) N, S, M, L
minp = 1000000000
i = 0
do
ln = i
nn = ln*12
if (nn >= N) then
p = ln*L
minp = min(minp, p)
exit
end if
j = 0
do
mn = j
nn = ln*12 + mn*8
if (nn >= N) then
p = ln*L + mn*M
minp = min(minp, p)
exit
end if
k = 0
do
sn = k
nn = ln*12 + mn*8 + sn*6
if (nn >= N) then
p = ln*L + mn*M + sn*S
minp = min(minp, p)
exit
end if
k = k + 1
end do
j = j + 1
end do
i = i + 1
end do
write (*, *) minp
end program abc331b
C - Sum of Numbers Greater Than Me
問題
長さ N の数列 $A=(A_1,…,A_N)$ が与えられます。
$i=1,…,N$のそれぞれについて、$A$ の全要素の中で $A_i$ より大きな要素全ての和を求めよ。
- $1≤N≤2×10^5$
- $1≤A_i≤10^6$
- 入力は全て整数である
詳細はこちらです。
解説
$1≤N≤2×10^5$であるため、各$i$ ごとに$A_i$より大きな要素を 1〜N まで調べていると計算量が多くなりTLEとなります。
対策としてあらかじめ A を昇順に並べておき、尺取り法を使って和を求めることで、計算量を減らす工夫を行います。
プログラム例
program abc331c
!A(N) ：長さNの配列
!A2(N)：ソート後の配列A(N)
implicit none
integer(16) N, i, j, cnt
integer(16), allocatable::A(:), An(:), A2(:)
read (*, *) N
allocate (A(N), An(N), A2(N))
read (*, *) A(:)
do i = 1, N
An(i) = i
end do
call margesort(A, An, N)
cnt = sum(A)
do i = 1, N
if (i /= 1 .and. A(i) == A(i - 1)) then
A2(i) = cnt
cycle
else
cnt = cnt - A(i)
end if
do j = i + 1, N
if (A(i) < A(j)) exit
cnt = cnt - A(j)
end do
A2(i) = cnt
end do
call margesort(An, A2, N)
do i = 1, N
write (*, '(i0,1x)', advance='no') A2(i)
end do
contains
subroutine margesort(x, y, n)
integer(16) N
integer(16) x(N), tmp(N)
integer(16) y(N), tmp2(N)
integer(16) start, end
start = 1; end = N
call loop_margesort(x, y, tmp, tmp2, N, start, end)
end subroutine
recursive subroutine loop_margesort(x, y, tmp, tmp2, N, left, right)
integer(16) left, right, mid
integer(16) N
integer(16) x(N), tmp(N)
integer(16) y(N), tmp2(N)
integer(16) i, j, k
!これ以上2分かつできないならretrun
if (left >= right) return
!分割できるだけ分割する
mid = (left + right)/2
call loop_margesort(x, y, tmp, tmp2, N, left, mid)
call loop_margesort(x, y, tmp, tmp2, N, mid + 1, right)
!並び替えの下準備としてtmpに配列をコピー
j = 0
tmp(left:mid) = x(left:mid)
tmp2(left:mid) = y(left:mid)
do i = mid + 1, right
tmp(i) = x(right - j)
tmp2(i) = y(right - j)
j = j + 1
end do
!大小比較して小さい順に入れていく
i = left
j = right
!write (*, '(3x,*(f13.101x),a)', advance='no') x(left:right)
!write (*, '(a)', advance='no') '>>'
do k = left, right
if (tmp(i) < tmp(j)) then
x(k) = tmp(i)
y(k) = tmp2(i)
i = i + 1
else if (tmp(i) == tmp(j) .and. tmp2(i) < tmp2(j)) then
x(k) = tmp(i)
y(k) = tmp2(i)
i = i + 1
else
x(k) = tmp(j)
y(k) = tmp2(j)
j = j - 1
end if
end do
!write (*, '(3x,*(f13.10,1x))') x(left:right)
end subroutine loop_margesort
end program abc331c