AOJ 2643 : AI
構文解析。ループの判定をどうするかだが、
命令のindex、x, y, 向いている方向を持てば良い。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2360572#1
横着してTreeSetで到達済みの状態を管理していたらTLE。
logはバカにならないので気を付けよう！
（logを殺してくる問題はあまり好きになれない）
動作文の実行回数をグローバルに持ってしまっていてあまり綺麗でない。
どうすればいいものか・・・。
AOJ 2297 : Rectangular Stamps
Rectangular Stamps | Aizu Online Judge
盤面の状態を2bit * 16の32bitで表現できるなあ、と考えたが
大きすぎてメモ化はできない。
A*などで頑張るが無理。検索する。
ああ～確かに1bitだけで十分だった。
そうすれば到達済みのところは行かないようにすれば
探索数を削減できる。
スタンプの適用をするマスクを前処理で用意したり、
キューに突っ込む前に到達済みチェックをすれば
時間内に間に合う。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2359465#1
AOJ 2438 : YAML
構文解析。一発とは行かず結構debugした。
debugの際、どこを今指しているかをビジュアライズすると楽。
例えばSample Input 1の場合
name: shimeji<id: shimejitan<tweets:< 1: shimejilove< 2: azupero
^みたいな感じで（改行を'<'にしている）。
改行ごとに区切った配列でも良さそうだけど、
少し面倒なことになりそうだったので改行含んだ1つの文字列として扱った。
あとはつい最近読んだ
構文解析 Howto · GitHub
を参考にしてみた。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2359079#1
本当はparse関数をparseObj(0,str,0)に一般化したかったけど、
上手い方法が思いつかなかった・・・。
parseStringというのを作ればよかったのかも。
AOJ 2425 : 全探索お姉さんの休日
A Holiday of Miss Brute Force | Aizu Online Judge
最大何回無視すれば答えがわかるのか、tの上限は？
などと考えて解けないと思っていた。
しかしよく考えてみるとtは6で割った余りだけ保持していれば良いことに気づく。
ある場所にt%6で辿りついたとき、今までのコスト（無視した回数）以下だったら探索しなくて良いので、
状態は cost[x][y][t%6] と取ってコストが小さい順にダイクストラすれば良い。
あとはoffsetを取ったり、隣接しているセルに移動する配列を用意すれば書ける。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2359040#1
abs(x)が奇数だったときに隣接するマスへの差分値が偶数のときと異なることに気づけなくて、
debugするのが大変で時間を喰ってしまった。
Codeforces Round #418 (Div. 2) : A B C D
A
bの数列に出てくる数字の種類が2種類以上であれば答えはYes。
それ以外の場合、1種類の数字をaが0のところに置いてみて、
ソートした結果がaと異なればYes、同じだったらNo。
B
数列a, b とも n - 1個は数列qと合っているとのことなので、
重複している2個と存在しない数字1つについて考えればよい。
重複している2個のどちらかを採用しないようにして、
数列を組み立てる。その結果1~nまで1つずつ存在したら
その数列が答え。
C
コンテスト中に解けず。TLを見てあそっかあとなる。
memo[a to z][m] := m回塗り替えたときに得られる最大Koyomity
とすると、memoを-1で初期化し、a から zまでの文字cに対して
[l, r]の範囲で全部cで塗り替えるには何回必要かを計算して、
memo[c][何回必要か] = max(memo[c][何回必要か], r - l + 1)
とすればクエリーにO(1)で答えられる。
D
コンテスト中にACできず。終わったあとにオーバーフローと出力フォーマットのミスに気づく。
2つの円のリストを考えたとき、半径の大きい順から円を取り出してきて
一方に円を追加したときの面積差分と、もう一方に円を追加したときの面積差分を比べて、
大きくなるほうに円を追加すればよい。差分が同じ場合は、どちらに追加しても結果は同じ。
O(n^2)
http://codeforces.com/contest/814/submission/27651258
直観でこう気づいたけど、これが正しい理由はイマイチ分からない。
AOJ 1169 : 最強の呪文
The Most Powerful Spell | Aizu Online Judge
嘘解法くさいです。
ダイクストラに見えるけど違うのかな・・・？
と思ったらダメになるケースがある。
あらかじめ幅優先探索をして各ノードからゴールまでの最小文字列を求めておき、
これをヒューリスティックスコアとしてA*探索を行う。
ループが発生したら2400文字（ループさせないでまっすぐ行ったときに考えうる最大の長さ）まで
ループ部分を付け足しておき、最後にループさせないでゴールに着いた文字列と比較する。
としたらACできた。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2355848#1
嘘解法くささ2
ループ判定。2度目にたどり着いて一定の条件を満たせばループ扱いになってしまう。
nが最大で40ぐらいだからbitで経由したノードを記録しておく必要がありそう。
嘘解法くささ3
そもそもこのアルゴリズムで正しい答えが出るのか・・・？
なんかすっきりしないACの仕方をしてしまった。
他のブログを参照するときちんと考察の上解いているので見習いたい。
少し背伸びをして難しい問題が解きたいと思って
700点でかつサークルの人たちが解いているこの問題に手を出してみた。
黄色ゾーンが埋まったらまた解きなおしたい。
AOJ 2444 : Substring
制約がnもmも10^5あるので愚直解はまず通らなそう。
Suffix Arrayを合ってるか分からないけど言葉だけ思い出したが、
実装できる自信はない・・・。
少し悩んだらローリングハッシュというものを思い出した。
前処理O(n)、区間クエリO(1)でできるようなので今回はこれを採用（簡単そうだし）。
「ローリングハッシュ」と検索して一番上に出てくる id:odan3240 さんの記事のコードを移植する。
名前だけ知っていたロリハを実際に使ったのは2016年夏合宿で
そのときの記憶を頼りに最初はMを2^60などと置いていたが
オーバーフローしているようでサンプルが合わない。
おとなしく記事の通りにしてACをもらう。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2355679#1
今回は体調が優れなかったので気分転換にD言語で解きました。
（オーバーフローぐらい、自分の感覚で把握できるようになりたいなあ）
