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する。意外と時間がかかった。

SRM520 Div2 Hard

1000
メモ化する。直前の1行を覚えておけばいい。

SRM526 Div2 Hard

1000
メモ化する。
memo[桁数][4の数][7の数][まだ一致しているか]

SRM534 Div2 Hard

1000
lg 10000 が充分小さいことに着目して、メモ化する。
メモを long long int で持つとメモリで落ちた。

SRM Div2 まとめ

300代あたりは後でマージするかも？

SRM400   Easy   Medium   Hard
SRM401   Easy   Medium   Hard
SRM402   Easy   Medium   Hard
SRM403   Easy   Medium   Hard
SRM404   Easy   Medium   Hard
SRM405   Easy   Medium   Hard
SRM406   Easy   Medium   Hard
SRM407   Easy   Medium   Hard
SRM408   Easy   Medium   Hard
SRM409   Easy   Medium   Hard
SRM410   Easy   Medium   Hard
SRM411   Easy   Medium   Hard
SRM412   Easy   Medium
SRM413   Easy   Medium   Hard

SRM435   Easy   Medium   Hard

SRM436   Easy   Medium   Hard

SRM437   Easy   Medium   Hard

SRM439   Easy   Medium   Hard
SRM440   Easy   Medium   Hard


SRM501   Hard
SRM502   Hard
SRM503   Hard

SRM520   Hard
SRM521   Hard
SRM523   Hard
SRM524   Hard
SRM526   Hard
SRM526.5   Hard
SRM527   Hard
SRM528   Hard
SRM529   Hard
SRM531   Hard
SRM532   Hard
SRM533   Hard
SRM534   Hard
SRM536   Hard
SRM537   Hard



SRM544   Easy   Medium   




SRM549   Easy   Medium   
SRM550   Easy   Medium   Hard
SRM551   Easy   Medium   Hard

SRM551   Easy   Medium   Hard

SRM520 Div1 Easy

250
全部試す。

SRM521 Div1 Easy

250
スタック

SRM522 Div1 Medium

450
それっぽい数字を試していく。

SRM522 Div1 Easy

250
先頭と末尾を見る。

SRM523 Div1 Medium

500
メモ化する。
memo[h][w]=ベースの幅がwのブロックに高さhまでブロックを置くときのパターン数
ある幅を長さK以下のブロックで埋めようとしたとき、どれくらいのパターンがあるかを前もって計算しておく。

SRM523 Div1 Easy

250
やるだけ。

SRM524 Div1 Medium

500
与えられた条件を満たすような数列で、ある区間の和とある区間の和の間に不等式が成り立つ。
長さを2分探索しながら、その関係に矛盾がないかを調べる。

SRM524 Div1 Easy

250
与えられた範囲で、連続している素数は２と３だけということは想像がつく。
それ以外は、素数でなければ１回で済むし、素数であれば-1して素数でなくす。

SRM537 Div1 Medium

500
DP[K日][部屋N][Bビット] = K日が経過した部屋NのBビット目が１になっている確率。

tabbar.elのグループ化機能をせっかくだから使ってみる

ググッて調べてみても、グループ化しているブログの記事をあまり見ない。もちろん、自分でも使っていない。
でも、せっかくだから使ってみる。

デフォだとメジャーモードでタブをグループ化する様になっている。
私感ではこれが使いやすいとは思えないので、自分でグループ化する機能を描いてみる。
まだ使い込んだわけではないので、バグの１つもあると思うけど、そこはご愛嬌。

もう tabbar をいじるのに飽きてきた。

SRM537 Div1 Easy

275
XとYに何かを掛けてAとBが作れるかを試す。Xだけでどちらも作れるのなら、Yの候補は無限個。

SRM491 Div1 Easy

250
向かい合った数の合計を決める。その合計を実現できる数字の組みの数を数える。そこから３つ選ぶ。
数字の組み３つから２種類のサイコロが作れるらしい。

こんな感じで出るだろ。　=>> お？全部1/2だ。　=>> ２種類作れるのか？とりあえず２倍しとけ。
みないな推測。場合によってはとても危険な方法だけど。

SRM490 Div1 Easy

250
これが一瞬で浮かぶ数学力を持ち合わせていない。頑張って紙に書いて計算した。

SRM536 Div1 Easy

250
ソートして頭から２つずつマージしていけば良いらしい。

tabbar.elのタブを閉じる。

現在のタブから右側もしくは左側のタブを全て閉じるelisp。
tabbar.elのタブが増えたとき、一部だけ閉じるのが面倒だった。
ほとんど閉じないバッファ(howmとかeshell)を一番左に寄せる習慣があるので、面倒が解消するかも？

動作確認は、これから使いながら済ませる。

SRM535 Div1 Easy

250
LCM / GCD を素因数分解する。
あとは、各素数の累乗をどちらの数字に割り当てるかを全通り試す。
最初の素数20個の積がgoogle先生曰く5.5794083 × 10^26らしい。
問題の制約上、これで充分間に合う。

本番では、オーバーフローのことを考えていなかった。ツラい。