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

hamayanhamayan's blog

競技プログラミング

Keep Distances [ACL Contest 1 D]

https://atcoder.jp/contests/acl1/tasks/acl1_d 解説 https://atcoder.jp/contests/acl1/submissions/16924046 強実装問題。 クエリ問題は1クエリではどう解くかを考えよう まずは1つのクエリに対してどうやって解くかを考えていこう。 「よい集合の和集合…

Moving Pieces [ACL Contest 1 C]

https://atcoder.jp/contests/acl1/tasks/acl1_c 解説 https://atcoder.jp/contests/acl1/submissions/16923883 ACLコンテストということで、最小費用流が何とか出てきた。 ACLじゃなきゃ思いついていないかも。 最小費用流が分からない場合は、先にどこかで…

Sum is Multiple [ACL Contest 1 B]

https://atcoder.jp/contests/acl1/tasks/acl1_b 解説 https://atcoder.jp/contests/acl1/submissions/16923688 1h考えてmodのもの字も出てこなかった… 大学受験で出てきそうな問題。 言い換え この言い換えはできた。 (1+2+...+K)=aN K(K+1)/2=aN K(K+1)=2a…

Reachable Towns [ACL Contest 1 A]

https://atcoder.jp/contests/acl1/tasks/acl1_a 解説 https://atcoder.jp/contests/acl1/submissions/16923085 まず、x,y座標がともに小さい街への移動と、x,y座標がともに大きい街への移動は 片方ができればもう片方もできるような移動になっている。 かつ…

Brave CHAIN [AtCoder Beginner Contest 176 F]

https://atcoder.jp/contests/abc176/tasks/abc176_f 前提知識 インラインDP 解説 https://atcoder.jp/contests/abc176/submissions/16164487 難しい問題。方針自体はやったことがあれば、すんなり出てくるかもしれないが、 効率的な実装方針決め、正確な場…

Sum is XOR [yukicoder 1189]

https://yukicoder.me/problems/no/1189 解説 https://yukicoder.me/submissions/538264 制約を順番に見ていこう。 まず、総和とXOR和が等しくなる条件というのは、数列BをすべてANDしたときに0になることが必要である。 これは総和で繰り上がりが発生してし…

レベルX門松列 [yukicoder 1188]

https://yukicoder.me/problems/no/1188 解説 https://yukicoder.me/submissions/538073 何か全探索できそうな部分は無いだろうか。 もう少し具体的に言うと、固定してしまうと嬉しいような部分が無いだろうか。 中心を固定する B[X+1]が固定されていたとす…

長方形の敷き詰め [yukicoder 1186]

https://yukicoder.me/problems/no/1186 解説 https://yukicoder.me/submissions/537703 パッと見て、難しい問題に見えるが、ピースの横幅と、長方形の縦幅が一致している所に弱点がある。 M < Nのとき このとき、ピースを横置きしていくしかない。 これは1…

完全な3の倍数 [yukicoder 1185]

https://yukicoder.me/problems/no/1185 解説 https://yukicoder.me/submissions/537221 特徴的な条件として、任意の桁の組において、数の和が3の倍数である必要がある。 よって、求めたい数字は0369を使って作れる数のことになる。 …と思いきやサンプルをみ…

Hà Nội [yukicoder 1184]

https://yukicoder.me/problems/no/1184 解説 https://yukicoder.me/submissions/536895 星1.5であるが、割と難しい問題に見える。 だが、理由があって星1.5になっているのであって、なるべくシンプルに考察を進める。 面倒な条件は何か L枚以下の板なら1回…

コイン遊び [yukicoder 1183]

https://yukicoder.me/problems/no/1183 解説 https://yukicoder.me/submissions/536748 区間swapを行ってA=Bにしたいという問題である。 ここで区間操作に関するテクを使用する。 「区間操作は階差数列を取ることで2点要素更新に帰着させることができる」 …

Welcome [yukicoder 1182]

https://yukicoder.me/problems/no/1182 解説 https://yukicoder.me/submissions/537274 Writer, Testerは以下の方々。順は適当です。 defineさん Thistleさん capra314cabraさん sanada_atcoderさん penguinmanさん kaageさん Rhoさん AndrewKさん NatsubiS…

Product Modulo [AtCoder Grand Contest 047 C]

https://atcoder.jp/contests/agc047/tasks/agc047_c 前提知識 FFT/NTT 原子根 解説 https://atcoder.jp/contests/agc047/submissions/15795698 隠してはあるが、最初の1手が分かれば一気に(高度)典型化する。 主客転倒 全ての組み合わせに対して、とある…

First Second [AtCoder Grand Contest 047 B]

https://atcoder.jp/contests/agc047/tasks/agc047_b 前提知識 Trie (想定解) ローリングハッシュ (hamayanhamayan解法) 解説 https://atcoder.jp/contests/agc047/submissions/15795474 複数文字列なので、最初にTrieが思い浮かんだが、よくよく考える…

Integer Product [AtCoder Grand Contest 047 A]

https://atcoder.jp/contests/agc047/tasks/agc047_a 解説 https://atcoder.jp/contests/agc047/submissions/15792907 実数の積をそのまま受け取って積が整数である問題であるが、 実数の形のまま計算して、積が整数であるかを判定するのは誤差的にだいぶ怖…

面積Nの三角形 [yukicoder 1143]

https://yukicoder.me/problems/no/1143 前提知識 ヘロンの公式 高度合成数 解説 https://yukicoder.me/submissions/523047 上に前提知識がもし書いてあれば、そちらを先に学習しましょう(ここではちゃんと解説しないです) あまり見ないような問題。 自分…

XOR と XOR [yukicoder 1142]

https://yukicoder.me/problems/no/1142 解説 https://yukicoder.me/submissions/522991 上に前提知識がもし書いてあれば、そちらを先に学習しましょう(ここではちゃんと解説しないです) どこから考えようか迷うと思う。 制約から弱点を抜きだそう。 a[i],…

田グリッド [yukicoder 1141]

https://yukicoder.me/problems/no/1141 前提知識 2次元累積和 解説 https://yukicoder.me/submissions/522972 上に前提知識がもし書いてあれば、そちらを先に学習しましょう(ここではちゃんと解説しないです) ちょっと難しい。 ある矩形についての操作を…

EXPotentiaLLL! [yukicoder 1140]

https://yukicoder.me/problems/no/1140 前提知識 素数判定 フェルマーの小定理 解説 https://yukicoder.me/submissions/522953 難しい問題に見える。要求事項として、以下がある。 Pが素数かを判定 Pが素数ならmodP上で、AのP!乗を計算せよ Pが素数かを判定…

Slime Race [yukicoder 1139]

https://yukicoder.me/problems/no/1139 解説 https://yukicoder.me/submissions/522943 パッと見て、星1.5の問題には見えないので、うまい性質を見抜く問題だろうなとあたりをつける。 うまい性質 全てのスライムが走った距離を求めるが、衝突がない場合は…

Two Snuke [エイシング プログラミング コンテスト 2020 F]

https://atcoder.jp/contests/aising2020/tasks/aising2020_f 今回はちょっと変則的に解説する。 3種類の方針を解説する。 アルメリアさん解法「積の和を組合せに変換してラグランジュ補間」 公式解説解法「積の和を組合せに変換してDPを作って行列累乗」 形…

Anything Goes to Zero [エイシング プログラミング コンテスト 2020 D]

https://atcoder.jp/contests/aising2020/tasks/aising2020_d 解説 https://atcoder.jp/contests/aising2020/submissions/15187557 実装が大変な問題。 順番に考えていこう。 操作の特性 今回の操作を見てみると、popcountの結果の最大値はNなので、 1回操作…

XYZ Triplets [エイシング プログラミング コンテスト 2020 C]

https://atcoder.jp/contests/aising2020/tasks/aising2020_c 解説 https://atcoder.jp/contests/aising2020/submissions/15185161 こういう系が初見だと何から手を付ければいいか分からないかもしれない。 基本は全探索なので、全探索を考える。 Nをそれぞ…

An Odd Problem [エイシング プログラミング コンテスト 2020 B]

https://atcoder.jp/contests/aising2020/tasks/aising2020_b 解説 https://atcoder.jp/contests/aising2020/submissions/15184778 配列の個数は100個くらいなので、全探索可能。 全探索して条件を満たすマスを数え上げよう。 int N, a[101]; //------------…

Number of Multiples [エイシング プログラミング コンテスト 2020 A]

https://atcoder.jp/contests/aising2020/tasks/aising2020_a 解説 https://atcoder.jp/contests/aising2020/submissions/15184641 愚直にやる。 [L,R]の範囲は100通りくらいなので、全探索して、dの倍数の個数を数えればいい。 int L, R, d; //------------…

冥界の音楽 [yukicoder 1112]

https://yukicoder.me/problems/no/1112 前提知識 行列累乗によるDP更新最適化 解説 https://yukicoder.me/submissions/510596 知っていれば行列累乗が最初に候補に挙がってくる問題。 操作が1018回ある問題なので、logNにする必要はあり、数学的にパッと解…

コード進行 [yukicoder 1111]

https://yukicoder.me/problems/no/1111 前提知識 動的計画法 解説 https://yukicoder.me/submissions/510572 mod109+7数え上げなので、まずはDP。 先頭から順番に決めていくとして、最後の要素だけがそれ以降の処理に関係してくるし…DPだな 動的計画法 dp[i…

好きな歌 [yukicoder 1110]

https://yukicoder.me/problems/no/1110 解説 https://yukicoder.me/submissions/510561 条件の言い換え 条件を少し言い換えよう。 iについて全探索して、jを数え上げるので、A[i]は固定になるので、固定じゃないjについて簡単にする。 A[i] - A[j]≧D A[i] -…

調の判定 [yukicoder 1109]

https://yukicoder.me/problems/no/1109 解説 https://yukicoder.me/submissions/510555 全てのDについて全探索しよう。 あるDの音階が含まれるかどうかを判定する。 setを使うのがオススメ。 setに配列Tを全部入れて、 Dの音階に含まれる音を消せるだけ消し…

移調 [yukicoder 1108]

https://yukicoder.me/problems/no/1108 解説 https://yukicoder.me/submissions/510549 配列Tを読み込んで、全部の要素に+Hをして出力する。 特に注意点はないな。 int N, H, T[101]; //-----------------------------------------------------------------…