kwm_t

kwm_tのメモ

Codeforces Round #776 (Div. 3)

unratedなので欠席
■A. Deletions of Two Adjacent Letters
奇数文字目にあるかどうか
■B. DIV + MOD
最大になる可能性があるのは、最後か
modがa-1になる最大のもの
■C. Weight of the System of Nested Segments
小さいものを貪欲に
座標とindexとvalueを上手に持ってsort
■D. Twist the Permutation
右端からもとに戻していく
■E. Rescheduling the Exam
動かすのは、いま最小の区間になっている部分の右か左になるもの
移動先は、区間の真ん中か右端。
■F. Vitaly and Advanced Useless Algorithms
問題ごとにナップサックdpとその復元を行う
■G. Counting Shortcuts
EやFより簡単。
まず各張点に対する最短距離をdfsで求める。
次にdp[i][j(0,1)]:=頂点iに最短距離+jで到達する通り数などとしてdfsを行う。