UVa1263

UVa1263
グラフにする。
強連結成分分解して、頂点の入次数を見る。
強連結成分分解のコードは省略。だいたいスパソと同じ。

ClojureでLispインタプリタ

思いつきでやってみた。意外と面白かった。
ちゃんと動くかは自信がない。
関数を定義するときに [ ] を使わないといけないのは気にしない。

UVa12338

UVa12238
接尾辞配列ライクなことをやる。
与えられた文字列をソートし、となりあう文字列の一致する最長のプレフィックス (LCP) を求める。
それに RMQ を使ってクエリーを処理する。

A[i] と A[i+1] のプレフィックスが n 文字目まで一致していて、
A[i+1] と A[i+2] のプレフィックスが m 文字目まで一致していれば、
A[i] と A[i+2] は min(n, m) 文字目までのプレフィックスが一致していることになる。

A[j]とA[k]のプレフィックスはRMQ(j, k)文字目まで一致することになる。

このアプローチで実行時間が3秒強。タイムリミットが5秒。
ラディックスソートとか使えばもっと早くなるかも？

SRM537 Div2 Hard

925
とりあえず、グラフにする。
あるトーストを学ぶために食べるトーストの枚数は最小で１、最大でルートまでの距離
全ての頂点に関して試す。

点数も1000より低いし、本番でも40人以上が通してるけど、そんなに簡単とは思えなかった。

SRM503 Div2 Hard

900
MST

SRM502 Div2 Hard

1000
DPする。
DP[何匹目まで見た mod 2][数字の合計 mod N][何匹が逃げた];

この実装だと、実行時間がそうとうギリギリ。
テーブルの半分を毎回初期化するのはもちろん、剰余算を少し余計にやっただけでアウト。

SRM501 Div2 Hard

1000
メモ化する。
memo[長さ][これまでの合計][最後に使った数][何連続で減少しているか];

SRM536 Div2 Hard

1000
ソートしてDPする。意外と時間がかかった。