- 2020.03.29
11.2 フィボナッチ数列をPythonで解いてみた
問題 AIZU ONLINE JUDGEのこの問題を参照。 解法 トップダウン(フィボナッチ数列のn番目の数値を算出するためのプロセスが最初に走り、そこからn-1番目の数値の算出プロセス、n-2番目の数値の算出プロセス...と処理していく方法)での実装をfibonacci, ボトムアップ(フィボナッチ数列2番目の数値の算出から開始し、n番目まで順に処理していく方式)での実装をroop_fibona […]
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
1/2ページ
- 2020.03.29
11.1 動的計画法の導入問題をPythonで解いてみた
問題 AIZU ONLINE JUDGEのこの問題を動的計画法を使用して解きます。 解法 既に計算した組み合わせの結果を辞書に格納しておき、再度の計算の手間を省くことで実行時間を削減できる。実際にそのようになるのか、動的計画法を使用していないverと使用したverで実行時間を比較してみた。 以下のコードを実行して実行時間を計測した。 動的計画法不使用ver 使用したコードはこの投稿で作成したもの。 […]
- 2020.03.29
6.3 コッホ曲線をPythonで解いてみた
問題 AIZU ONLINE JUDGEを参照 解法 解説はTBD.
- 2020.03.24
6.2 全探索をPythonで解いてみた
問題 総当たり 長さ n の数列 A と整数 m に対して、A の要素の中のいくつかの要素を足しあわせて m が作れるかどうかを判定するプログラムを作成してください。A の各要素は１度だけ使うことができます。数列 A が与えられたうえで、質問として q 個の mi が与えれるので、それぞれについて "yes" または "no" と出力してください。 入力 １行目に n、２行目に A を表す n 個 […]
- 2020.01.19
5.6 AllocationをPythonで解いてみた
問題 重さがそれぞれ wi(i=0,1,...n−1)のn 個の荷物が、ベルトコンベアから順番に流れてきます。これらの荷物を k台のトラックに積みます。各トラックには連続する 0 個以上の荷物を積むことができますが、それらの重さの和がトラックの最大積載量P を超えてはなりません。最大積載量 Pはすべてのトラックで共通です。n、k、wi が […]
- 2020.01.19
5.3 二分探索をPythonで解いてみた
問題 n個の整数を含む数列 Sと、q個の異なる整数を含む数列 Tを読み込み、Tに含まれる整数の中で Sに含まれるものの個数 C出力するプログラムを作成してください。ただし、Sの要素は昇順に整列されています。 https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/4/ALDS1_4_B 線形探索と同じ問題を二分探索を用いて解いてみます。 解法 […]
- 2020.01.19
5.2 線形探索をPythonで解いてみた
問題 n個の整数を含む数列 Sと、q個の異なる整数を含む数列 Tを読み込み、Tに含まれる整数の中で Sに含まれるものの個数 C出力するプログラムを作成してください。 https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/4/ALDS1_4_A 解法 1.forループを用いる方法 ただfor文を回して1要素ずつ比較を行う方法。上記コードの実行 […]
- 2020.01.19
4.4 双方向連結リストをPythonで解いてみた
問題 以下の命令を受けつける双方向連結リストを実装してください。 insert x: 連結リストの先頭にキー x を持つ要素を継ぎ足す。 delete x: キー x を持つ最初の要素を連結リストから削除する。そのような要素が存在しない場合は何もしない。 deleteFirst: リストの先頭の要素を削除する。 deleteLast: リストの末尾の要素を削 […]
- 2020.01.18
4.3 キューをPythonで解いてみた
問題 名前 namei と必要な処理時間 timei を持つ n 個のプロセスが順番に一列に並んでいます。ラウンドロビンスケジューリングと呼ばれる処理方法では、CPU がプロセスを順番に処理します。各プロセスは最大 q ms（これをクオンタムと呼びます）だけ処理が実行されます。q ms だけ処理を行っても、ま […]
- 2020.01.17
4.2 スタックをPythonで解いてみた
問題 逆ポーランド記法は、演算子をオペランドの後に記述する数式やプログラムを記述する記法です。例えば、一般的な中間記法で記述された数式 (1+2)*(5+4) は、逆ポーランド記法では 1 2 + 5 4 + * と記述されます。逆ポーランド記法では、中間記法で必要とした括弧が不要である、というメリットがあります。逆ポーランド記法で与えられた数式の計算結果を出力してください。 https://on […]