足跡-sokuseki-

りかの日進月歩の記録

COLOCON -Colopl programming contest 2018- Final B 異世界数式

競技プログラミング AtCoder

B - 異世界数式

これ自力で思いつけたの嬉しい。

問題概要

数式 S が、単なる数字の列か、もしくは演算子 （+, -, *, / のいずれか） の直後で括弧（(） を開き、その中に数式をいくつかカンマ （,） で区切って並べ、その後括弧 （)） を閉じるという形式で表されている。
この数式を通常の中置記法の数式に変換せよ。

制約
1 \le |S| \le 10^5

解法

'+' '-' '*' '/'のいずれかの演算子が現れたとき、その演算子を使うのは、直後の括弧の中だけなので、スタックに積んでおき、','が現れたらスタックの一番上の演算子に置き換え、括弧が閉じたらスタックの一番上を廃棄すればよい。
さいごに、もともと数式に存在した括弧の直前の演算子を取り除けば良い（スタックに積む時に取り除いてもいいけど面倒）。

Submission #2164590 - COLOCON -Colopl programming contest 2018- Final（オープンコンテスト）

みんなのプロコン 2017 本選 A YahooYahooYahoo

競技プログラミング AtCoder

A - YahooYahooYahoo

問題概要

文字列 S が与えられるので、 'yahoo'の繰り返しの文字列にするための編集距離を求めよ。

制約
1 \le |S| \le 10^5

解法

dp[ i ][ j ] := S[0…i ] を「 'yahoo' の繰り返し + 'yahoo' の先頭 j 文字」の文字列にするための編集距離

としてDPする。

dp[0][0]は0、その他はINFで初期化する。

遷移は、dp[ i ][ j ] （ S[i ] と 'yahoo' の j 文字目）を見ているとき

  • 削除 … 編集距離は1増えて、次は S[ i+1 ] と 'yahoo' の j 文字目を見る
  • 挿入 … 編集距離は1増えて、次は S[i ] と 'yahoo' の j+1 文字目を見る
  • 変更 … S[ i ] が 'yahoo' の j 文字目と同じならば編集距離は変化せず、異なるならば編集距離は1増える。次は S[i+1 ] と 'yahoo' の j+1 文字目を見る

となる（普通の編集距離のDPとほぼ同じ）。

注意が必要なのは挿入の遷移で、更新式が
dp[ i ][1] = min(dp[ i ][1], dp[ i ][0]+1);
dp[ i ][2] = min(dp[ i ][2], dp[ i ][1]+1);
dp[ i ][3] = min(dp[ i ][3], dp[ i ][2]+1);
dp[ i ][4] = min(dp[ i ][4], dp[ i ][3]+1);
dp[ i ][0] = min(dp[ i ][0], dp[ i ][4]+1);
dp[ i ][1] = min(dp[ i ][1], dp[ i ][0]+1);
…
と循環してしまうため、 j は0から4までを1周するだけでは足りない。（2周すれば大丈夫らしいけどたくさん回しました）


Submission #2164134 - 「みんなのプロコン」本選 オープンコンテスト

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

競技プログラミング AtCoder

C - 広告

問題概要

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

制約
1 \le r, c \le 40

解法

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

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

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

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

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

ゲーム制作

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

 

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

 

で、できたのがこれ。

 

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

 

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

 

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

 

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

 

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

 

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

 

 

今後の課題等

  • 当たり判定がガバなのでなんとかしたさある
  • そすうさが素数や合成数に当たったときに、そすうさが何らかのアクションをできたらいいな
  • 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のゲームをアップロードして公開しよう

 

 

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) ) を使うべき