No Caffeine, No Life

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

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

再帰的に計算:

広告を非表示にする

ABC 056 D:No Need

問題:

D: No Need - AtCoder Beginner Contest 056 | AtCoder

解説:

ちょっと考えにくいと思う。Atcoderの解説では動的計画法を提案していたけれど、下記はもっとシンプルに考えている。

よい集合の中から「不要な数」を見つけるには、実際にそういう「よい集合」を作ってみたらよい。

与えられた数列{\displaystyle a }を昇順にソートする(それを改めて{\displaystyle a }としよう)。この時、大きい要素から足していき、{\displaystyle K }を超えるまで何個必要かカウントする。ここで得られた数列の部分集合({\displaystyle B = (b_{i}, b_{i+1} \ \dots b_{n} }と呼ぼう)に対し、残りの要素はあってもなくてもよい「不要な数」である。なぜなら、{\displaystyle B }の和がすでに{\displaystyle K }以上であるため、{\displaystyle a }の他の要素があってもなくても{\displaystyle K }以上を満たすので。

 また、{\displaystyle K }以上の要素に対しては考慮しなくてよい。なぜなら、そのカード1枚からなる部分集合(これは「よい集合」)に対し、それを除いてしまえば空集合となり、「よい集合」ではなくなってしまうから。

解答例:

 

広告を非表示にする

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

問題:

C: 経路 - AtCoder Beginner Contest 034 | AtCoder

解説:

 高校数学で習う公式を当てはめれば、求めたいのは{\displaystyle _{H+W-2} C _{H-1 } }とわかる。

道順の場合の数を求めるテクニック | 高校数学の美しい物語

ここでは、組み合わせの計算をするために逆関数を用いたかたちをとっている。

なお、pythonにおけるpow関数は、組み込み関数とmathモジュールにある関数の2つがある。このうち、pow(X, Y, Z)と3つの引数を取るのは組み込み関数の方なので注意が必要:

pow(xy[z])(原文)

x の y 乗を返します; z があれば、x の y 乗に対する z の剰余を返します (pow(x, y) % z より効率よく計算されます)。二引数の形式 pow(x, y) は、冪乗演算子を使った x**y と等価です。

引数は数値型でなくてはなりません。型混合の場合、二項算術演算における型強制規則が適用されます。 int 被演算子に対しては、第二引数が負でない限り、結果は (型強制後の) 被演算子と同じ型になります; 負の場合、全ての引数は浮動小数点に変換され、浮動小数点の結果が返されます。例えば、 10**2 は 100 を返しますが、 10**-2 は 0.01 を返します。第二引数が負の場合、第三引数は省略しなければなりません。 zがある場合、 x および y は整数型でなければならず、 y は非負でなくてはなりません。

一方で、mathモジュールの方は、

math.pow(xy)(原文)

x の y 乗を返します。例外的な場合については、 C99 標準の付録 ‘F’ に可能な限り従います。特に、 pow(1.0, x) と pow(x, 0.0) は、たとえ x が零や NaN でも、常に 1.0 を返します。もし x と y の両方が有限の値で、 x が負、 y が整数でない場合、 pow(x, y) は未定義で、 ValueError を送出します。

組み込みの ** 演算子と違って、 math.pow() は両方の引数を float 型に変換します。正確な整数の冪乗を計算するには ** もしくは組み込みの pow() 関数を使ってください。

 

解答例:

 

広告を非表示にする