Mujin Programming Challenge 2018
目標は200位でした。レート順400位ぐらいだったので運次第、と思ってました
A - コンテスト名
提出コード
頭が真っ白になったので素直に全部書き出しました。与えられる文字の長さがそもそも5に満たない場合の条件を途中まですっかり書き忘れていたので危なかったです。
B - セキュリティ
提出コード
似たような問題はいくつか見たことがありますね。文字列の頭からみていって、+と-の場合でそれぞれの処理を行っていきます。
最初と最後が0人かどうかのチェックも忘れずに。
C - 右折
提出コード
こちらは実装がかなり重そうだったので先にCを通しました。
自分は2方向の累積和を使って考えました。
最初のテストケースを用いて考えることにします。テストケースのマス目は以下のようになっています。
. . #
. . .
#. #
右方向に進み、右折して下方向にすすむことを考えます。 iを行番号、jを列番号とすると、iを増やすfor文の中にjを増やすfor文をネストすることで、下のようにマス目を見ていくことができます。
→→→
→→→
→→→
2つのステップを踏んで答えを求めます。
① 右方向
マス目と同じ大きさのあらたな配列を用意して、そこには
- 右側に進んだ結果そのマス目にたどり着く出発地点の個数
をいれることにします。これは累積和を用いて、マス目が通れるか通れないかの場合分けで、比較的簡単に求めることができます。
そのマス目が通れるなら一つ手前の数+1、通れないなら0の代入を施してあげればよいです。
求めた結果は次のようになります。
0 1 0
0 1 2
0 0 0
➁ 下方向
先ほどと同様に、
- 右折して下側に進んだ結果そのマス目にたどり着く出発地点の個数
を格納するための配列を用意してあげます。すると、今度は①の結果を利用することができます。先ほどはマス目を進めるたびに+1していたのですが、今度は進める前のマス目に入っていた、①の結果を足してあげればよいです。今度も、マス目が通れなかったときは自動的に0になります。
すこしわかりづらいので2列目についてみてみます。
(1,2)は 、上にマス目がないので0になります。
(2,2)は、一つ上のマス目の、①の結果が1になっているので、答えは1になります。
(2,3)は、一つ上のマス目の、①の結果が1であり、一つ上のマス目の、➁で求めた1と足し合わせて2になります。
これを繰り返すと、
0 0 0
0 1 0
0 2 0
となります。
あとは、このすべての合計を求め、そして4方向(右→下、下→左、左→上、上→右)全てについて同じことを繰り返せば答えがもとまります。
ループの向き、ネストする順番、始まりと終わりの値、そして参照する配列の場所に注意して実装すれば、c++でしたら時間的には問題ありません。あとは、答えの組み合わせのオーバーフローにも注意しましょう(intだったので1WAでした)
D - うほょじご
提出コード
rev(うほょじご)=ごじょほう
メモ化再帰ですね。
x,yという2つの数字があったときに(x>=yとします)、x=rev(y)になると片方が0になってしまいループがとぎれてしまうので、そうなったら終了し、そうならなければループが続くまで操作を続けるような関数を考えます。
いちいちループするかどうかを判定するのは手間がかかるので、二次元配列に、もうその数字のペアを調べたかどうか、およびループが途切れるかどうか、を記録するようにします。
あとは、その配列を参照しつつ、操作を再帰で繰り返していけば時間内に答えを求めることができます。
E - 迷路
残り30分ほどだったので、とりあえず思いついた幅優先を書きましたがTLEでした…さすがにE問題をこの時間で解くことは無理そうなのですが、27分ほどでバグを取り切ったのでまぁまぁかなと思います(満足してはいけないと思いますが)。また通したら追記しようと思います。
2018.8.7追記
一応通しました！
提出コード(時間外)
幅優先探索のコードをほぼ流用して優先度キューに書き直し、加えて、解説にも載っている
- 現在の時間から、次に行きたい方向になるまでにかかる時間
を先にメモしておくことで、ダイクストラ法の要領で解くことができました。
また、ダイクストラ法を利用するにあたり、初めてラムダ式を使いました。
十分に時間があったとしても、次の進みたい方向に進むまで待機する時間をメモするという発想はできなかったと思います…
というわけで、4完の234位でフィニッシュでした。目標にはあと少し足りませんでしたが、先輩方の順位を見ていると、この順位が妥当だなという感じです。200位に入るにはあと20分ほどはやく通さないといけないようなので、思ったより遠そうです。引き続きがんばっていきたいと思います。
