A - Weekly Records
問題
1から9 までの数字が書かれた 3×3の盤面の中に、A,Bを配置します。
配置したA,Bについて、隣り合う位置にあるかを調べ、"Yes"or"No"を出力します。
制約
- $1≤A<B≤9$
- A,B は整数である。
- 隣り合う位置はA,Bが"左右"に並んでいる場合のみを指します。
詳細はこちらです。
解説
【フローチャート】
【補足】
※1
3*3の盤面であるため、3,4と6,7は隣り合う形になりません。
従って、Aが３、６の時にはどうやっても隣り合うことはないため、Noとなります。
プログラム例
program ABC309a
implicit none
integer(8) A, B
!初期化
A = 0; B = 0
!入力
read (*, *) A, B
!処理
if (A /= 3 .and. A /= 6) then !3と6の時は盤面の隅なので対象外
if (A + 1 == B) then
write (*, "(a)") 'Yes'
stop
end if
end if
!結果の出力
write (*, "(a)") 'No'
end
B - Default Price
問題
N 行 N 列の盤面のうち、外周のみを時計回りに動かした盤面を出力します。
制約
- $2≤N≤100$
- $0≤A_{i,j}≤1(1≤i,j≤N)$
- 入力は全て1か0の整数
詳細はこちらです。
解説
【フローチャート】
【補足】
※1
Aは区切りのない数字で用意されています。
何もせずにread文を使い数字として読み込むと、区切りがないため、以下の様に読み込んでしまいます。
A(1)=101
A(2)=1101
A(3)=1111
A(4)=0000
今回は１文字ずつ区切って盤面を配列に構成したいため、 read (*, '(*(i1))')により書式を指定して読み込みました。
※2
時計回りで回転させた盤面をBに作ります。
外周以外はそのままで良いので、B=Aを行い一括して配列の中身をコピーします。
外周もそのままコピーされしまいますが、後の処理で値は上書きするので問題ありません。
※3
２重のdoループを用いて、回転させた後の盤面Bを１マスずつ作成します。
※4
対象のマスを横方向に１つ移動させます。
対象となるマスは、1行目かN行目のマスです。
ただし、$B(1,1)$と $B(N,N)$は縦方向にマスを移動させる必要があるため、if文を用いて判定から除外する必要があります。
※5
対象のマスを縦方向に１つ移動させます。
対象となるマスは、1列目かN列目のマスです。
ただし、$B(1,N)$と $B(N,1)$は横方向にマスを移動させる必要があるため、if文を用いて判定から除外する必要があります。
プログラム例
program ABC309b
implicit none
integer i, j
integer N
integer, allocatable :: A(:, :), B(:, :)
!初期化
i = 0; j = 0; N = 0
!入力
read (*, *) N
allocate (A(N, N), B(N, N))
do i = 1, N
read (*, '(*(i1))') (A(i, j), j=1, N) !1文字区切りで入力
end do
!時計回りに回転
B = A
do i = 1, N
do j = 1, N
!横の移動
if (i == 1 .and. j /= 1) then
B(1, j) = A(1, j - 1)
else if (i == N .and. j /= N) then
B(N, j) = A(N, j + 1)
end if
!縦の移動
if (j == 1 .and. i /= N) then
B(i, 1) = A(i + 1, 1)
elseif (j == N .and. i /= 1) then
B(i, N) = A(i - 1, N)
end if
end do
end do
!結果の出力
do i = 1, N
write (*, '(*(i1))') (B(i, j), j=1, N)
end do
end
C - Medicine
問題
N種類の薬を処方されました。
それぞれの薬は、1日に飲む錠数 $b_i$錠 と 飲み続ける日数 $a_i$日が異なります。
1日に飲む錠数の総数がK個以下となるには何日必要かを求めます。
制約
- $1≤N≤3×10^5$
- $0≤K≤10^9$
- $1≤a_i,b_i≤10^9$
詳細はこちらです。
解説
【注意点】
-
この問題は、$1≤a_i,b_i≤10^9$です。
そのため、Do文を使って1日ずつ薬の飲む数を調べるとTLEになります。
また、日毎にDo文を使って飲む数を毎回調べるとTLEになります。 -
$0≤K≤10^9$であるため、a,bの数に関わらず、1日目からK以下となる場合があります。
【フローチャート】
※1
$1≤a_i,b_i≤10^9$であるため、その日飲む薬の総数についてaを全て調べ求めるとTLEになってしまいます。
そこで、予め1日で飲む薬の最大数を調べておき、そこからA(i)日経過した時にb(i)錠だけ薬の数を減らすアプローチを取ります。
この方法は、その日に飲み切る薬のみを減らすだけで、その日飲む薬の総数を求める事ができます。
この処理を実装するために、a,bの入力時に1日で飲む薬の最大数を調べておきます。
※2
※1で示した内容を実践するためには、aは昇順に並んでいる必要があります。
今回はクイックソートを使用して並び替えを行いました。
なお、クイックソートは安定ソートではないため、同日内で薬の切れる順が前後する可能性があります。
ですが今回の場合は、薬の切れる順番は見ていないため問題ありません。
※3
1日目からK以下となっている場合を考慮し、先に判定を行います。
※4
その日飲む薬の総数は、$a(i)+1$日目から$a(i+1)+1$日目までは変化しません。
なぜなら、飲む薬の種類が変化しないからです。
従って、経過日数はa(i)ごとに見ていきます。
プログラム例
program ABC309c
implicit none
integer(8) i
integer(8) N, K, tmp
integer(8), allocatable ::a(:), b(:)
!初期化
i = 0; tmp = 0
!入力
read (*, *) N, K
allocate (a(N), b(N))
do i = 1, N
read (*, *) a(i), b(i)
tmp = tmp + b(i)
end do
!昇順にソート
call quicksort(a, b, 1, N, N)
! 1 日目：飲む薬がK以下かどうか
if (tmp <= K) then
write (*, '(i0)') 1
stop
end if
! i 日目：飲む薬がK以下かどうか
do i = 1, N
tmp = tmp - b(i)
if (tmp <= K) then
write (*, '(i0)') a(i) + 1
stop
end if
end do
end program
!sub:クイックソート
recursive subroutine quicksort(a, b, first, last, N)
implicit none
integer(8) N
integer(8) a(N), b(N), i, j, tmp1, tmp2
integer(8) first, last, center
i = first
j = last
center = a(int((first + last)/2))
do
do while (a(i) < center)
i = i + 1
end do
do while (center < a(j))
j = j - 1
end do
if (i > j) then
exit
else if (i == j) then
exit
end if
tmp1 = a(i); a(i) = a(j); a(j) = tmp1
tmp2 = b(i); b(i) = b(j); b(j) = tmp2
i = i + 1
j = j - 1
end do
if (first < i - 1) call quicksort(a, b, first, i - 1, N)
if (j + 1 < last) call quicksort(a, b, j + 1, last, N)
end subroutine quicksort
感想
- A問題、隣り合う縦の数も調べていました。２次元の盤面だったので、勝手に縦も調べないといけないと錯覚していました。
- A問題に手間取ったので、B問題をギリギリ解いて終了でした。時間的にギリギリな中、落ち着いて問題を解けたのはよかったです。