2018-03-05

SoundHound Inc. Programming Contest 2018 (春) C 広告

競技プログラミング AtCoder

C - 広告

問題概要

縦 $r$ マス横 $c$ マスのグリッドがあり、それぞれのマスには ' * ' か ' . ' が書かれている。
' . ' のマスに、それぞれがとなり合わないように広告を打つとき、打てる広告の最大数を求めよ。

制約
$1 \le r, c \le 40$

解法

' . ' のマスを頂点とし、となり合う ' . ' のマス同士を辺で結んでグラフを作ると二部グラフになる。
この問題はグラフの最大独立集合を求める問題に帰着するので、このグラフの最大マッチングを求めて、頂点数から引けばよい。

Submission #2161432 - SoundHound Inc. Programming Contest 2018 (春)

2018-03-04

ARC061 D すぬけ君の塗り絵 / Snuke's Coloring

競技プログラミング AtCoder

D - すぬけ君の塗り絵 / Snuke's Coloring

問題概要

縦 $H$ マス横 $W$ マスの盤があり、すべて白く塗られている。
この状態から $N$ マスを黒く塗りつぶした。 $i$ 番目の黒いマスは上から $a_i$ 行目で左から $b_i$ 列目のマスである。

$0 \le j \le 9$ を満たす全ての $j$ について、盤の中に完全に含まれるすべての3行3列の連続するマス目のうち、黒いマスがちょうど $j$ 個あるものの個数を求めよ。

制約
$2 \le H, W \le 10^9$
$1 \le N < min(10^5, H \times W)$
$1 \le a_i \le H$
$1 \le b_i \le W$

解法

マス $(i, j)$ を黒く塗ったとき、3行3列の連続するマス目のうち関係するのは、中央が $(i-1, j-1), (i-1, j), (i-1, j+1),$ $(i, j-1), (i, j), (i, j+1),$ $(i+1, j-1), (i+1, j), (i+1, j+1)$ であるようなもの（で、かつ盤の中に完全に含まれるもの）である。また、1マスを黒く塗りつぶした時に関係がある行3列の連続するマス目は高々9個であり、 $N$ マスを黒く塗りつぶした時に関係がある行3列の連続するマス目は高々 $9N$ 個である。

よって、高々 $9N$ 個を全列挙して数え上げれば、 $1 \le j \le 9$ を満たす全ての $j$ について、盤の中に完全に含まれるすべての3行3列の連続するマス目のうち、黒いマスがちょうど $j$ 個あるものの個数は求められる。
盤の中に完全に含まれるすべての3行3列の連続するマス目は $(H-2)(W-2)$ 個なので、 $j = 0$ のときは、「 $(H-2)(W-2) -$ ( $1 \le j \le 9$ の時の答えの総和) 」が答えとなる。

Submission #2152583 - AtCoder Regular Contest 061

2018-03-04

ARC058 D いろはちゃんとマス目 / Iroha and a Grid

競技プログラミング AtCoder

D - いろはちゃんとマス目 / Iroha and a Grid

問題概要

縦 $H$ マス横 $W$ マスのグリッドの左上のマスから、右と下の移動を繰り返し右下のマスに移動する。
下から $A$ マス以内かつ左から $B$ マス以内のマスには移動できない。
移動する方法が何通りかを $10^9+7$ で割った余りを求めよ。

制約
$2 \le H, W \le 10^5$
$1 \le A < H$
$1 \le B < W$

解法

縦 $x$ マス横 $y$ マスの長方形の移動は $_{x+y-2} C _{x-1} = \frac{ (x+y-2)! }{ (x-1)! (y-1)!}$ 通り。

階乗と階乗の逆元を $O(H+W)$ であらかじめ求めておく。

$0 \le i < H-A$ を満たす全ての $i$ について、 $(0, 0), (i, B-1), (i, B), (H-1, W-1)$ を順に通る経路（つまり、 $_{B+i-1} C_{B-1} \times \ _{W-B-1 + H-i-1} C _{H-B-1}$ ）の個数を数え上げて、総和を求めればよい。

Submission #2152295 - AtCoder Regular Contest 058

2018-02-27

Unityでそすうさゲームを作った

ゲーム制作

ゲーム制作には以前から興味があったけど難しそうだし…と手を出せずにいたのですが、Unityを使えば簡単にゲームを作れると教えてもらったのでやってみました。

春休みに入ってから、初心者向けのUnityの本（https://www.amazon.co.jp/Unityの教科書-Unity-2017完全対応版-3Dスマートフォンゲーム入門講座-Entertainment/dp/4797393521）を借りて、本に載ってるサンプルを作りながらどういうゲームを作ろうかなーと構想を練ってました。

で、できたのがこれ。

そすうさを喜ばせる(?)ゲームを作った pic.twitter.com/9ibkxJ0PDE
— りさ (@wk1080id) 2018年2月26日

制作時間は1日半ほどで、実際にUnity触ってたのは7時間くらい？（他はフリー素材探したり素材作ったり）

以下ゲームの簡単な説明。

上から2桁の自然数が落ちてきます
キャラクター（そすうさ）を左右に動かすことができる
キャラクターに合成数が当たるとHPが減る（音が鳴る）
キャラクターに素数が当たると、その数がスコアに加算される（音が鳴る）
HPが0になるとゲームオーバーになってリザルト画面に移る
リザルト画面ではスコアを表示し、スコアが素数ならばキャラクターが動く

ちなみに、スコアが素数だと鳴きます pic.twitter.com/YIrwnkIuOv
— りさ (@wk1080id) 2018年2月26日

キャラクターの移動は、移動ボタンを作ろうかとも思ったんですが、落ちてくる数と重なったりボタンが小さくて押しにくかったりしたらいやだなあと思って、画面の右半分をさわれば右に移動、画面の左半分をさわれば左に移動するようにしています。

自然数の落下する時間間隔と落下速度は、スコアによって変わるようにしています。そのため制限時間等は設けていません。最後のほうは画面が自然数だらけになってやばい。

あともう一つ隠し要素があるので、もしプレイする機会があれば頑張って探してください。

今後の課題等

当たり判定がガバなのでなんとかしたさある
そすうさが素数や合成数に当たったときに、そすうさが何らかのアクションをできたらいいな
BGMとか
ゲームの中断画面って作れるんですかね…？
公開したい気持ちはあるんですけどね、お金がいるので

音源

http://inter-high-blog.unity3d.jp/2017/08/08/freemusic/

画像素材

http://www.irasutoya.com

http://free-line-design.com

[追記]

WebGLで作り直してunity roomで遊べるようにしました

Sosuusa Feeding | 無料ゲーム投稿サイト unityroom - Unityのゲームをアップロードして公開しよう

2018-02-24

ABC061 D Score Attack

競技プログラミング AtCoder

D - Score Attack

問題概要

$N$ 頂点 $M$ 辺の有向グラフが与えられ、 $i$ 番目の辺は頂点 $a_i$ から頂点 $b_i$ をコスト $c_i$ でつないでいる。
頂点1から頂点 $N$ に行くときの合計コストの最大値を求めよ。なお、合計コストをいくらでも大きくできるときはinfを出力せよ。

制約
$2 \le N \le 1000$
$1 \le M \le min(N(N-1), 2000)$
$1 \le a_i , b_i \le N$
$- 10^9 \le c_i \le 10^9$

解法

コストの正負を逆にすることでグラフの最短距離を求める問題になる。以下はコストの正負を逆にして考える。

まず、グラフの最短距離をいくらでも小さくできるときというのは、グラフに距離が負の閉路が存在するときのみなので、頂点1から頂点 $N$ の経路の途中に負の閉路があった場合はinfを出力する。
そうでない場合は、単純に頂点1から頂点 $N$ までの最短距離が答えとなる。

最短距離を求めるのと負の閉路を検出するのにはベルマンフォードを使う。

ベルマンフォードは単一始点の最短距離を求めるアルゴリズムで計算量は $O(NM)$ 。
特徴はコストが負の辺があっても正しく計算できることと、コストが負の閉路を検出できること*1。

ベルマンフォードのアルゴリズムは、始点から始点の距離を0、始点から始点以外の頂点の距離を $\infty$ として、「すべての辺を見て、始点からの距離を更新できる頂点があれば更新する」を $N-1$ 回くりかえす。

「すべての辺を見て、始点からの距離を更新できる頂点があれば更新する」という操作をしたとき、必ず1つ以上の頂点の、始点からの距離が確定することがわかる。任意の頂点間の辺の数は高々 $N-1$ 本なので、この操作を $N-1$ 回繰り返せば、すべての頂点に対する始点からの距離が求められるはずである。

しかし、これには例外があって、コストが負の閉路があった場合、最短距離はいくらでも小さくできるので、この操作を $N-1$ 回繰り返しても始点からの距離が確定せず、 $N$ 回目の操作でも始点からの距離を短くすることができる。よって、 $N$ 回目の操作で始点からの距離を更新する頂点が存在すれば、そこに負の閉路が存在することがわかる。

以上のことから今回の問題では

辺のコストの正負を逆にして、ベルマンフォードをする。
その後、頂点1から頂点 $N$ の経路に負の閉路があるかを確かめ、あればinfを、なければ頂点1から頂点 $N$ の距離を符号を逆にして答える。

をすればよい。

頂点1から頂点 $N$ の経路に負の閉路があるかを確かめる方法は、ベルマンフォードをしたあとに、さらに「すべての辺を見て、始点からの距離を更新できる頂点があれば更新する」を $N$ 回くりかえし、そのあいだに頂点 $N$ の最短距離が更新されれば、経路中に負の閉路があるということがわかる。

負の閉路がある場合、ベルマンフォード直後の「すべての辺を見て、始点からの距離を更新できる頂点があれば更新する」操作で、負の閉路に含まれる頂点のうち少なくとも1つがわかる。その後にその操作を $N-1$ 回繰り返すことで、負の閉路中にある頂点から到達できるすべての頂点について、最短距離が更新されるからである。

Submission #2125589 - AtCoder Beginner Contest 061

*1:コストが負の辺が存在しない場合は、より計算量が小さいダイクストラ( $O(ElogV)$ ) を使うべき

2018-02-22

ABC011 D 大ジャンプ

競技プログラミング AtCoder

D - 大ジャンプ

問題概要

スタート地点の座標は $(0, 0)$ で、ゴール地点の座標は $(X, Y)$ とする。
1回のジャンプで、それぞれ $\frac{1}{4}$ の確率で以下の4つのうちどれかを行う。

$x$ 軸方向に $+D$ だけ移動する
$x$ 軸方向に $-D$ だけ移動する
$y$ 軸方向に $+D$ だけ移動する
$y$ 軸方向に $-D$ だけ移動する

ちょうど $N$ 回のジャンプでスタート地点からゴール地点に到達できる確率を求めよ。

制約
$0 \le N \le 1000$
$1 \le D \le 10^9$
$- 10^9 \le X, Y \le 10^9$

解法

$x$ 軸方向に $i$ 回移動するとき、 $y$ 軸方向に $n-i$ 回移動することになる。
また、このとき、 $x$ 軸の正の方向に $j$ 回移動すると、 $x$ 軸の負の方向に $i-j$ 回移動することになるので、到達点の $x$ 軸座標は $D j - D ( i - j )$ になる。
$y$ 軸方向にも同様に考えて、 $y$ 軸の正の方向に $k$ 回移動すると、 $y$ 軸の負の方向に $n-i-k$ 回移動することになるので、到達点の $y$ 軸座標は $D k - D ( n - i - k )$ になる。
到達点の座標が $(X, Y)$ であればよい。

つまり、 $x$ 軸方向の移動回数 $i$ 、 $x$ 軸の正の方向の移動回数 $j$ 、 $y$ 軸の正の方向の移動回数 $k$ を全探索して、その到達点の座標が $(X, Y)$ ならば、その確率を答えに足しあわせればよい。

$i$ 回の移動のうち正の方向に $j$ 回移動するのは $_i C _j$ 通りあり、 $i$ 回正負のどちらかに移動するのは $2^i$ 通りあるので、 $i$ 回の移動のうち正の方向に $j$ 回移動する確率は $\frac{ _i C _j }{2^i}$ である。
よって、 $i$ 回の移動のうち正の方向に $j$ 回移動する確率を前計算することで、 $O(N^2)$ で求めることができる。

なお、制約の $N$ が大きいので、「 $i$ 回の移動のうち正の方向に $j$ 回移動する場合の数」は計算できない。パスカルの三角形を計算する時の遷移で2で割ることで確率を計算できる。

ちなみに、 $x$ 軸方向の移動回数 $i$ を決めると、ゴールにたどり着くための $x$ 軸の正の方向の移動回数と $x$ 軸の負の方向の移動回数はわかるので、この問題は $O(N)$ で解くこともできる。

Submission #2121336 - AtCoder Beginner Contest 011

2018-02-21

ABC037 D 経路

競技プログラミング AtCoder

D - 経路

問題概要

縦 $H$ 横 $W$ のマス目があり、それぞれのマスには整数 $a_{i j}$ が書かれている。
このグリッドの中の好きなマスから開始し、今いるマスの上下左右に隣接しているマスのうち、今いるマスより大きな整数が書かれたマスに移動することができる（移動しなくてもよい）。
ありうる移動経路の個数を $10^9 + 7$ で割った余りを求めよ。