SRM 628 Div2 Codeforces #264 Div2
SRM 628
Easy
ビジョップを使って、最低何手で(r1, c1)から(r2, c2)にたどり着けるか？たどり着けない場合は-1を出力。
BFSで解いた。ビジョップの移動をシュミレートするだけ。
Med
'(',')','[',']','{','}','X'からなる文字列が与えられる。Xはどの文字にもなれる。
exp := ""
exp := "(exp)" | "[exp]" | "{exp}"
expが成り立つなら。"possible"。無理なら"impossible"とする。
全探索で解いた。stackで構文が成り立つか
Hard
ごめん。わからない。集合とかの話。
Codeforces #264 Div2
C
ビジョップを2つ置く。もっとも点数が高くなる場所はどこか。
解けない。斜めの累積和を取る。(y+x)%2が同じならカブる部分ができるので必要ない。単純に合計するだけでいい。それぞれの最大値を求める。O(N2)。
D
K個の整数列のLCS(最長共通部分列)を求める。普通にDPしようと思ったら、O(NK)でした。絶対無理。
数列をひとつずつ見ていくと、この数字はこの数字の後ろには来てはいけないというのがわかる。すべての数列に対して、どの数字がどの数字の後ろに来ちゃいけないかわかったら。1からNまでの数字に対して、この数字を先頭にした時のLCSを求めてく。各数字に対してO(N)なので全部でO(N2)で済む。前処理を含めてO(K*N+N2)でいいんでしょうか
E
N個の頂点からなる根付き木と各頂点の値がある。Q個のクエリを処理する。
わかりません。解説読んでもわからない
まとめ
SRMは2問、CFはABはすでに通したあったので飛ばして、CDを一回解説読んで写経して、自分で実装しなおした。とりあえずは理解できたと思う。HardとEは意味がわからない
精進が足りない
