院試4日前だけど出ました。
久しぶりにTシャツを得た!
A. コンテスト名
プログラミングをします。
計算量:$O(|S|)$
Submission
B. セキュリティ
初期状態を含めたものについて実際にシュミレーションをして、0人になる瞬間があるかどうかを調べればよい。
計算量:$O(|S|)$
Submission
C. 右折
愚直に調べることを考える。これは一点を選択して遷移マスを決めれば良いので、$O(N^2M^2)$でできる。
遷移マスを決める際に欲しい情報はある列や行で合計何マス選択できるかであるから、これを事前に求めておけば、ある点を経由する組み合わせを積の和で求めることができる。
二次元累積和は使わなかった。
計算量:$O(NM)$
Submission
D. うほょじご
つまりある数字の組からなる遷移について、閉路があるかどうかを全ての組について調べれば良い。
組となる数字は$1000$を超えることが無いので実際に調べれば良い。この際以前に調べたことがある組は調べる必要がないので、メモ化再帰をすればすべての組は1回しか調べ無いことになる。
reverse(ごじょほう) ってこの記事を書いているときに気が付きました。
計算量:$O(NM)$
Submission
E. 迷路
脳死でダイクストラをしようとしたときに、ある頂点にいる時刻によって遷移が変わるのでこれを区別する必要を感じる。
しかしそれでは計算量が大きすぎるので考える。速くいればいるほど他の頂点に移動できうるのである時刻から次の移動方向までに必要な時間がわかれば、普通にダイクストラ法を適用できる。
これは文字列$S$の各要素をもとに、ある時刻において、上下左右に移動可能な最小の時間を求めることができるので解ける。
計算量:$O(K+(NM)log(NM))$
Submission
F. チーム分け
いつかのARCのgroupingみたいなdpをするというのはわかったけど条件がわからなかった。
以下解説をみた。
$sz$人で構成されるグループを作る際、$a[i]<sz$であるものはグループを作ることができないので考慮する必要はない。
グループを作る際にある人を振り分けた/振り分けていないという情報を持ちたいが$2^N$だけ情報を必要とするので無理。
そこで多い人数のグループからつくるとして、’割り振りが可能だが割り振られていない人数’という情報を持てば問題なく情報を少なくできる。(挿入dpでよく持ちがちな情報)
$dp[i][j]:=$最小$i$人までで構成されるグループを作り終え、今$j$人は割り振り可能だがまだ割り振っていないときの組合せ数
とする。$dp[N+1][0]$を起点にして、$dp[1][0]$が答えになる。遷移の組合せ数は$M$人から$sz*k$人選択してこれらを区別できない$k$個のグループに分ける、を式にすれば良い。
大きい方からグループをつくるとこれは調和級数的な操作になるので$O(N^3)$っぽいが$O(N^2logN)$になる。
計算量:$O(N^2logN)$
Submission