2018-03-04

ARC058 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$ で割った余りを求めよ。

制約
$0 \le H , W \le 1000$
$1 \le a_{i j} \le 10^9$

解法

dp[ $i$ ][ $j$ ] := マス $( i, j )$ で動くのを終了する場合の移動経路の個数

として、 $a_{i j}$ が大きい順に dp[ $i$ ][ $j$ ] を計算していく。
dpテーブルは全て1で初期化しておき、dpテーブルの更新は、マス $( i, j )$ の4近傍のマス $( x, y )$ に対して、

dp[ $i$ ][ $j$ ] $+=$ dp[ $x$ ][ $y$ ];

をする。

すべてのマス $( i, j )$ に対してdp[ $i$ ][ $j$ ] の総和が答えとなる。

Submission #2119231 - AtCoder Beginner Contest 037

2018-02-21

CODE FESTIVAL 2016 Grand Final B Inscribed Bicycle

競技プログラミング AtCoder

B - Inscribed Bicycle

幾何。

問題概要

三角形の頂点が与えられる。
三角形の内部に半径の等しい円を重ならないように2つかくとき、円の半径の最大値を求めよ。

制約
$0 \le x_i, y_i \le 1000$

解法

まず、三角形の内部に半径 $x$ の円がかけるとはどういうことかを考えてみる。
円の中心と三角形の辺の距離が $x$ 以上であれば、半径 $x$ の円がかける。
つまり、三角形の内部で、各辺から $x$ 以上離れた場所(図の緑の三角形)に円の中心があれば、その円の円周は三角形の辺上か三角形の内部にあることがわかる。
f:id:wk1080id:20180220230806p:plain

次に、三角形の内部に半径 $x$ の円が重ならないように2つかけるとはどういうことかを考える。
それぞれの円の中心と三角形の辺の距離が $x$ 以上であり、2つの円の中心の距離が $2x$ 以上であれば、半径 $x$ の円が重ならないように2つかける。
つまり、三角形の内部で、各辺から $x$ 以上離れた場所(図の緑の三角形)にそれぞれの円の中心があり、2つの円の中心間の距離が $2x$ 以上ならば、その2円の円周は三角形の辺上か三角形の内部にあり、かつ2円は重ならないことがわかる。
f:id:wk1080id:20180220230751p:plain

ここで、元の三角形の内接円の半径を $r$ とすると、元の三角形の内部で各辺から $x$ 以上離れた点の集合からなる三角形の内接円の半径は $r - x$ である。よって、2つの三角形の相似比は $r : r - x$ 。

2つの円の中心間の距離を $2x$ 以上にするためには、「元の三角形の内部で各辺から $x$ 以上離れた点からなる三角形」の少なくとも一辺が $2x$ 以上であればよい。つまり、与えられた三角形の3辺のうち最も長い辺の長さを $A$ とすると、内部の三角形の最も長い辺の長さは $A \times \frac{r - x}{r}$ になるので、これが $2x$ 以上ならば、与えられた三角形の内部に半径 $x$ の円が重ならないように2つかける。