keyword 幅優先探索 C++ 問題概要 サイズ5*5のボードが与えられ、そのうちN( 解法 全状態が(25,5)通りしかないので探索が間に合う。書くだけ。 感想 最初はN(vector突っ込んでも間に合うと思う。あと相変わらず実装が遅すぎる。

keyword シミュレーション 確率 C++ 問題概要 ロボットが東西南北の方向にある確率で移動する。n( 解法 nが小さいのがどう見ても怪しい。普通にDFSしたとき、既に訪ねたところには移動しないので最大でも分岐は3つ(初手を除く)。なのでシミュレーションして…

keyword メモ化再帰 C++ 問題概要 ミッションがN( 解法 memo[知性][体力]としてメモ化再帰で解く。ただし、素朴にやるとO(M^2 * (M+N))となってTLEする。ここで、知性や体力を中途半端に割り振る必要がないことに着目して、座標圧縮風に知性か体力のどっちか…

keyword 整数 10進数 C++ 問題概要 整数N( 解法 素因数分解したとき10以上の素数があれば不可能。そうでないときは、桁数を縮めるように8,9,6,4の順で割っていく。

keyword 整数 C++ 問題概要 Y, Dが与えられたときR=Y%Dに対してR*P=0 (mod D)を満たす最小のP(>0)を求める問題。 解法 RとDが互いに素ならP=Dが答えになることは自明。なのでRとDを最大公約数で割ってやる。もちろん問題の読解が一番難しい。

keyword シミュレーション C++ 問題概要 (0,0)の地点に北を向いた人がいる。C=1とする。その人はK( 向きにしたがってCだけ歩き、右を向く。 C = digitRoot(C*multi)とする。 最終的な座標を求める問題。 解法 状態は向きとCで考えても9*4通りしかないのでル…

keyword 平面幾何 二分探索 C++ 問題概要 2次元平面上にN(=0)を求める問題。 解法 答えに関して二分探索する。できるかどうかの判定は、自分の解き方だとx_i(t)-x_j(t)が二分探索中の値に等しくなるような時刻を求めて、その時刻で他の点が含まれているかど…

keyword 期待値 Greedy C++ 問題概要 数列0,1,...,N-1(NK-1が自分の手元に来るようにしたい。最善を尽くしたとき、いくつ得ることができるの期待値を求める問題。 解法 期待値の問題ではお馴染みの線形性を使う。置換をS回シミュレートして、数字jがi_1, i_2…