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

hamayanhamayan's blog

2019-10-19から1日間の記事一覧

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だけの距離が…