はまやんはまやんはまやん

hamayanhamayan's blog

Distinct Numbers [AtCoder Beginner Contest 143 F]

https://atcoder.jp/contests/abc143/tasks/abc143_f 前提知識 調和級数計算量 解説 https://atcoder.jp/contests/abc143/submissions/8049281 Kと答えansが固定されているときに何が起こるかを考える。 ansが固定されていると、ある種類の数は最大ans回しか…

Slimes [AtCoder Beginner Contest 143 C]

https://atcoder.jp/contests/abc143/tasks/abc143_c 解説 https://atcoder.jp/contests/abc143/submissions/8036277 連続する同じ色(文字)を1つにまとめると何グループできるかという問題。 ランレングス表現というのがある。 これは連続してどれだけの文…

Distinct Numbers [AtCoder Beginner Contest 143 F]

https://atcoder.jp/contests/abc143/tasks/abc143_f 前提知識 調和級数計算量 解説 https://atcoder.jp/contests/abc143/submissions/8049281 Kと答えansが固定されているときに何が起こるかを考える。 ansが固定されていると、ある種類の数は最大ans回しか…

Travel by Car [AtCoder Beginner Contest 143 E]

https://atcoder.jp/contests/abc143/tasks/abc143_e 前提知識 ワーシャルフロイド 解説 https://atcoder.jp/contests/abc143/submissions/8041800 問題としては最短経路問題に似ている。 似ているが、燃料が足りなくなったらコストが1かかるという部分。 燃…

Triangles [AtCoder Beginner Contest 143 D]

https://atcoder.jp/contests/abc143/tasks/abc143_d 前提知識 累積和 解説 https://atcoder.jp/contests/abc143/submissions/8038987 まずは全探索を考える。 a,b,cを全探索して、条件を満たすか考える。 これは組み合わせが109くらいなのでダメ。 でも、a,…

Slimes [AtCoder Beginner Contest 143 C]

https://atcoder.jp/contests/abc143/tasks/abc143_c 解説 https://atcoder.jp/contests/abc143/submissions/8036277 連続する同じ色(文字)を1つにまとめると何グループできるかという問題。 ランレングス表現というのがある。 これは連続してどれだけの文…

Curtain [AtCoder Beginner Contest 143 A]

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

TAKOYAKI FESTIVAL 2019 [AtCoder Beginner Contest 143 B]

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

ラッキーソート [yukicoder 911]

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

木の燃やし方 [yukicoder 913]

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

うしたぷにきあくん文字列 [yukicoder 908]

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

素数部分列 [yukicoder 910]

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

たぴの配置 [yukicoder 909]

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

ABCのG問題 [Kyoto University Programming Contest 2019 G]

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

根付き森二人用ゲーム [Kyoto University Programming Contest 2019 E]

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

てんびんばかり [Kyoto University Programming Contest 2019 C]

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 F]

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

November Festival [Kyoto University Programming Contest 2019 A]

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

ナップサック問題 [Kyoto University Programming Contest 2019 B]

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

Maximin Game [Kyoto University Programming Contest 2019 D]

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

Y字グラフ [yukicoder 906]

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

太郎の確率 [yukicoder 903]

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

サメトロ [yukicoder 904]

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

Sorted? [yukicoder 905]

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

Yoppy's FriendShip [WASEDAJITSUGYO_SCIENCECLUB_FESTIVAL_CONTEST2019 G]

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…

YoppinWork [WASEDAJITSUGYO_SCIENCECLUB_FESTIVAL_CONTEST2019 B]

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

YoppinParty [WASEDAJITSUGYO_SCIENCECLUB_FESTIVAL_CONTEST2019 F]

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…

Soujitsu Query [WASEDAJITSUGYO_SCIENCECLUB_FESTIVAL_CONTEST2019 C]

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

TeamAyutaya [WASEDAJITSUGYO_SCIENCECLUB_FESTIVAL_CONTEST2019 A]

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

Number saying game [WASEDAJITSUGYO_SCIENCECLUB_FESTIVAL_CONTEST2019 D]

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