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

hamayanhamayan's blog

競技プログラミング

Intervals on Tree [AtCoder Beginner Contest 173 F]

https://atcoder.jp/contests/abc173/tasks/abc173_f 解説 https://atcoder.jp/contests/abc173/submissions/15025119 さて、まずはf(L,R)というのが提示されているので、これについて考えていこう。 f(L,R) 連結成分の個数についての典型がある。 閉路が存…

Multiplication 4 [AtCoder Beginner Contest 173 E]

https://atcoder.jp/contests/abc173/tasks/abc173_e 解説 https://atcoder.jp/contests/abc173/submissions/15024432 貪欲法。コーナーケースが多く、実装も大変。 まず簡単な問題で考えてみる。 全て正の数であれば、数が大きいものから貪欲にK個とってい…

Chat in a Circle [AtCoder Beginner Contest 173 D]

https://atcoder.jp/contests/abc173/tasks/abc173_d 解説 https://atcoder.jp/contests/abc173/submissions/15023990 難しい問題。 「N人の到着順番や割り込む位置を適切に決める」とあるが、決めるべきことが多すぎる。 こういう時は、固定できそうな所を…

H and V [AtCoder Beginner Contest 173 C]

https://atcoder.jp/contests/abc173/tasks/abc173_c 解説 https://atcoder.jp/contests/abc173/submissions/15023668 実装問題であるが、bit全探索の書き方を知らない場合は解くのは難しいだろう。 どこかで勉強してから、この問題に戻ってくること。 この…

Judge Status Summary [AtCoder Beginner Contest 173 B]

https://atcoder.jp/contests/abc173/tasks/abc173_b 解説 https://atcoder.jp/contests/abc173/submissions/15023533 実装問題。 問題に書かれている文字列を間違えて記載してしまうのは一番悲しいので、 必ずコピペで持ってこよう。 あとは、4種類について…

Payment [AtCoder Beginner Contest 173 A]

https://atcoder.jp/contests/abc173/tasks/abc173_a 解説 https://atcoder.jp/contests/abc173/submissions/15023450 支払い上限は1万円なので、1000円札10枚を出しておこう。 すると、おつりで1000円札が帰ってくるので、帰ってきた分は本来出さなくていい…

Sum of Divisors [AtCoder Beginner Contest 172 D]

https://atcoder.jp/contests/abc172/tasks/abc172_d 前提知識 エラトステネスの篩 解説 https://atcoder.jp/contests/abc172/submissions/14777943 [1,K]の約数の個数を効率的に数え上げる必要がある。 以下のことを知っているとエラトステネスの篩が思いつ…

Tsundoku [AtCoder Beginner Contest 172 C]

https://atcoder.jp/contests/abc172/tasks/abc172_c 前提知識 尺取り法 解説 https://atcoder.jp/contests/abc172/submissions/14779347 まずは全探索で考えてみる 机Aからa冊、机Bからb冊取り除くとする。 すると、必要な時間が、A[1]+A[2]+...+A[a] + B[1…

Minor Change [AtCoder Beginner Contest 172 B]

https://atcoder.jp/contests/abc172/tasks/abc172_b 解説 https://atcoder.jp/contests/abc172/submissions/14779477 操作回数の最小値を達成するには、文字が違う場所のみ変換する必要がある。 なので、S[i]!=T[i]であるiの個数が必要な最小回数となる。 …

Calc [AtCoder Beginner Contest 172 A]

https://atcoder.jp/contests/abc172/tasks/abc172_a 解説 https://atcoder.jp/contests/abc172/submissions/14779528 問題文で提示されている計算を行う。 for文を使って工夫してもいいし、タイピング頑張ってもいい。 自分はタイピングを頑張った。 int a;…

Unfair Nim [AtCoder Beginner Contest 172 F]

https://atcoder.jp/contests/abc172/tasks/abc172_f 前提知識 Nim XOR系の知識 桁DP 解説 https://atcoder.jp/contests/abc172/submissions/14771442 今回の問題はNimを知っていないと解くのは不可能である。 問題の前半部分で説明している、山を1つ選んで…

NEQ [AtCoder Beginner Contest 172 E]

https://atcoder.jp/contests/abc172/tasks/abc172_e 前提知識 個数系包除原理 素数mod上での二項係数 解説 https://atcoder.jp/contests/abc172/submissions/14774888 もうこの手の問題をやりすぎて、何となく包除かな?という所からそれっぽいコードを書い…

Strivore [AtCoder Beginner Contest 171 F]

https://atcoder.jp/contests/abc171/tasks/abc171_f 前提知識 数え上げテク greedyからの帰着 解説 https://atcoder.jp/contests/abc171/submissions/14635205 数え上げで最も気にするべきことは、重複して数えてしまわないかということである。 今回も問題…

Red Scarf [AtCoder Beginner Contest 171 E]

https://atcoder.jp/contests/abc171/tasks/abc171_e 解説 https://atcoder.jp/contests/abc171/submissions/14625557 XORの性質を知っておく必要がある。 x ^ x = 0 x ^ 0 = x このルールから、全ての数のxorを取ったときに同じ数が複数個あった場合は2個セ…

Replacing [AtCoder Beginner Contest 171 D]

https://atcoder.jp/contests/abc171/tasks/abc171_d 解説 https://atcoder.jp/contests/abc171/submissions/14613838 高速シミュレーションを行う。 クエリ問題で毎回操作後の総和を答える必要があるが、差分だけ計算することで高速に求めよう。 B[i]である…

One Quadrillion and One Dalmatians [AtCoder Beginner Contest 171 C]

https://atcoder.jp/contests/abc171/tasks/abc171_c 解説 https://atcoder.jp/contests/abc171/submissions/14611823 難しい問題に見えるだろう。 こういう問題を見ると、~進数で見るような癖がついてしまっているので、そういう目線でどうしても見てしま…

Mix Juice [AtCoder Beginner Contest 171 B]

https://atcoder.jp/contests/abc171/tasks/abc171_b 解説 https://atcoder.jp/contests/abc171/submissions/14611203 貪欲解法で解ける。 合計価格を最小化したいので、なるべく価格の安い果物を買っていくのがいい。 よって、売っている果実の中で価格の安…

αlphabet [AtCoder Beginner Contest 171 A]

https://atcoder.jp/contests/abc171/tasks/abc171_a 解説 https://atcoder.jp/contests/abc171/submissions/14610931 大文字小文字の判定が求められているが、C++であればasciiで比較するのが手っ取り早い。 大文字ならAとZの間のasciiコードになるので、単…

Shift [AtCoder Grand Contest 046 C]

https://atcoder.jp/contests/agc046/tasks/agc046_c 解説 https://atcoder.jp/contests/agc046/submissions/14517640 DPだろうけど… mod数え上げなので、DPかなと感じではあるが、うまく条件をまとめ上げる必要があるので、 まとめ上げるための性質を探す。…

Extension [AtCoder Grand Contest 046 B]

https://atcoder.jp/contests/agc046/tasks/agc046_b 解説 https://atcoder.jp/contests/agc046/submissions/14512309 まずはDPから考えてみる とりあえずmod数え上げなので、DPから考えてみる。 制約からまず以下のDPをベースに考え始めてみる。 dp[h][w] :…

Takahashikun, The Strider [AtCoder Grand Contest 046 A]

https://atcoder.jp/contests/agc046/tasks/agc046_a 解説 https://atcoder.jp/contests/agc046/submissions/14511770 まず自明な所から考えてみると、 X=180, X=90, X=60みたいな正多角形で内角が整数であるものは360/Xが答えになっている。 X=100のような…

桁和の桁和2 [yukicoder 1086]

https://yukicoder.me/problems/no/1086 解説 https://yukicoder.me/submissions/500440 下位問題があるので、そちらがまだならそちらを解いてから、こちらを考えるといい。 基本的には、下位問題と似たような感じになる。 数列の要素を数字根を計算して、そ…

桁和の桁和 [yukicoder 1085]

https://yukicoder.me/problems/no/1085 前提知識 数字根(知っていれば早い) 動的計画法 解説 https://yukicoder.me/submissions/500381 数字根を知らないとかなり時間をロスすると思う。 ある数について桁和を取れるだけとった結果を数字根という。 数字…

積の積 [yukicoder 1084]

https://yukicoder.me/problems/no/1084 前提知識 区間積セグメントツリー(または、スパーステーブル) 二分探索 一次(関数)imos 解説 https://yukicoder.me/submissions/500368 複合的な知識が必要。 まずは、全探索対象が区間となっているが、区間の全探…

余りの余り [yukicoder 1083]

https://yukicoder.me/problems/no/1083 解説 https://yukicoder.me/submissions/499917 見た目に難しい問題。 Nの制約が異常に小さいので、O(N2N)かな…といういつものやつを頭の片隅に置きつつ考える。 配列Aを固定した場合を考えてみよう。 modを取るとき…

XORのXOR [yukicoder 1082]

https://yukicoder.me/problems/no/1082 解説 https://yukicoder.me/submissions/499879 配列Aが固定されている場面でまずは考えてみよう。 すると、 Xは B1 xor B2 xor B3 xor ... xor BN-1 (A1 xor A2) xor (A2 xor A3) xor (A3 xor A4) xor ... xor (AN-1…

和の和 [yukicoder 1081]

https://yukicoder.me/problems/no/1081 解説 https://yukicoder.me/submissions/499832 シミュレーションをしていこう。 具体的には、A[i] += A[i + 1]を全部の要素に行うことをN - 1回やればいい。 すると、A[0]が答えになる。 もっと賢くやることもできそ…

Pond Skater [AtCoder Beginner Contest 170 F]

https://atcoder.jp/contests/abc170/tasks/abc170_f 解説 https://atcoder.jp/contests/abc170/submissions/14369162 後追いで解いて、色々な解法を目にしてしまったので、以下にまとめておく。 3種類見かけた。 難易度はどれもどれという感じもしているの…

Smart Infants [AtCoder Beginner Contest 170 E]

https://atcoder.jp/contests/abc170/tasks/abc170_e 前提知識 multiset 区間minセグメントツリー 解説 https://atcoder.jp/contests/abc170/submissions/14365126 シミュレーション高速化の問題。 データ構造をうまく使ってシミュレーションを高速化しよう…

Not Divisible [AtCoder Beginner Contest 170 D]

https://atcoder.jp/contests/abc170/tasks/abc170_d 前提知識 調和級数的計算量 解説 https://atcoder.jp/contests/abc170/submissions/14362889 この問題は調和級数的計算量を知らないと難しいかもしれない。 つまるところ、 「rep(i,1,N) for(j=i;j<=N;j+…