https://atcoder.jp/contests/abc143/tasks/abc143_f 前提知識 調和級数計算量 解説 https://atcoder.jp/contests/abc143/submissions/8049281 Kと答えansが固定されているときに何が起こるかを考える。 ansが固定されていると、ある種類の数は最大ans回しか…
![はてなブックマーク - Distinct Numbers [AtCoder Beginner Contest 143 F]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/20/001048)
https://atcoder.jp/contests/abc143/tasks/abc143_c 解説 https://atcoder.jp/contests/abc143/submissions/8036277 連続する同じ色（文字）を1つにまとめると何グループできるかという問題。 ランレングス表現というのがある。 これは連続してどれだけの文…
![はてなブックマーク - Slimes [AtCoder Beginner Contest 143 C]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/19/234640)
https://atcoder.jp/contests/abc143/tasks/abc143_f 前提知識 調和級数計算量 解説 https://atcoder.jp/contests/abc143/submissions/8049281 Kと答えansが固定されているときに何が起こるかを考える。 ansが固定されていると、ある種類の数は最大ans回しか…
![はてなブックマーク - Distinct Numbers [AtCoder Beginner Contest 143 F]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/19/231048)
https://atcoder.jp/contests/abc143/tasks/abc143_e 前提知識 ワーシャルフロイド 解説 https://atcoder.jp/contests/abc143/submissions/8041800 問題としては最短経路問題に似ている。 似ているが、燃料が足りなくなったらコストが1かかるという部分。 燃…
![はてなブックマーク - Travel by Car [AtCoder Beginner Contest 143 E]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/19/231028)
https://atcoder.jp/contests/abc143/tasks/abc143_d 前提知識 累積和 解説 https://atcoder.jp/contests/abc143/submissions/8038987 まずは全探索を考える。 a,b,cを全探索して、条件を満たすか考える。 これは組み合わせが109くらいなのでダメ。 でも、a,…
![はてなブックマーク - Triangles [AtCoder Beginner Contest 143 D]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/19/224640_2)
https://atcoder.jp/contests/abc143/tasks/abc143_c 解説 https://atcoder.jp/contests/abc143/submissions/8036277 連続する同じ色（文字）を1つにまとめると何グループできるかという問題。 ランレングス表現というのがある。 これは連続してどれだけの文…
![はてなブックマーク - Slimes [AtCoder Beginner Contest 143 C]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/19/224640_1)
https://atcoder.jp/contests/abc143/tasks/abc143_a 解説 https://atcoder.jp/contests/abc143/submissions/8035132 カーテンを横並びにして横の長さを2Bにするのが隠せる最大になる。 なので、A-2Bが答えであるが、負になる可能性がある。 こういうときは…
![はてなブックマーク - Curtain [AtCoder Beginner Contest 143 A]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/19/224640)
https://atcoder.jp/contests/abc143/tasks/abc143_b 解説 https://atcoder.jp/contests/abc143/submissions/8035678 制約を見るとN個のたこ焼きから2個を選ぶ組み合わせは全探索できる。 なので、組み合わせを全探索して、回復量の総和を求めよう。 int N, …
![はてなブックマーク - TAKOYAKI FESTIVAL 2019 [AtCoder Beginner Contest 143 B]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/19/224638)
https://yukicoder.me/problems/no/911 前提知識 桁DP XOR 解説 https://yukicoder.me/submissions/391670 まずはいつもの区間テクを使おう。 [L,R]区間で選んだときの答えであるが、[1,R]-[1,L)としよう。 なので、[1,X]区間でxを選んだときの答えを求めよ…
![はてなブックマーク - ラッキーソート [yukicoder 911]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/19/114358_1)
https://yukicoder.me/problems/no/913 前提知識 列の分割統治 CHT 解説 https://yukicoder.me/submissions/391706 分割統治+CHTで解く。 こういう系の問題に初めて取り組む場合は、まずは「列の分割統治」と「CHT」について学ぼう。 この2つが理解できてい…
![はてなブックマーク - 木の燃やし方 [yukicoder 913]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/19/114358)
https://yukicoder.me/problems/no/908 解説 https://yukicoder.me/submissions/391136 うしたぷにきあくん文字列である条件を確認すればいい。 1列取得したいときはgetline関数を使うといい。 ダメなパターンをチェックする。 「奇数番目で空白があるとき」…
![はてなブックマーク - うしたぷにきあくん文字列 [yukicoder 908]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/19/114338)
https://yukicoder.me/problems/no/910 解説 https://yukicoder.me/submissions/391664 サンプル1で97を削除しているが、これは7に変えても問題ない。 つまり、削除するときに最小単位があるような気がする。 3 5 7 これは個別に消すのがいい。1つで1回稼げ…
![はてなブックマーク - 素数部分列 [yukicoder 910]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/19/114337_1)
https://yukicoder.me/problems/no/909 解説 https://yukicoder.me/submissions/391180 たぴ1から考えてみると、なるべく離したいので、たぴ0からXiの距離に置きたい。 あと、たぴN+1とも極力離したいので、Yiの距離に置きたい。 すると、Xi+Yiだけの距離が…
![はてなブックマーク - たぴの配置 [yukicoder 909]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/19/114337)
https://atcoder.jp/contests/kupc2019/tasks/kupc2019_g ジャンル 構築 解説 https://atcoder.jp/contests/kupc2019/submissions/7962102 そういう作り方の構築は初めて見たかもしれない。 最小は4×4なので、とりあえずこれから作ってみるが、もう作ってあ…
![はてなブックマーク - ABCのG問題 [Kyoto University Programming Contest 2019 G]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/13/195319)
https://atcoder.jp/contests/kupc2019/tasks/kupc2019_e 解説 https://atcoder.jp/contests/kupc2019/submissions/7961395 最後に相手ターンでスタート地点に戻せば、こちらの勝ちになる。 各木に一旦入ったら抜け出すまでは他の木は関係無くなるので、木に…
![はてなブックマーク - 根付き森二人用ゲーム [Kyoto University Programming Contest 2019 E]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/13/195319_1)
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…
![はてなブックマーク - てんびんばかり [Kyoto University Programming Contest 2019 C]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/13/195300)
https://atcoder.jp/contests/kupc2019/tasks/kupc2019_f 前提知識 二次元累積和 解説 https://atcoder.jp/contests/kupc2019/submissions/7958884 最適方針として、なるべく1人の勇者に攻撃を集中させるのが得策。 なんとなくDP感がするので、DPで考えてみ…
![はてなブックマーク - カズマ王国の陥落 [Kyoto University Programming Contest 2019 F]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/13/180445)
https://atcoder.jp/contests/kupc2019/tasks/kupc2019_a 解説 https://atcoder.jp/contests/kupc2019/submissions/7955954 あるテーマが選ばれる可能性を最大化したい場合は、そのテーマにX票すべて与えるのがいい。 よって、X票すべて与えたときに投票数が…
![はてなブックマーク - November Festival [Kyoto University Programming Contest 2019 A]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/13/180425_1)
https://atcoder.jp/contests/kupc2019/tasks/kupc2019_b 前提知識 UnionFind DP 解説 https://atcoder.jp/contests/kupc2019/submissions/7956197 ナップサック問題の派生であるが、追加されてる条件について考えてみる。 aとbを一緒に入れる必要があり、b…
![はてなブックマーク - ナップサック問題 [Kyoto University Programming Contest 2019 B]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/13/180425_2)
https://atcoder.jp/contests/kupc2019/tasks/kupc2019_d 前提知識 カタラン数 解説 https://atcoder.jp/contests/kupc2019/submissions/7958349 順列を2グループに分けていく問題であるが、小さいほうから確定させていくことを考える。 01を作る場合は 千| …
![はてなブックマーク - Maximin Game [Kyoto University Programming Contest 2019 D]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/13/180425)
https://yukicoder.me/problems/no/906 解説 https://yukicoder.me/submissions/389459 数列辞典にかけたい気持ちをぐっとこらえて考察する。 玉の分配を考えてみると、N個のうち4つはもう分配が決まっている。 次数3の玉が1つ。そこから3路あるが、それぞれ…
![はてなブックマーク - Y字グラフ [yukicoder 906]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/12/105320)
https://yukicoder.me/problems/no/903 解説 https://yukicoder.me/submissions/389261 シンプルな数学の問題。 N通りのパターンから、ある1つのパターンがでる確率は1/Nである。 よって、1/Nをこたえるが、整数型でやると0になってしまうので、double型にし…
![はてなブックマーク - 太郎の確率 [yukicoder 903]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/12/105300)
https://yukicoder.me/problems/no/904 解説 https://yukicoder.me/submissions/389278 難しい。 何もわからないが、Nが小さいのが気になる。 まず、わかることとして、Aの総和＝Bの総和であることは自明。 A1が決まると、Aの総和＝Bの総和なので、B1も一意…
![はてなブックマーク - サメトロ [yukicoder 904]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/12/105300_1)
https://yukicoder.me/problems/no/905 解説 https://yukicoder.me/submissions/389294 ある列が広義単調増加列であるというのは、各要素間でA[i]≦A[i+1]であればいい。 A[i]≦A[i+1]であるなら1、そうでないなら0であるとすると、すべての要素間が1であれば…
![はてなブックマーク - Sorted? [yukicoder 905]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/12/105258)
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…
![はてなブックマーク - Yoppy's FriendShip [WASEDAJITSUGYO_SCIENCECLUB_FESTIVAL_CONTEST2019 G]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/08/103232_2)
前提知識 区間スケジューリング問題 解説 https://www.hackerrank.com/contests/wasedajitsugyo-scienceclub-festival-contest2019/challenges/yoppinwork/submissions/code/1316764099 この問題は、区間スケジューリング問題と呼ばれるものである。 区間ス…
![はてなブックマーク - YoppinWork [WASEDAJITSUGYO_SCIENCECLUB_FESTIVAL_CONTEST2019 B]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/08/103232)
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…
![はてなブックマーク - YoppinParty [WASEDAJITSUGYO_SCIENCECLUB_FESTIVAL_CONTEST2019 F]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/08/103232_1)
解説 https://www.hackerrank.com/contests/wasedajitsugyo-scienceclub-festival-contest2019/challenges/soujitsu-query/submissions/code/1316764213 集合に含まれる数を保持したsetも持ちながら2番目の数を特定しよう。 要素の個数はmapで持っておけばい…
![はてなブックマーク - Soujitsu Query [WASEDAJITSUGYO_SCIENCECLUB_FESTIVAL_CONTEST2019 C]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/08/103213)
解説 https://www.hackerrank.com/contests/wasedajitsugyo-scienceclub-festival-contest2019/challenges/team-ayutaya1/submissions/code/1316764060 XがN以上であればYesであり、そうでないならNoである。 int N, X; //---------------------------------…
![はてなブックマーク - TeamAyutaya [WASEDAJITSUGYO_SCIENCECLUB_FESTIVAL_CONTEST2019 A]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/08/103212)
前提知識 Grundy数 解説 https://www.hackerrank.com/contests/wasedajitsugyo-scienceclub-festival-contest2019/challenges/number-saying-game/submissions/code/1316764352 Nim派生問題感がある。 だが、Nimと違うのが最後の数を言ったほうが負けという…
![はてなブックマーク - Number saying game [WASEDAJITSUGYO_SCIENCECLUB_FESTIVAL_CONTEST2019 D]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/10/08/103212_1)