No Caffeine, No Life

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

ABC 082 C: Good Sequence

問題:

C: Good Sequence - AtCoder Beginner Contest 082 | AtCoder

解説:

Counterを用いて、各要素の個数を出す。各keyに対して個数(value)が大きければ、その差を加え、valueが小さければすべて取り除くことをすればよい。

解答例:

広告を非表示にする

ABC 082 B: Two Anagrams

問題:

B: Two Anagrams - AtCoder Beginner Contest 082 | AtCoder

解説:

題意を満たす例があればよいので、片方を昇順に、片方を降順に並べ替えた場合を検討し、題意を満たしていればよい。

解答例:

広告を非表示にする

ABC 053 B: A to Z String

問題:

B: A to Z String - AtCoder Beginner Contest 053 | AtCoder

解説:

Aについて、最も早く出てくるインデックスを求める。

Zについては、最も遅くに出てくるインデックスを求める。

pythonでは、find / rfindメソッドが有効。

Pythonを学ぼう 第19回 文字列の操作 - ほぷしぃ

解答例:

 

広告を非表示にする

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番目の例は、

  • ある点と点がつながっている状態を1、そうでなければ0

と表現すると、すべての点がつながっている状態は順列間の積で表されることに注目している。(すべてつながっていれば、1 x 1 x 1 x ... x 1 = 1となるが、どこかがつながっていなければ x 0 が入り、= 0となる。これがそのまま、場合の数として使える)

2番目の例は、もう少し素直に、深さ優先探索を用いている。

3番目の例は、ビット演算を用いている。

解答例:

積を用いた方法:

深さ優先探索

ビット演算を用いた方法:

 

広告を非表示にする

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モジュールを使用:

再帰的に計算:

広告を非表示にする