WEB系エンジニアの勉強日記

Baby steps to Giant strides!

Atcoder Beginner Contest 034

abc034.contest.atcoder.jp

A, Bは問題なく解けた。

C

DPを用いた解き方が解らなかった。 経路の問題は苦手意識があって、ミニマムケースでも数えるのが苦手。 (w, h) への経路数は、(w-1, h) + (w, h-1) であると気づければ簡単に解くことができそう。 点の関係性を導き出すのが大事?

D

すべての組み合わせを試すのは計算量が爆発的に多くなってしまう。 nCk. ビンの優先順位をつける必要があると考えたが、どうやって優先順位をつけていいか解らずギブアップ。

ある目標のパーセントを決めることで、優先順位をつけることができるらしい。 優先順位が決まれば、組み合わせのパーセントも出せるので、目標値を満たすかどうかを判定することが可能になる。

目標値の決め方を二分法を用いることで、少ない試行数で十分な精度を満たす解法が可能。

考察

苦手な問題で思考停止になってしまったときは、早めに解説をみて数をこなすことで、いろいろな解法があると知っていくことが大事かな?