なつやすみ 48日目
眠いので手短に
- 片付けが少し進んだ
- No.377 銅Diffだけどかなり典型
ポリアの数え上げ定理が使えそう→ちょっと実験すると(0,0)と一致するマスの数はlcm(H,W)の約数になっていることがわかる→この時点で約数包除でなんとかできそうな気がする→さらに実験しまくると包除する前の関数がgcd(H,x)*gcd(W,x)なことがわかる→書くと通る
実際には実験しまくると〜のところが良くなくて、ここは普通に求めることができた 単純に(0,0)から(i,j)ずつ移動して(0,0)に戻ってくる手数は?という問題で、これはxだけに注目するとgcd(H,i) そのため、xy両方見ればlcm(gcd(H,i),gcd(W,j))なことが簡単にわかる これを丁寧に式変形していけば求まる - No.399 LCA+imosではい
- yukicoder contest 314 むずすぎ
A:45度回転した時に正方形内に入る点の個数
B:対称性と打ち消し
C:これがむずい 最初うまくナップサックとかに帰着できないかな〜と考えるけどできない 適当に実験コードを書くと規則性がわかる
どうやら1/2未満、1/2、1/2より大きいで式が閉じているのでDPができるらしい なるほどな〜〜〜
D:1つ決めると束縛条件が3つあるのでパラメータ4つが一意に定まる - JOI-CandiesとABC-H
解説見て放棄してたので埋めておいた なるほどな〜という感じ