https://atcoder.jp/contests/abc143/tasks/abc143_a 解説 https://atcoder.jp/contests/abc143/submissions/8035132 カーテンを横並びにして横の長さを2Bにするのが隠せる最大になる。 なので、A-2Bが答えであるが、負になる可能性がある。 こういうときは…

https://atcoder.jp/contests/abc143/tasks/abc143_b 解説 https://atcoder.jp/contests/abc143/submissions/8035678 制約を見るとN個のたこ焼きから2個を選ぶ組み合わせは全探索できる。 なので、組み合わせを全探索して、回復量の総和を求めよう。 int N, …

https://yukicoder.me/problems/no/911 前提知識 桁DP XOR 解説 https://yukicoder.me/submissions/391670 まずはいつもの区間テクを使おう。 [L,R]区間で選んだときの答えであるが、[1,R]-[1,L)としよう。 なので、[1,X]区間でxを選んだときの答えを求めよ…

https://yukicoder.me/problems/no/913 前提知識 列の分割統治 CHT 解説 https://yukicoder.me/submissions/391706 分割統治+CHTで解く。 こういう系の問題に初めて取り組む場合は、まずは「列の分割統治」と「CHT」について学ぼう。 この2つが理解できてい…

https://yukicoder.me/problems/no/908 解説 https://yukicoder.me/submissions/391136 うしたぷにきあくん文字列である条件を確認すればいい。 1列取得したいときはgetline関数を使うといい。 ダメなパターンをチェックする。 「奇数番目で空白があるとき」…

https://yukicoder.me/problems/no/910 解説 https://yukicoder.me/submissions/391664 サンプル1で97を削除しているが、これは7に変えても問題ない。 つまり、削除するときに最小単位があるような気がする。 3 5 7 これは個別に消すのがいい。1つで1回稼げ…

https://yukicoder.me/problems/no/909 解説 https://yukicoder.me/submissions/391180 たぴ1から考えてみると、なるべく離したいので、たぴ0からXiの距離に置きたい。 あと、たぴN+1とも極力離したいので、Yiの距離に置きたい。 すると、Xi+Yiだけの距離が…

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_g ジャンル 構築 解説 https://atcoder.jp/contests/kupc2019/submissions/7962102 そういう作り方の構築は初めて見たかもしれない。 最小は4×4なので、とりあえずこれから作ってみるが、もう作ってあ…

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_e 解説 https://atcoder.jp/contests/kupc2019/submissions/7961395 最後に相手ターンでスタート地点に戻せば、こちらの勝ちになる。 各木に一旦入ったら抜け出すまでは他の木は関係無くなるので、木に…

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_c 解説 https://atcoder.jp/contests/kupc2019/submissions/7961542 最初の分銅は1gにする。 すると、1～Kgは測れる。 次に用意する分銅はK+1としたい所だが、(2K+1)gを用意すればいい。 例えば、K+1g…

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_f 前提知識 二次元累積和 解説 https://atcoder.jp/contests/kupc2019/submissions/7958884 最適方針として、なるべく1人の勇者に攻撃を集中させるのが得策。 なんとなくDP感がするので、DPで考えてみ…

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_a 解説 https://atcoder.jp/contests/kupc2019/submissions/7955954 あるテーマが選ばれる可能性を最大化したい場合は、そのテーマにX票すべて与えるのがいい。 よって、X票すべて与えたときに投票数が…

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_b 前提知識 UnionFind DP 解説 https://atcoder.jp/contests/kupc2019/submissions/7956197 ナップサック問題の派生であるが、追加されてる条件について考えてみる。 aとbを一緒に入れる必要があり、b…

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_d 前提知識 カタラン数 解説 https://atcoder.jp/contests/kupc2019/submissions/7958349 順列を2グループに分けていく問題であるが、小さいほうから確定させていくことを考える。 01を作る場合は 千| …

https://yukicoder.me/problems/no/906 解説 https://yukicoder.me/submissions/389459 数列辞典にかけたい気持ちをぐっとこらえて考察する。 玉の分配を考えてみると、N個のうち4つはもう分配が決まっている。 次数3の玉が1つ。そこから3路あるが、それぞれ…

https://yukicoder.me/problems/no/903 解説 https://yukicoder.me/submissions/389261 シンプルな数学の問題。 N通りのパターンから、ある1つのパターンがでる確率は1/Nである。 よって、1/Nをこたえるが、整数型でやると0になってしまうので、double型にし…

https://yukicoder.me/problems/no/904 解説 https://yukicoder.me/submissions/389278 難しい。 何もわからないが、Nが小さいのが気になる。 まず、わかることとして、Aの総和＝Bの総和であることは自明。 A1が決まると、Aの総和＝Bの総和なので、B1も一意…

https://yukicoder.me/problems/no/905 解説 https://yukicoder.me/submissions/389294 ある列が広義単調増加列であるというのは、各要素間でA[i]≦A[i+1]であればいい。 A[i]≦A[i+1]であるなら1、そうでないなら0であるとすると、すべての要素間が1であれば…

https://www.hackerrank.com/contests/wasedajitsugyo-scienceclub-festival-contest2019/challenges/yoppys-frendship 解説 https://www.hackerrank.com/contests/wasedajitsugyo-scienceclub-festival-contest2019/challenges/yoppys-frendship/submission…

前提知識 区間スケジューリング問題 解説 https://www.hackerrank.com/contests/wasedajitsugyo-scienceclub-festival-contest2019/challenges/yoppinwork/submissions/code/1316764099 この問題は、区間スケジューリング問題と呼ばれるものである。 区間ス…

https://www.hackerrank.com/contests/wasedajitsugyo-scienceclub-festival-contest2019/challenges/yoppinparty 解説 https://www.hackerrank.com/contests/wasedajitsugyo-scienceclub-festival-contest2019/challenges/yoppinparty/submissions/code/131…

解説 https://www.hackerrank.com/contests/wasedajitsugyo-scienceclub-festival-contest2019/challenges/soujitsu-query/submissions/code/1316764213 集合に含まれる数を保持したsetも持ちながら2番目の数を特定しよう。 要素の個数はmapで持っておけばい…

解説 https://www.hackerrank.com/contests/wasedajitsugyo-scienceclub-festival-contest2019/challenges/team-ayutaya1/submissions/code/1316764060 XがN以上であればYesであり、そうでないならNoである。 int N, X; //---------------------------------…

前提知識 Grundy数 解説 https://www.hackerrank.com/contests/wasedajitsugyo-scienceclub-festival-contest2019/challenges/number-saying-game/submissions/code/1316764352 Nim派生問題感がある。 だが、Nimと違うのが最後の数を言ったほうが負けという…

https://www.hackerrank.com/contests/wasedajitsugyo-scienceclub-festival-contest2019/challenges/cut-the-sequence-into-three 解説 https://www.hackerrank.com/contests/wasedajitsugyo-scienceclub-festival-contest2019/challenges/cut-the-sequence…

https://yukicoder.me/problems/no/901 前提知識 LCA 解説 https://yukicoder.me/submissions/387110 この問題の上位互換であるが、本質的には同じ解法を使える。 与えられた頂点をEuler Tourでの順番にソートすると、(v1->v2の距離+v2->v3の距離+...+vN->v1…

https://yukicoder.me/problems/no/899 前提知識 オイラーツアー 解説 https://yukicoder.me/submissions/387104 操作を見ると、妖精がいる頂点数がどんどん減っている。 頂点を削減しながら、順番に見ていく的なことをしていくのかな… わからんとなったが… …

https://yukicoder.me/problems/no/900 前提知識 HL分解 遅延評価セグメントツリー(区間add,区間sum) 解説 https://yukicoder.me/submissions/387106 クエリを見ると部分木クエリとパスクエリになっている。 木に対して部分木もパスも行けるHL分解という手法…

https://yukicoder.me/problems/no/898 前提知識 LCA 解説 https://yukicoder.me/submissions/387102 頂点数が最小で連結な部分グラフを持ってくるが、 これはx-y, x-z, y-z間の最小パスで使われる頂点を集めたものになる。 これは直感的に分かるかもしれな…

https://yukicoder.me/problems/no/897 解説 https://yukicoder.me/submissions/386980 深さを最小化したいなら、なるべく子供をK個にするのがいい。 そうすると、密度が高まり、多くの頂点で深さを最小化できる。 あとは、計算だが、深さ基準で考えよう。 …