AtCoder Mujin Programming Challenge 2018 反省

C問題コンテスト中に解きたかったなあ

A: コンテスト名 - Mujin Programming Challenge 2018 | AtCoder
substrで入力の先頭5文字を見て"MUJIN"になっているかを見る.
Submission #2941754 - Mujin Programming Challenge 2018 | AtCoder

B: セキュリティ - Mujin Programming Challenge 2018 | AtCoder
愚直にシミュレーションしましょう.
Submission #2942432 - Mujin Programming Challenge 2018 | AtCoder

C: 右折 - Mujin Programming Challenge 2018 | AtCoder
曲がる場所に着目して左右上下の空きマスを掛けあわせるとできそうだなあと思いましたが実装がなかなかきつそうだったので後回しに. D問題を解いた後戻りましたが実装に手間がかかり, 最後に最後っ屁をぶん投げるもWA. コンテスト後にいろいろ手直ししてAC. 答えの範囲がint型に収まると思っていましたが, 順序対の対は((2*10^3)^2)^2となるため確かにlong long intが必要です.
Submission #2946178 - Mujin Programming Challenge 2018 | AtCoder

D: うほょじご - Mujin Programming Challenge 2018 | AtCoder

とりあえず実験でいくつかやってみると, ある程度枝刈りすれば間に合うのではないかと思えました. そこで計算過程をみながらいろいろ枝刈りする方法を探していると, 無限ループに入る状態と入らない状態への遷移を見ればある程度計算量を落とせることに気づきました. 状態の遷移を見るので動的計画法を実装しなければなりませんが, 状態の遷移の仕方がかなり不規則であるために順にテーブルを埋めるのは難しいと考え, メモ化再帰で実装しました. 無限ループに入るかどうかはあらかじめmapを用意しておき, ある状態に遷移したら順序対をtrueに設定し, 再びtrueの状態に遷移すれば無限ループ状態と判定しました. 無限ループが確定するまでdp配列を決定することができないため, メモ化再帰がやはりうってつけです.

Submission #2944821 - Mujin Programming Challenge 2018 | AtCoder