No Caffeine, No Life

プログラミング(主にPython)

python

ABC 054 D:Mixing Experiment 動的計画法

問題: D: Mixing Experiment - AtCoder Beginner Contest 054 | AtCoder 解説: editorialにあるように、変数やdp tableを設定してみる。 (3重リストを用いている) 解答例:

ABC 054 C:One-stroke Path 動的計画法 メモ化再帰 ビットdp

問題: C: One-stroke Path - AtCoder Beginner Contest 054 | AtCoder 解説: 頂点の数がとても少ないので、頂点の数におけるすべての順列において、すべての点をたどることができるかを深さ優先探索(dfs)で探っていく。 1番目の例は、 ある点と点がつなが…

ABC 055 C:Scc Puzzle

問題: C: Scc Puzzle - AtCoder Beginner Contest 055 | AtCoder 解説: sがcの2倍以上あるときは、sを全部使ってsccを作る。 sがcの2倍未満であるときは、sが余るので、c // 2の分が最大。 解答例:

ABC 055 B:Training Camp 階乗の計算

問題: B: Training Camp - AtCoder Beginner Contest 055 | AtCoder 解説: mathモジュールにもfactorial関数があるけれど、実際には再帰的に計算する方が速かった。前者の解答例が230msに対し、後者は40ms。 解答例: mathモジュールを使用: 再帰的に計算…

ABC 056 D:No Need

問題: D: No Need - AtCoder Beginner Contest 056 | AtCoder 解説: ちょっと考えにくいと思う。Atcoderの解説では動的計画法を提案していたけれど、下記はもっとシンプルに考えている。 よい集合の中から「不要な数」を見つけるには、実際にそういう「よ…

ABC 034 C:経路 組み合わせ・順列の計算

問題: C: 経路 - AtCoder Beginner Contest 034 | AtCoder 解説: 高校数学で習う公式を当てはめれば、求めたいのはとわかる。 道順の場合の数を求めるテクニック | 高校数学の美しい物語 ここでは、組み合わせの計算をするために逆関数を用いたかたちをと…

ABC 011 D:大ジャンプ 組み合わせ・順列の計算

問題: D: 大ジャンプ - AtCoder Beginner Contest 011 | AtCoder 解説: 目的地をで規格化する。すると、回のうち、方向、方向に正味でどれだけ動けばよいかが、まず求められる。 方向に動く回数を方向 方向に動く回数を方向 と、おくと、 ここで、 はと、…

ABC 011 C:123引き算 貪欲法

問題: C: 123引き算 - AtCoder Beginner Contest 011 | AtCoder 解説: 禁止された数値のリストlに引っかからない限り、なるべく大きく数を引いていく。(つまり、3, 2, 1の順に優先。)これは、引く回数が100回までと決まっているので、とにかく、なるべ…

ABC 074 C:Sugar Water

問題: C: Sugar Water - AtCoder Beginner Contest 074 | AtCoder 解説: 時間制限が3秒 全体的に数値が小さい のを理由に、全探索することを考えた。つまり、操作1, 2, 3 ,4の回数をa, b, c, dとしたとき、 を満たすようなa, b, c, d を探し、該当する組…

ABC 057 D:Maximum Average Sets

問題: D: Maximum Average Sets - AtCoder Beginner Contest 057 | AtCoder 解説: 与えられた数列に対し、選んだ平均値が大きくなるためには、大きい順に並び変えて、上から選んでいけば良い。 最大となる平均値の場合に対し、重複を許した順列を計算すれ…

ABC 057 C:Digits in Multiplication

問題: C: Digits in Multiplication - AtCoder Beginner Contest 057 | AtCoder 解説: 桁数の取得は、素直に対数を用いればよい。 解答例:

ABC 069 D:Grid Coloring

問題: D: Grid Coloring - AtCoder Beginner Contest 069 | AtCoder 解説: 気づけば難しくない。(つまり、気づかないと難しい?) 解答例:

ABC 064 D:Insertion

問題: D: Insertion - AtCoder Beginner Contest 064 | AtCoder 解説: 考え方として、 正しいかっこ列の時、' ( ' と' ) 'の数は等しい そこで、' ( 'の数と、' ) 'がそれぞれいくらあるか考える。 文字列の左から、' ( 'の数をカウントしていく。途中、' …

ABC 062 D:3N Numbers

問題: D: 3N Numbers - AtCoder Beginner Contest 062 | AtCoder 解説: 詳しい考え方は、atcoderの解説を参照。その解説通りに組んでみたのが解答例。 個人的には、ポイントは 前半から個()の選んだ中で、大きい順に個の和を計算(もしくは小さい順に個の…

ABC 059 D:Alice&Brown

問題: D: Alice&Brown - AtCoder Beginner Contest 059 | AtCoder 解説: これは気づくかどうか…。 解答例:

ABC 058 D:井井井 / ### 算数(因数分解)

問題: D: 井井井 / ### - AtCoder Beginner Contest 058 | AtCoder 解説: 解答例にあるように、summationのまとめ方がポイント。 こういう、算数中心の問題は好き。(というよりも、純粋なアルゴリズムの問題だと刃が立たないから、ではあるのだが。。。)…

ABC 058 怪文書 / Dubious Document

問題: C: 怪文書 / Dubious Document - AtCoder Beginner Contest 058 | AtCoder 解説: 各列に共通な文字を探し出し、それを辞書順に、必要な個数だけ表示すればよい。 (例えば、n個の文字列中に、aが1個、bが2個、cが4個…共通して存在しているのであ…

AOJ ALDS1_10_C:最長共通部分列 (LCS: Longest Common Subsequence)  動的計画法

問題: 最長共通部分列 | アルゴリズムとデータ構造 | Aizu Online Judge 解説: 「普通の」アルゴリズムはこちら: 最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリー が、下記にあるように、最長共通部分列の「長さ」だけを求め…

AOJ DPL_1_E:編集距離 Levenshtein Distance

問題: Edit Distance (Levenshtein Distance) | Aizu Online Judge 解説: いまさら編集距離 (Levenshtein Distance) を実装するぜ | takuti.me こんなふうにわかりやすく書けるなんてすごいなぁ…。 解答例: 上記そのままですが…。 ちなみに、pythonにはLe…

AOJ DPL_1_C:ナップザック問題 (同じ種類の品物はいくつでも選ぶことができる場合) 動的計画法

問題: Knapsack Problem | Aizu Online Judge 解説: 最もシンプルな場合と同じように、 :種類の品物を用いて大きさのナップザックに入れる場合の価値の最大値 :品物の価値と重さのリスト と置いたとき、は、 の、最大値で決まる。(この3点目が、重複を…

AOJ DPL_1_B:ナップザック問題 動的計画法

問題: ナップザック問題 | 動的計画法 | Aizu Online Judge 解説: :種類の品物を用いて大きさのナップザックに入れる場合の価値の最大値 :品物の価値と重さのリスト と置いたとき、は、 の、最大値で決まる。 解答例:

AOJ DPL_3_B:最大長方形 (Largest Rectangle) 動的計画法

問題: 最大長方形 | 動的計画法 | Aizu Online Judge 解説: 与えられた盤面に対し、 「(縦に見て)連続してきれいなマス目が何個並んでいるか」をカウント。それを「ヒストグラム」とみなして、 ヒストグラムに内接する最大の長方形を割り出す という具合…

Python3 Tips:リスト、タプル、辞書にまつわるヒント

リスト:二次元配列から最大値を取り出す 形式: l = [ [0,1,2,3,4], [5,6,7,8,9], [10,11,12,13,14] ] のような二次元配列から最大値を取り出す。 入力:

AOJ DPL_3_A:最大正方形(Largest Square) 動的計画法

問題: 最大正方形 | 動的計画法 | Aizu Online Judge 解説: :位置から見て、左上に向かってできる最大の正方形の数 このように設定したとき、は、左上( )、左( )、上( )から決定される。すなわち、左上、左、上の要素の最小値+1となる: 解答例:

Python3 Tips:入出力のヒント

1行に文字列1つの入力 形式: ※Sは文字列 問題例: B: OddString - AtCoder Beginner Contest 072 | AtCoder 入力: 1行にスペース区切りで複数の整数または浮動小数点数の入力 形式: ※A,B,Cは,いずれも整数または浮動小数点数. 問題例: A: Sandglass2…

ABC 073 D - joisino's travel:ダイクストラ法、ワーシャルフロイド法、組み合わせ(itertools)

問題: D: joisino's travel - AtCoder Beginner Contest 073 | AtCoder 解説: 訪れる町が個と少ない。そこで、全通りの順列を全探索。 各点から各点への最短距離はダイクストラ法で求める。負の距離が無いし。 と、コンテスト中は考えた。これでうまくいく…

ABC 060 D:Simple Knapsack 全探索(直積集合)、動的計画法(メモ化再帰)

問題: D: Simple Knapsack - AtCoder Beginner Contest 060 | AtCoder 解説: 問題の解説にあるように、今回は重さの範囲が限定されている(w0 <= wi <= w0+3)ので、それを考慮すると全探索することができる。すなわち、 重さは全部で4通り。 その4通りに…

ABC 060 C:Sentou

問題: C: Sentou - AtCoder Beginner Contest 060 | AtCoder 解説: スイッチを押したときに、前回スイッチを押してからお湯が出続けている間とダブっている分を引き算…というかたちで解いた。 でもこれはややこしい。もっと単純に、(解説にあるように)こ…

ABC 060 B:Choose Integers 初等整数論:不定方程式の解

問題: B: Choose Integers - AtCoder Beginner Contest 060 | AtCoder 解説: 一次不定方程式ax+by=cの整数解 | 高校数学の美しい物語 解答例:

ABC 061 D:Score Attack ベルマンフォード法

問題: D: Score Attack - AtCoder Beginner Contest 061 | AtCoder 解説: ベルマンフォード法を使うために、辺のコストをすべて負とする。(答えは、得られた最小値 x -1 ) 閉路が検出されれば、それがinfの場合。普通のベルマンフォードの法と異なり、終…