大和証券プログラミングコンテスト2024（AtCoder Beginner Contest 383） のB問題〜D問題をPythonで解説します。
提出コード
B問題
問題
画像の文字起こし
H*Wのマスがあります。マスには机と床があります。
床のマスから異なる2マスを選んで加湿器を置くとき、最も加湿される床のマス数を求めてください。
加湿器はマンハッタン距離がD内の床のマスを加湿します。
マンハッタン距離とは2点（X,y），（X,y）における|xーx'|＋|y-y'|です。
（1,1） と （1,5） のマスに加湿器を置くことが最も加します。
（1,1） ， （1,5） のマンハッタン距離は0（2,1）のマンハッタン距離は1です。
よって、加湿される床のマス数は3です。
アプローチ
画像の文字起こし
2つの加湿器を置く組み合わせを全パターン試して、最も加湿される組み合わせを探索します。
1つ目の加湿器は全ての床のマス、2つ目の加湿器は現在1つ目の加湿器が置かれていない床以外のマスを探索します。
加されるマスの探索も全探索します。
現在置かれている加湿器のマンハッタン距離内のマスを加湿されるマスとしてカウントします。
つまり3重ループの処理になります。
C問題
問題
画像の文字起こし
H*Wのマスがあります。マスには壁と床と加湿器があります。
加湿器は床を上下左右にD回以内で移動できる床のマスを加湿します。
加湿される床のマス数を求めてください。
アプローチ
画像の文字起こし
多始点BFSで解けます。
最初に加湿器の位置をキューに追加しBFSを始めます。
移動距離がD以内で届くマスを記録し、最後にそのマス数を出力します。
よって、5マスです。
BFSとは
画像の文字起こし
・幅優先探索です。
・近いところから順番に探す方法です。
・キューを使います。
D問題
問題
画像の文字起こし
N以下の正整数のうち、正の約数をちょうど9個持つものの個数を求めてください。
入力例 1
200
出力例1
3
36,100,196の3つです。
例えば、36の約数は 1,2,3,4,6,9, 12,18,36の9つです。
入力例2
4000000000000
出力例 2
407073
アプローチ
画像の文字起こし
N以下の約数の個数の求め方には公式があります。
Nの素因数分解を以下のように置きます。
N=Pi*P%*.. *Pi
約数の個数は次の公式で求められます。
（ei+1） * （ez+1） *…* （ek+1）
例えば12=（2^3）*（3^1）です。
よって約数の個数は（2+1）*（1＋1）=6となります。
実際に12の約数は 1,2,3,4,5,6,10,12の6個です。
正の約数が9個となるのは P^8の時とP^2*Q^2の時のみです。
P^8は（8+1）=9、P^2*Q^2は（2+1）*（2+1）=9です。
あとは、Pは素数なので、素数一覧をループします。
ループ範囲は、Nまでで十分です。P^2*Q^2＜＝Nより、P,q＜＝Nとなります。
素数一覧はPythonだと sympy.primerange が便利です。
primerange(start, end)
primerange(10, 50) = [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
素数をループして、P^8＜=NもしくはP^2*Q^2＜=Nに当てはまる数をカウントします。