7K12B blog

猫でも分かる何か

2020-03-01から1ヶ月間の記事一覧

ABC136 E - Max GCD

https://atcoder.jp/contests/abc136/submissions/11077726 diff1600を超えると数学的素養がないと考察を進めるのが厳しい。 理解はしたけど一生出来るようにならないという気分になった。 各操作をしても合計は不変 答えMはの約数 約数の個数は対数程度に収…

Educational DP Contest M - Candies

https://atcoder.jp/contests/dp/submissions/10545854 子供たちが飴を分け合うと言うと重複組み合わせっぽく見えるが、重複組み合わせだとDPが書きづらいので子供i-1から子供iに遷移するとき飴jがどうなるかというDPで実装する。このとき、K個の飴を配ると…

パナソニックプログラミングコンテスト2020

https://atcoder.jp/contests/panasonic2020/submissions?f.User=tkr987 根号の計算すら出来ない人間に価値なし。情けない。 直近5回のコンテストで3回も1年前と変わらないパフォとか冗談でなく虚無でしかない。 A - Kth Term https://atcoder.jp/contests/p…

ABC134 E - Sequence Decomposing

https://atcoder.jp/contests/abc134/submissions/10792162 二分探索の応用範囲が広すぎて困る。 分解数最小の増加部分列を作るという処理は、小さい積み木の上に大きい積み木を積み上げていくイメージになる。このとき、なるべく積み木の列が少なくなるよう…

重み付きUnionFind木

重み付きUnionFind(ポテンシャル付きUnionFind)は差分制約系 (牛ゲー) の処理が出来る。 Union(x, y, 10); Union(y, z, 20); を実行すると Diff(x, z) の戻り値で30が返ってくる。 この性質を利用するとABC087Dなどがライブラリをコピペするだけで解ける。…

ABC158の感想

https://atcoder.jp/contests/abc158/submissions?f.User=tkr987 A - Station and Bus https://atcoder.jp/contests/abc158/submissions/10589804 難問。問題文の意味が分からなかったのでサンプルからエスパーした。 B - Count Balls https://atcoder.jp/co…

IQテスト💩

https://not-522.appspot.com/contest/5683583224119296 虚無と言いつつ苦労したわけだが…(^^; なんだこれIQテストか?糞ゲー いや自分の地頭力がなんだよな 萎える A - Infinite Coins https://atcoder.jp/contests/abc088/submissions/10496614 う B -…

ABC133 E - Virus Tree 2

https://atcoder.jp/contests/abc133/submissions/10504611 今回も地頭力なさすぎて解説ACになってしまった…知識的に足りないものはないのに。 根はK色で塗れる。根に隣接する頂点数をcとすると色で塗れる。孫の頂点をcとすると親と親の親の2色引いて色にな…

MinMax法

https://atcoder.jp/contests/dp/submissions/10388277 MinMax法を実装するために以下を暗記すると効率が良いと思う。 片方min片方maxでdp漸化式を書く 最大化するときは+a[i]、最小化するときは-a[i]で符号を変えるだけで対応できる ただし、これだけの知識…