No Caffeine, No Life

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

パズル

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個…共通して存在しているのであ…

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 062 C:Chocolate Bar

問題: C: Chocolate Bar - AtCoder Beginner Contest 062 | AtCoder 解説: 長方形の分割は3つ、と決まっているので考えやすい。 ポイントは、1つの分割を決めたら、のこりの2つはなるべく縦または横の長さを均等にするのが最適であるということ。 解答…

ABC 063 C:Bugged

問題: C: Bugged - AtCoder Beginner Contest 063 | AtCoder 解説: 配点を昇順で整理したのち、 全部の和が10の倍数で無ければそのまま表示 10の倍数であったとき、配列のうち10の倍数で無いものの最小値を探し、それを引けばよい。 もしそういう1…

ABC 063 D:Widespread

問題: D: Widespread - AtCoder Beginner Contest 063 | AtCoder 解説: 解説通りに考えてみる。ポイントは、何回で問題の条件を満たすか探すのに二分探索を用いるところ。 解答例:

ABC 072 D:Derangement

問題: D: Derangement - AtCoder Beginner Contest 072 | AtCoder 解説: 実際に操作を行っていくだけでよい。 (難しく考えて手が止まってしまった…もっとシンプルに考えられるようになりたい。) 解答例:

ABC 072 C:Together

問題: C: Together - AtCoder Beginner Contest 072 | AtCoder 解説: 与えられた数列aに対して、 aの要素(ダブり無し)を求め aの要素が何個ずつ入っているかを格納するリスト(cnt)を導入。 cntにおいて、隣接する3つの数を足し合わせたものが答え。 ただ…

AOJ NTL_1_B:べき乗 (繰り返し自乗法)

問題: 繰り返し二乗法 | 整数論ライブラリ | Aizu Online Judge 解答: pythonの場合、pow(x, y, z)という組み込み関数が用意されており、それだけでも十分事足りる。(math ライブラリにあるpowはpow(x, y)と第三引数を考慮しないので注意) 一方、書籍通…

ABC070:Multiple Clocks (最大公約数と最小公倍数)

問題: C: Multiple Clocks - AtCoder Beginner Contest 070 | AtCoder 解答例: 複数個の整数に関する最小公倍数は、上記のようにすればよい。

Python3 Tips: 素数まわりの話

素数の判定法: