21(火)
22(水)
23(木)
24(金)
25(土)
Chokudai SpeedRun 002に参加．全完セットだったと思うのに解けなくて悔しい．
種類数β
$O(N^{\frac{3}{2}})$のフローでやってしまったので想定解法の復習．
値をつなぐ辺をもとにグラフをつくる．閉路ができなければ必ず辺の数だけ選択をすることが可能．
閉路がある場合は頂点の分しか取れないので，UnionFind等で連結成分のサイズと含まれる辺の数を管理して小さい方を取れば良い．
僕はクエリを処理できるように改造してある．
submission長方形β
見るからに2DLIS．縦横入れ替えたものを混ぜて入れても問題ないので入れて終わり．この発想ができないのダメすぎる．
ABC127に参加．
読み込みが速くなっていて嬉しかった．結果はさんざんだった．
ABC127 F Absolute Minima
手を動かすと中央値になる．(前回の結果に比べて関数を変化させた時差分はpoint1だけ．)
オフラインなので座圧+BITで中央値は求められる．(平衡木やゲタ+BinaryTrieにすればオンラインでも．)
あとは値を求める事ができれば良い．
これは2つBITをもって左右を上手に求める．
最初にやるべきだった…
submissionABC127 E わからないのでとにかく実験しまくる．40分かけて一般項を出せたので良かった．(奇跡)
以下本来考えるべき部分．
縦横独立に求めることができる．
sumの式をK=2としてO(H)ぐらいで求めておく．
これがK>2で何度も足されることがわかるので，この回数を考える．
HW-2箇所からK-2個とるのでこの組み合わせをかけ合わせれば良い．
賢いね．
submission
26(日)
AOJ 2566 Restore Calculation
虫食い算が何通りあるかを求める．桁あがりがあることを考慮すると，$dp(i,carry)$:=下からi番目の数字までみたときに，carryだけ桁上がる場合の数としてdpできる．
?のときは0から9まで全部ためすような実装にする．
こういうのは所見でdpと見抜けないとダメ．AOJ 2236 Rabbit Plays Games!
順番を定義できないとまず解けない問題．A，Bをどちらを先に倒すかを考えたい．
それぞれを先に倒すパターンについて被ダメージを式で表すと順序付け可能で，ソート可能である事がわかる．
あとはシュミレーションすれば良い．
お互いにダメージ0のパターンの処理ができていなくてWAを出し続けた．
A Wiggle Walk
https://atcoder.jp/contests/arc039/tasks/arc039_c と一緒．B CircuitBorad
まず横幅を$O(W^2)$で決める．
全ての行についてこの幅の部分のmaxとminの差がK以下であるかを確認しておく．
ある幅について，当てはまるののの連続部分列の最大値と横幅の積が答えとなる． 10分で解きたい問題．25分かかった．C Catch Some
選び方は可換なのでナップサックDPみたいにできる．
ある選び方について往復しないとするときに遷移が起きるとする．
$dp(k,2):=k$匹みたときの移動最小値(bool:片道を加算したか?)とすればよい．ABC 128に参加． Eで解法はただしいが数値がずれているのに気づかず散々だった．図をキレイに書くのを心がけるようにした．
27(月)
AOJ 350を少し解いた．
28(火)
AOJ 350を少し解いた．
29(水)
AOJ 350を少し解いた．
- AOJ 2601 避難
解説 解法3とセグ木の1が思いついた．解法2がむずい．
30(木)
AOJ 350を全部解いた．
- nagoya university virtual contest 11に参加．
- AOJ 2536 Median Tree
離散凸解析を読んでいるか天才だと解ける．
全域木の最小・最大の辺を最小化しようとすると最小全域木を作るのはすぐ分かるし，二番目に小さい辺を最小化するのでもすぐ分かる．中央値だとぱっと浮かばないのはなぜだろう．
31(金)
- nagoya university virtual contest 12に参加．
まだまだだなあと思った． 問題のアプローチを参加している人からたくさん聞けてよかった．
AOJ 400を少し解いた．
来週末までに400全部埋めます．