AtCoder APG4bをPythonで解く(Ex19~21)-Shinoryo's Weblog

こんにちは, Shinoryoです.

今回はC++入門 AtCoder Programming Guide for beginners(APG4b)を, Pythonで無理やり解いてみた結果を書き連ねていこうと思います.

EX19 - 九九の採点

前提として, 「Pythonでは関数への引数は全て参照渡しされます」が, 「変数の型によって, 関数内で受けた変更が関数外で保存されるかどうかが変わります」.

この問題では, 関数内で受けた変更が関数外で保存されるmutable型を使うことによって, 記述することを考えます. 問題文でのプログラムと異なり, int型の変数「correct_count」「wrong_count」をまとめてリストにすることによって, プログラムを完成させることができます.

問題にあるプログラムをPythonで書き直すと以下のようになるでしょうか.

「count_report_num(children, x)」は, 組織番号xの子組織一覧children[x]をもとに, 提出する報告書の枚数を計算する関数です.

再帰関数を利用して報告書の枚数を求めます.

問題にあるプログラムをPythonで書き直すと以下のようになるでしょうか.

各関数における時間計算量は, 次のように計算されます.

ゆえに, 消すべきは「a4 = f4(n)」になります. しかし, Pythonでは計算が重いからかTLEになってしまいました.