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

hamayanhamayan's blog

競技プログラミング

Lamps [HHKB プログラミングコンテスト 2020 E]

https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_e 前提知識 主客転倒 二次元累積和 二分探索 解説 https://atcoder.jp/contests/hhkb2020/submissions/17319314 初めて見る人には何から手を付けるべきか分からない問題であるように思う。 2K通りをす…

Squares [HHKB プログラミングコンテスト 2020 D]

https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_d 解説 https://atcoder.jp/contests/hhkb2020/submissions/17318367 色々な考察が必要で、方針もたくさん見えるような問題。 引くべき方針1「余事象」 今回は余事象を考えるとすっきりする。 つまり、…

Neq Min [HHKB プログラミングコンテスト 2020 C]

https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_c 解説 https://atcoder.jp/contests/hhkb2020/submissions/17316773 こういったクエリ問題では、1クエリだけの場合ではどのように答えるかを考える。 i=Nの場合は? いずれとも等しくない値で、かつ、…

Futon [HHKB プログラミングコンテスト 2020 B]

https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_b 解説 https://atcoder.jp/contests/hhkb2020/submissions/17315225 布団を敷く可能性がある場所をすべて全探索することで答える。 横置きの場合 横置きする場合の布団を置く可能性がある場所は、横置…

Keyboard [HHKB プログラミングコンテスト 2020 A]

https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_a 解説 https://atcoder.jp/contests/hhkb2020/submissions/17314776 SがYであれば、Tに対して、大文字にする操作をするように実装する。 大文字にする操作は標準関数を使うか、場合分けして答えるのが…

Multiset Mean [AtCoder Regular Contest 104 D]

https://atcoder.jp/contests/arc104/tasks/arc104_d 解説 https://atcoder.jp/contests/arc104/submissions/17180396 何から始める? 簡潔な問題文だが、何から始めるべきだろうか。 平均の問題への取り組み方はいくつかあるが、平均を求めるには「個数」と…

Fair Elevator [AtCoder Regular Contest 104 C]

https://atcoder.jp/contests/arc104/tasks/arc104_c 解説 https://atcoder.jp/contests/arc104/submissions/17177990 条件の簡単化 まず、条件を少し簡単化していく。 エレベーターの階層を数直線上に考えて、ある人が乗り降りすることを区間として考えてみ…

DNA Sequence [AtCoder Regular Contest 104 B]

https://atcoder.jp/contests/arc104/tasks/arc104_b 解説 https://atcoder.jp/contests/arc104/submissions/17177217 まず、条件を簡単化できないかを考えてみる。 結論だけ書くと、T1とT2が相補的である条件の言い換えは「AとTが同数、かつ、CとGが同数」…

Plus Minus [AtCoder Regular Contest 104 A]

https://atcoder.jp/contests/arc104/tasks/arc104_a 解説 https://atcoder.jp/contests/arc104/submissions/17177438 A=X+Y B=X-Y なので、A+Bをすると2Xとなる。 よって、(A+B)/2をすると、Xが得られる。 YはA-Xを使って計算して、答える。 int A, B; //--…

Heights and Pairs [ACL Beginner Contest F]

https://atcoder.jp/contests/abl/tasks/abl_f 前提知識 包除原理 NTT 解説 https://atcoder.jp/contests/abl/submissions/17051729 この問題は複合的な知識が要求される。 順番に理解をしていこう。 包除原理? パッと見て包除原理感がある。 なんでやとい…

Replace Digits [ACL Beginner Contest E]

https://atcoder.jp/contests/abl/tasks/abl_e 前提知識 遅延評価セグメントツリー 解説 https://atcoder.jp/contests/abl/submissions/17051206 ACLコンテストというのもあり、遅延評価セグメントツリーが真っ先に思いついた。 遅延評価セグメントツリーで…

Flat Subsequence [ACL Beginner Contest D]

https://atcoder.jp/contests/abl/tasks/abl_d 前提知識 区間maxセグメントツリー 解説 https://atcoder.jp/contests/abl/submissions/17050957 たぶん似たような解法をやったことが無いと、思いつくのは難しいかもしれない。 以下のような問題設定は見たこ…

Connect Cities [ACL Beginner Contest C]

https://atcoder.jp/contests/abl/tasks/abl_c 前提知識 UnionFind, DSU 解説 https://atcoder.jp/contests/abl/submissions/17050582 この問題設定をパッと見てUnionFindが真っ先に思い浮かんだので、途中考察がしにくいのだが、 都市と道路を頂点と無向辺…

Integer Preference [ACL Beginner Contest B]

https://atcoder.jp/contests/abl/tasks/abl_b 解説 https://atcoder.jp/contests/abl/submissions/17050220 [A,B]と[C,D]の区間のANDを取ったときに、残る区間があるかという問題。 区間のANDを取りたい場面は結構あって、以下の手法が役に立つ。 [A,B]と[C…

Repeat ACL [ACL Beginner Contest A]

https://atcoder.jp/contests/abl/tasks/abl_a 解説 https://atcoder.jp/contests/abl/submissions/17050136 K回"ACL"を繰り返す。 ループで回してACLをくっつけてから答えとして返せばいい。 おすすめしないが、ループを使わなくてもif文でごり押してもいい…

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 実数の積をそのまま受け取って積が整数である問題であるが、 実数の形のまま計算して、積が整数であるかを判定するのは誤差的にだいぶ怖…