情報妖精の競プロ日記

AtCoderの問題に対する方針を主に書きます

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 - セキュリティ

これはシミュレーションすれば良くて、'+'ならばA=A+1、'-'ならばA=A-1を行い、
途中でA=0になるかのみを判定すればO(|S|)で十分間に合います。

C - 右折

まず、こういう時はサンプルケースと比較しながら実験してみましょう。

. . #
. . .
# . #

まず、最初は右に行く→次に下に行く、の場合について考えてみましょう。
ここで、右折後の移動の仕方は各マスについて次のようになります。

1 2 #
0 1 0
# 0 #

これは、つまり自分の下のマスが何個あるか、ということなので累積和を用いて予めO(NM)で計算しておくことができます。
では、右折する前の状態は各マスについて何通りあるか考えてみましょう。

2 0 #
1 0 0
# 0 #

これは、先ほど右折後の通り数を求めたマップについて、自分の右側の通り数の合計に等しい訳です。
何故なら、各地点で右折したら後はその通りだけのパターンが存在し、しかも互いに排反だからですね。
よって、また同様に累積和を取ると各マスについて通り数がO(1)で求められるので、結局全体の通り数もO(NM)で求められます。
後は最初の移動方向が4通りあるので、それぞれについて同様に解けば答えが出ます。

D - うほょじご

まず、操作について考えてみます。
x<1000ならrev(x)<1000であり、次の操作は引き算なので必ず0 \leq x, y < 1000であることが分かります。
つまり、(0, 0)から(999, 999)までの全ての答えを求めていればO(NM)で答えを導出できます。
この答えは次のようにして導出できます。以下、(x, y) = true(x, y)が無限ループすると定義することにします。

  1. (0, y)及び(x, 0)false
  2. まだ答えの出ていない(x, y)を一つ選ぶ
  3. (x, y)に対して操作を行った結果を(x2, y2)とする時、(x, y)の答えと(x2, y2)の答えは一致するので操作後の(x2, y2)について調べる
  4. まだ答えが出ていない、かつ調べた(x, y)を2度通ったなら、今まで調べた(x, y)は全て無限ループとする

ある(x, y)について既に調べたかどうかを管理するフラグを1個持っておくと、これは同じ(x, y)を2度調査しないのでO(NM)で計算できます。
よって計算量はO(NM)となります。

E - 迷路

まず、愚直に幅優先探索でシミュレーションするとO(NMK)となり普通に無理です。
これは次のマスに行けるかどうかに最大でO(K)のループが発生するからに他ならないので、これをO(1)にできないか考えます。
まず、注意点として既に通ったマスでは待機が可能なので、ある時間tまでで行けるマスには必ず時間tの時点でそのマスにいる方法が存在します。
よって、必要な情報としては時間tにどのマスには既に行けていて、次のシミュレーションでどのマスに行けるかです。
そこで、サンプルと見比べながら考えてみましょう。
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通りに分類しておくことができます。
ここで、各時間におけるどの候補が最初に来るか分かっていれば、O(1)でシミュレーションできるのではないかと考えられます。
次の表を見てみましょう。

時間t \mod K
移動方向 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
これは、現在時間が分かっているときに次の各方向が後何秒後に来るかの表です。この表はO(K)で作れます。
この表を用いると、次のようなことが導出できます。
例えば、先ほどのサンプルで時間0の時、移動可能な方向はRとDです。
ここで、 0 mod K = 0の部分を見比べるとRは4秒後、Dは2秒後なので2秒進めるとD方向へ進めるマスが存在することが分かります。
これでO(1)で少なくとも1マスは移動可能なマスを増やすことに成功したので、O(NM)で全てのマスを見ることができます。
また、この時にもし進めるマスの候補が無くなったら-1を返せば良いことも分かります。

結果

oooox--- 4完(1100点) 2:08-4:13-35:31(1WA)-54:55 : 59:55
185位

感想

5問目は実装が重いので、工夫をしないと直ぐに死ぬかもしれません。
4方向の探索についてや、予め与えられたマップの周囲1マスを'#'で囲む番兵と言われる実装など、典型的な注意点が多々あります。
実装バグには注意しましょう!
というか5問目、終わってから提出したらACだったよ!ふざけんな!