パナソニックプログラミングコンテスト(AtCoder Beginner Contest 195)をPythonで解く

こんにちは, Shinoryoです.

今回はパナソニックプログラミングコンテスト(AtCoder Beginner Contest 195)を, Pythonで解いてみた結果を書き連ねていこうと思います.

A - Health M Death

条件を書いてif文で分岐させれば問題ないです.

B - Many Oranges

最も少ない個数$\mathrm{lower}$は, $B$グラムのみかんで$W$キログラム以上となるようにし, オーバーした分はより軽いみかんに置き換えることで得られます. 具体的には, $1000 W / B$の小数点以下を切り上げることによって得られます.

最も多い個数$\mathrm{upper}$は, $A$グラムのみかんで$W$キログラム以下となるようにし, 足りない分はより重いみかんに置き換えることで得られます. 具体的には, $1000 W / A$の小数点以下を切り捨てることによって得られます.

切り上げ, 切り捨ての計算は, mathモジュールのceil()(切り上げ), floor()(切り捨て)を用いると楽です. 整数int型が返されます.

なお, $\mathrm{lower} > \mathrm{upper}$の場合は, オーバーした分はより軽いみかんに置き換えても$W$キログラムにならない場合に相当します.

C - Comma

一般に, $10^{3i}$から$10^{3(i+1)} - 1$までのコンマの数は,

で得られます^*1. $N$の桁数$D$に関して, $D - 1$を$3$で割った商を$A$とすると, $1$から$A$までの$i$に関して$\mathrm{ans}_i$を合計することによって, $1$から$10^{3A} - 1$までのコンマの数を得ることができます. $10^{3A}$からのコンマの数は, 別に求める必要があります.

$A = 0, 1$の場合も, range()の性質から, 同様のコードで求めることができます.

D - Shipping Center

価値の大きい荷物から順に, できる限り容量の小さい箱に詰めていくことで, 荷物の価値の合計が最大になります.

価値の大きい荷物から順に調べていく際に, $W$と$V$の値を格納した2次元配列を, $V$の大きい順にソートする必要が出てくるかと思います. 多次元リストのソートでは, 1番目の値から順に比較されますので, $V$の値を先頭にしておいた方が楽でしょう^*2.

下のコードでは, すでに荷物を入れた箱を, 使える箱のリストから除外するにあたって, del文を使用しています. もちろん, インデックスでスライスして上書きしても構わないと思います.

E以降

E以降は私の能力不足故に省略いたします.

参考にしたサイト等

• 「解説 - パナソニックプログラミングコンテスト(AtCoder Beginner Contest 195)」
  Editorial - Panasonic Programming Contest (AtCoder Beginner Contest 195)

  AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

• nkmk様による「Pythonで小数点以下を切り捨て・切り上げ: math.floor(), math.ceil()」
  Pythonで小数点以下を切り捨て・切り上げ: math.floor(), math.ceil() | note.nkmk.me

  Pythonで浮動小数点数floatの小数点以下を切り捨て・切り上げするには, 標準ライブラリmathモジュールのfloor(), ceil()を使う. math.floor() --- 数学関数 — Python 3.8.1rc1 ドキュメント math.ceil() --- 数学関数 — Python 3.8.1rc1 ドキュメント ここでは以下の内容について説明する. 小数点以下を切り捨て: math.fl...

• nkmk様による「Pythonでリスト（配列）の要素を削除するclear, pop, remove, del」
  Pythonでリスト（配列）の要素を削除するclear, pop, remove, del | note.nkmk.me

  Pythonでlist型のリスト（配列）の要素を削除するには, リストのメソッドclear(), pop(), remove()を使う. そのほか, インデックスやスライスで位置・範囲を指定してdel文で削除する方法もある. すべての要素を削除: clear() 指定した位置の要素を削除し, 値を取得: pop() 指定した値と同じ要素を検索し, 最初の要素を削除:...

脚注

*1 :$10^{3i}$から$10^{3(i+1)} - 1$までの自然数には, それぞれ$i$個のコンマがつくということを表した式になります. 例えば, $1,000$から$999,999$までの自然数には, コンマが$1$個つきます. $1,000,000$から$999,999,999$までの自然数には, コンマが$2$個つきます.

*2 :APG4bのEX-22に, 多次元配列のソートに関連した問題があります.