Mujin Programming Challenge 2018
Mujin Programming Challenge 2018 に参加しました!
Mujin Programming Challenge 2018 旧版
Mujin Programming Challenge 2018 beta版
解けた問題だけ解説をしていきますー
要項
Mujin Programming Challenge 2018
unrated
8/4(土) 21:00 ~ 23:00 (120分)
100-200-400-400-500-600-800-1000 (8問)
ペナルティ: 5分
方針
100位以内のボーダーは6完だと思うので、如何に早くそれまでの問題を埋めるかが鍵
とにかく愚直でも良いから解けそうな方針を次々考えるべし
後、配点の差が小さいから先の問題でも解けそうなら読むのもありかも
A - コンテスト名
要するに最初の5文字が一致するかなので、substr辺りを使って比較すればおk
B - セキュリティ
これはシミュレーションすれば良くて、'+'ならば、'-'ならばを行い、
途中でになるかのみを判定すればで十分間に合います。
C - 右折
まず、こういう時はサンプルケースと比較しながら実験してみましょう。
. | . | # |
. | . | . |
# | . | # |
まず、最初は右に行く→次に下に行く、の場合について考えてみましょう。
ここで、右折後の移動の仕方は各マスについて次のようになります。
1 | 2 | # |
0 | 1 | 0 |
# | 0 | # |
これは、つまり自分の下のマスが何個あるか、ということなので累積和を用いて予めで計算しておくことができます。
では、右折する前の状態は各マスについて何通りあるか考えてみましょう。
2 | 0 | # |
1 | 0 | 0 |
# | 0 | # |
これは、先ほど右折後の通り数を求めたマップについて、自分の右側の通り数の合計に等しい訳です。
何故なら、各地点で右折したら後はその通りだけのパターンが存在し、しかも互いに排反だからですね。
よって、また同様に累積和を取ると各マスについて通り数がで求められるので、結局全体の通り数もで求められます。
後は最初の移動方向が4通りあるので、それぞれについて同様に解けば答えが出ます。
D - うほょじご
まず、操作について考えてみます。
ならであり、次の操作は引き算なので必ずであることが分かります。
つまり、からまでの全ての答えを求めていればで答えを導出できます。
この答えは次のようにして導出できます。以下、をが無限ループすると定義することにします。
- 及びは
- まだ答えの出ていないを一つ選ぶ
- に対して操作を行った結果をとする時、の答えとの答えは一致するので操作後のについて調べる
- まだ答えが出ていない、かつ調べたを2度通ったなら、今まで調べたは全て無限ループとする
あるについて既に調べたかどうかを管理するフラグを1個持っておくと、これは同じを2度調査しないのでで計算できます。
よって計算量はとなります。
E - 迷路
まず、愚直に幅優先探索でシミュレーションするととなり普通に無理です。
これは次のマスに行けるかどうかに最大でのループが発生するからに他ならないので、これをにできないか考えます。
まず、注意点として既に通ったマスでは待機が可能なので、ある時間までで行けるマスには必ず時間の時点でそのマスにいる方法が存在します。
よって、必要な情報としては時間にどのマスには既に行けていて、次のシミュレーションでどのマスに行けるかです。
そこで、サンプルと見比べながら考えてみましょう。
3 3 5
UDLRD
S | . | . |
. | # | . |
. | . | G |
これを、時間経過で追っていきます。
時間2:
S | . | . |
2 | # | . |
. | . | G |
時間4:
S | 4 | . |
2 | # | . |
. | . | G |
時間5:
S | 4 | . |
2 | # | . |
5 | . | G |
時間9:
S | 4 | 9 |
2 | # | . |
5 | 9 | G |
時間10:
S | 4 | 9 |
2 | # | 10 |
5 | 9 | G |
時間12:
S | 4 | 9 |
2 | # | 10 |
5 | 9 | 12 |
この移動についてよく見ると、同じ方向への移動は全てのマスについて同時に移動を考えても良いことが分かります。
ということは、移動方向は4通りなので次のマスの候補をこの4通りに分類しておくことができます。
ここで、各時間におけるどの候補が最初に来るか分かっていれば、でシミュレーションできるのではないかと考えられます。
次の表を見てみましょう。
時間 | |||||
移動方向 | 0 | 1 | 2 | 3 | 4 |
U | 1 | 5 | 4 | 3 | 2 |
D | 2 | 1 | 3 | 2 | 1 |
L | 3 | 2 | 1 | 5 | 4 |
R | 4 | 3 | 2 | 1 | 5 |
この表を用いると、次のようなことが導出できます。
例えば、先ほどのサンプルで時間0の時、移動可能な方向はRとDです。
ここで、の部分を見比べるとRは4秒後、Dは2秒後なので2秒進めるとD方向へ進めるマスが存在することが分かります。
これでで少なくとも1マスは移動可能なマスを増やすことに成功したので、で全てのマスを見ることができます。
また、この時にもし進めるマスの候補が無くなったら-1を返せば良いことも分かります。
結果
oooox--- 4完(1100点) 2:08-4:13-35:31(1WA)-54:55 : 59:55
185位
感想
5問目は実装が重いので、工夫をしないと直ぐに死ぬかもしれません。
4方向の探索についてや、予め与えられたマップの周囲1マスを'#'で囲む番兵と言われる実装など、典型的な注意点が多々あります。
実装バグには注意しましょう!
というか5問目、終わってから提出したらACだったよ!ふざけんな!