読者です 読者をやめる 読者になる 読者になる

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は意味がわからない

精進が足りない