No Caffeine, No Life

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

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() 関数を使ってください。

 

解答例:

 

広告を非表示にする

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

問題:

D: 大ジャンプ - AtCoder Beginner Contest 011 | AtCoder

解説:

目的地{\displaystyle (X, Y) }{\displaystyle D }で規格化する。すると、{\displaystyle N }回のうち、{\displaystyle X }方向、{\displaystyle Y }方向に正味でどれだけ動けばよいかが、まず求められる。

  • {\displaystyle X }方向に動く回数を{\displaystyle u }方向
  • {\displaystyle Y }方向に動く回数を{\displaystyle v }方向
  • と、おくと、{\displaystyle u + v = N }

ここで、{\displaystyle u, \ v }{\displaystyle x, \ y }と、異なっていてよい。というのも、負方向への移動が可能なので、行きすぎたら戻ってきて、ということもありえるから。ただし、そのために{\displaystyle u }{\displaystyle x }、または{\displaystyle v }{\displaystyle y }の差は必ず偶数で無いといけない。

最後に、組み合わせ(combination。いわゆる{\displaystyle _{n} C _{r} })を計算する。ここでは、ガンマ関数の自然対数(lgamma)を経由して、計算している。

※ガンマ関数については、

ガンマ関数(階乗の一般化)の定義と性質 | 高校数学の美しい物語

を参照。

解答例:

広告を非表示にする

ABC 011 C:123引き算 貪欲法

問題:

C: 123引き算 - AtCoder Beginner Contest 011 | AtCoder

解説:

禁止された数値のリストlに引っかからない限り、なるべく大きく数を引いていく。(つまり、3, 2, 1の順に優先。)これは、引く回数が100回までと決まっているので、とにかく、なるべく大きく引いて0に近づけていった方が効率的なので。

解答例:

広告を非表示にする

ABC 074 C:Sugar Water

問題:

C: Sugar Water - AtCoder Beginner Contest 074 | AtCoder

解説:

  • 時間制限が3秒
  • 全体的に数値が小さい

のを理由に、全探索することを考えた。つまり、操作1, 2, 3 ,4の回数をa, b, c, dとしたとき、

  • {\displaystyle 100A * a + 100B * b + C * c + D * d \leq F}
  • {\displaystyle C * c + D * d \leq E}

を満たすようなa, b, c, d を探し、該当する組に対し、濃度を計算し、保存(解答例中のmemo)。a,b,c,dは、与えられた不等式より、せいぜい

  • {\displaystyle 0 \leq a, b \leq 30}
  • {\displaystyle 0 \leq c, d \leq 100}

であることがわかる。(したがって、全探索する場合は31 x 31 x 101 x 101 ~ 1,000,000...基本的には大丈夫なはず、と検討がつく)

考え方はこれでよかったのだけれど、本番中は致命的な勘違いをしていてダメだった…のが痛い。速く正確に、というのはとても大事な要素だと思うけれど、これは練習でもちゃんと鍛えていかないといけないな、とは思う。

解答例:

広告を非表示にする