AtCoder Regular Contest 075 E - Meaningful Mean
数列が与えられる。連続部分列の平均値がK以上であるような部分列は何通りあるか？
まずすぐ分かることはすべての要素からKを引くと、部分列の和が0以上になるような組み合わせをカウントすればよい。これはO(N^2)であれば、累積和を使ってカウントできる。
ただし計算量の問題があるので、累積和をsum[i]などと書くと、sum[0]～sum[i - 1]までにsum[i]以下の物が何通りあるか、というのをO(logN)以下で計算する必要がある。これは結構よく見るテクで、値そのものをIndexに持つセグメント木 or BITを使うと良い。ただし、値をIndexに持つので、値自体はO(10^6)以下でなければならないため座標圧縮を用いる。
すると、例えばBITを用いて、BIT.sum(sum[i])の和を取りつつ、sum[i]番目のBITにどんどん1を足していく、というループを回すと答えになる。O(N logN)。
このBITやセグメント木に配列の値そのものをインデックスとして持つ、みたいなテクニックは以前見たことあったのだけど、思い出せなかった。
画像認識 (機械学習プロフェッショナルシリーズ) レビュー
比較的新しい画像認識の本。ただ構成が独特で、画像認識の一般論といった基礎を一通り解説したあとに具体的なアルゴリズムの品揃えが定番から最新のものまで幅広く載っている本。
画像に限らないパターン認識の名著としては「はじめてのパターン認識」という本があるのですが、こちらは一般的な概念等は学習済みとして、アルゴリズムの解説にに特化した本です。一方で本書はまず概念を説明し、その上で各種アルゴリズムの解説をするので一応ゼロから始める人でも理論的には読めてしまう内容。ただし、結構真面目にかいてあるので、いわゆる「何となく概念が分かる系」の解説本のつもりでは読まないほうがいいかもです。
厳密に言えば画像認識ではないですが、画像生成として最近DCGANというモデルが流行っています(すでに過去形かも？)これについても軽く触れてあり、画像認識をだいたい俯瞰できるとてもいい本です。
最近のディープラーニング系の本は解説が適当であったり、概念しか説明していなかったりといった本が結構出ているので、真面目にこういう本を読んでみるのはおすすめです。
AtCoder Regular Contest 075 D - Widespread
魔物の体力s[1]～s[N]が与えられる。一回の魔法攻撃で、特定の一つの魔物の体力をA削り、その他すべての魔物の体力をB削る。ただしA>Bとする。全滅させるには魔法攻撃を最低何回打てばよいか？
C=A-Bとする。魔法攻撃の回数をkとした時、すべての魔物は少なくともkBの体力が削られている。s[i] - kB > 0 であるような各iについて、(s[i] - kB) / C (ただし切り上げ)を計算して和を取ると、その敵に対してAの攻撃を何回当てれば体力が0になるかが算出される。この回数の合計がkより少なければ少なくともk回の魔法攻撃では魔物の全滅させることが可能である。そこで、kを二分探索する。O(N log(max(s[i]))。
Educational Codeforces Round 22 C. The Tag Game
木の2個の頂点にAさん及びBさんがいる。AさんがBさんを追いかけ、BさんはAさんから逃げるという目的で行動を最適化するとき、AさんがBさんに追いつく手数を求めよ。その場にとどまるのもありとし、Bさんが先手とする。
Aさん及びBさんがいる地点からの距離を全列挙する。この時、木の性質としてある2個の地点間の最短距離はただひとつのルートしかいない、という性質を使うと、ある頂点pに於いて、d(A, p) > d(B, p) であれば、その頂点にBさんは来ることが可能になる。なぜならそこまでの経路上の点qに於いて、d(A, q) <= d(B, q)という点があったとすると、先述の性質によりqはB-p間の最短経路上の点になりえず、Bさんがまっすぐそこに向かえばqは通らないからである。
なので、Bさんとしてはd(A, p) < d(B, p) であるような点のうち、最長の点に行くという行動を取るのが最適になり、Aさんはそこにまっすぐ向かい追いついた時点でゲーム終了となる。O(N)。
コーナーケースとして、初期位置からAとBが重なっている場合は0になる。
Yukicoder 524 コイン
N(0<N<2^32)枚のお皿に1個、2個、…、N個の石が入ったNIMを行う。先手の勝ち負けを判定せよ。
Editorial読むと単なる実験ゲーでmod4 = 3を出すだけ。
ここでは自分で解いた時の考察を残す。
NIMなのでGrundy数を計算する。Grundy数は1 xor 2 xor 3 xor ... xor Nであり、これが0なら先手の負け、それ以外は勝ちである。
ただし、Nが大きいのでO(N)では間に合わない。そのため各bitごとにxorを計算し、1になる桁があった時点で勝ち判定を返す。
1桁目は1 0 1 0 の繰り返しなので、N mod 4が1または2の時1なので、勝ち確定。それ以外のときは2桁目へ進む。
2桁目は0 1 1 0 0 1 1 の繰り返しなので同様に判定する。これを最上位の桁まで行う。すべての桁で0であれば負け確定。
Codeforces 417 B. Sagheer, the Hausmeister
n階m部屋と両脇に階段(よって全体の幅はm + 2)の建物がある。最初は1階の左はじにいる人が各階の電気をすべて消し、上にのぼる、次の階もすべて消し上にのぼる…を繰り返してすべての部屋の電気を消す。最初に点いている部屋が与えられる時、最短の距離を求めよ。
ある階を消し終わって右端にいる時の最短距離及び左はじにいる時の最短距離を仮定すると、次の階はそれらの二つを使って求められるのでdpになる。最後の階だけは端の階段に戻らない、最初の階は一番右にある電気のついてる部屋 or m+1というところを気をつける。dpの遷移自体はO(n)。単に入力の読み込みだけがO(nm)。
Yukicoder No.520 プロジェクトオイラーへの招待
No.520 プロジェクトオイラーへの招待 - yukicoder
三角形の各辺について、a個、b個、c個の内分点が与えられる。頂点及び内分点同士で直線を互いに交わらないように引けるだけ引く。線の引き方は何通りあるか？
真ん中に三角形ができるパターンと出来ないパターンの二通りを考える。
真ん中に三角形ができるパターン
各辺から1個点を選び、それで三角形を構成する。これが真ん中にできる三角形になる。a * b * c通り。
次に各頂点と今引いた線で構成される、真ん中の三角形を除いた3個の三角形を考える。
dp[a][b] = dp[a-1][b] + dp[a][b-1]
の漸化式でカウントできる。(ある直線が引かれる1個前の組み合わせは二通りしかないため。)また、dp[a][1] = dp[1][b] = 1である(1点から残りのすべての辺に線が引かれる。
三角形ができないパターン
一つの辺から残り2この辺への直線のみで構成される。このパターンはdp[a + b + 1][c] などで計算できる。
