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

hamayanhamayan's blog

競技プログラミング

Lunlun Number [AtCoder Beginner Contest 161 D]

https://atcoder.jp/contests/abc161/tasks/abc161_d 解説 https://atcoder.jp/contests/abc161/submissions/11550250 サンプルを見ると105の場合が紹介されている。 あまり桁数が増えていないので、普通にインクリメント作業をしても間に合いそうだ。 x++の…

Yutori [AtCoder Beginner Contest 161 E]

https://atcoder.jp/contests/abc161/tasks/abc161_e 前提知識 DPの復元 解説 https://atcoder.jp/contests/abc161/submissions/11549308 ※ 本解説は、DPの復元が理解できてないとちょっと厳しいかもしれない 色々な方針が見える。 ある日で必ず働くというこ…

Division or Substraction [AtCoder Beginner Contest 161 F]

https://atcoder.jp/contests/abc161/tasks/abc161_f 前提知識 O(sqrt(N))による約数列挙 解説 https://atcoder.jp/contests/abc161/submissions/11544845 余談であるが、1012という制約はとても特徴的であり、平方根をとると106となって、まだやれる計算量…

Reiwa Sequence [yukicoder 1017]

https://yukicoder.me/problems/no/1017 解説 https://yukicoder.me/submissions/458766 今までの経験からして、これ系で行けそうというものはあるが、制約がちょっと厳しいのと、構築する必要がある。 なにも思いつかんけど、難易度がREDじゃないというとき…

三目並べ [yukicoder 1016]

https://yukicoder.me/problems/no/1016 解説 https://yukicoder.me/submissions/458599 貪欲法で解けそう。 まずは自明な所から考えてみる。 既にoooがあるなら勝っているし、どこか1マスにoを入れれば勝てるなら勝ち。 複数手で勝てる手を考える。 3手詰め…

おつりは要らないです [yukicoder 1015]

https://yukicoder.me/problems/no/1015 解説 https://yukicoder.me/submissions/458591 問題の見た目と★2なので、貪欲方針系だろうというのは分かる。 本番では別の貪欲をしてしまって通せなかった。 (ちゃんと落としてくるのが、さすが、maspyさん+beetさ…

Traveling Salesman around Lake [AtCoder Beginner Contest 160 C]

https://atcoder.jp/contests/abc160/tasks/abc160_c 解説 https://atcoder.jp/contests/abc160/submissions/11325671 ある家iから出発してすべての家を回る最短経路はi -> i+1 -> i+2 -> ... -> N -> 1 -> 2 -> ... -> i-1という感じになる。 つまり、1パタ…

RankingStudents [SRM 782 Div1 Med]

解法 簡単に書いておく。 貪欲法で解ける。 先頭から埋めていくことを考えると使える要素がどんどん少なくなっていく。 だが、末尾から埋めていくことを考えると使える要素がどんどん多くなっていく。 多くなる方がうまくいく場合が多いので、そっちでまず考…

EmptyTheBox [SRM 782 Div1 Easy]

前提知識 O(3N)のbitDP 解説 簡単にまとめておく。 サイコロで出せる合計の目の上限は2Dなので、Tが2Dを超えていたら、その部分は絶対余る。 なので、Tは2Dまでを考えればいい。 すると、bitDPができることに気が付く。 dp[msk] := 残っているペナルティトー…

Distributing Integers [AtCoder Beginner Contest 160 F]

https://atcoder.jp/contests/abc160/tasks/abc160_f 前提知識 全方位木DP 解説 https://atcoder.jp/contests/abc160/submissions/11325358 全方位木DPが分かっていないと解けない。 この問題で全方位木DPを学ぶには少し問題がややこしい。 入門問題としては…

Red and Green Apples [AtCoder Beginner Contest 160 E]

https://atcoder.jp/contests/abc160/tasks/abc160_e 解説 https://atcoder.jp/contests/abc160/submissions/11320313 今回の問題では、2種類の取り組み方をブレンドして解く。 C個の無色のリンゴの中で使う個数を「全探索」し、そのパターンで「貪欲」にリ…

Line++ [AtCoder Beginner Contest 160 D]

https://atcoder.jp/contests/abc160/tasks/abc160_d 解説 https://atcoder.jp/contests/abc160/submissions/11318810 今回の問題で最も重要なのは、制約に気が付くところにある。 Nは最大2000なので、O(N2)が通る。 計算量は107くらいを上限にしてとりあえ…

Banned K [AtCoder Beginner Contest 159 D]

https://atcoder.jp/contests/abc159/tasks/abc159_d 解説 https://atcoder.jp/contests/abc159/submissions/11139315 今回のようなクエリ問題に対する対処はあまりパターンがない。 各クエリについて高速に計算 全部前計算してしまう 差分を計算することで…

Knapsack for All Segments [AtCoder Beginner Contest 159 F]

https://atcoder.jp/contests/abc159/tasks/abc159_f 前提知識 動的計画法 解説 https://atcoder.jp/contests/abc159/submissions/11138847 DPを使ってまとめて数え上げることができる。 思いつく仮定としては、DPで解くんだろうと考え始めることと、N,S≦300…

Dividing Chocolate [AtCoder Beginner Contest 159 E]

https://atcoder.jp/contests/abc159/tasks/abc159_e 解説 https://atcoder.jp/contests/abc159/submissions/11137460 どう見てもHの制約の小ささが気になるので、2Hを中心に考えてみる。 チョコレートを横に切る操作は2H-1通りあるので、全探索できる。 横…

123 Triangle [AtCoder Grand Contest 043 B]

https://atcoder.jp/contests/agc043/tasks/agc043_b 解説 https://atcoder.jp/contests/agc043/submissions/11065208 まず、答えは0,1,2の3択になる。 このどれが答えになるかを求めていこう。 これは実験すると分かるし、操作を見てみるとそうなりそうなこ…

Range Flip Find Route [AtCoder Grand Contest 043 A]

https://atcoder.jp/contests/agc043/tasks/agc043_a 解説 https://atcoder.jp/contests/agc043/submissions/11063628 左上から右下へのとある経路を考える。 この経路で移動しようと考えたときの必要な最小操作回数は「白→黒」となった回数である。 (スタ…

Prefix-Suffix Palindrome (Hard version) [Codeforces Global Round 7 D2]

https://codeforces.com/contest/1326/problem/D2 前提知識 Manacher 解説 https://codeforces.com/contest/1326/submission/73898734 高速にクエリをさばいていこう。 文字列のprefixとsuffixで回文となる最大長を計算しておく。 この最大長以下であれば、…

Permutation Partitions [Codeforces Global Round 7 C]

https://codeforces.com/contest/1326/problem/C 解説 https://codeforces.com/contest/1326/submission/73896496 最善の答えは、最も大きいK個の総和であり、これはうまく分割することで達成できる。 そのような分割にするには、最も大きいK個の間に分割の…

Maximums [Codeforces Global Round 7 B]

https://codeforces.com/contest/1326/problem/B 解説 https://codeforces.com/contest/1326/submission/73896052 実は順番に構築していけばいい。 x[0]は0で固定。 b[i]=a[i]-x[i]なので、a[i]=b[i]+x[i]である。 なので、a[0]=b[0]+x[0]を使って、a[0]を計…

Bad Ugly Numbers [Codeforces Global Round 7 A]

https://codeforces.com/contest/1326/problem/A 解説 https://codeforces.com/contest/1326/submission/73895303 n=1のときは、その桁で必ず割り切れるので答えがない。 2以上のときは必ず答えが存在する。 自分は222222....222223を作って、全体が3で割り…

文字列集合 [Kyoto University Programming Contest 2020 Spring M]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/M 解説 根性構築。 N=1,2のときはサンプルにあるやつを答えればいい。 3≦Nのときは、00, 010, 0110, 01110, ...と構築していけばN-1個を達成できる。 なぜN-1が上限(最適解)であ…

トーナメント [Kyoto University Programming Contest 2020 Spring K]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/K 前提知識 ダブリングDP 解説 どこから手を付けるかと言うと、まずは1クエリでの計算である。 クエリ問題での方針は、「毎回高速に計算」「一気に前計算しておく」「差分だけ計算…

数列ゲーム [Kyoto University Programming Contest 2020 Spring E]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/E 前提知識 grundy数 解説 ゲーム問題は実験せよと古事記に書いてあるのでやる。 正確には勝ち負けだけ分かればいいので、grundy数が0になる規則性を探してくる。 ひたすら実験し…

Xor Array [Kyoto University Programming Contest 2020 Spring D]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/D 前提知識 累積和による動的計画法高速化 前提知識 DPの作り方で運命が変わる。 dp[i][xo][lst] := 数列のi個目まで確定していて、総XORがxoで、最後の要素がlstであるときの組み…

サイコロを転がさないで [Kyoto University Programming Contest 2020 Spring B]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/B 解説 到達可能性といえばBFS。BFSだろうなぁと思って考えていくと解ける。 状態は(x座標, y座標, サイコロの下の面の数字, サイコロの右の面の数字)で表現する。 遷移は4方向な…

チーム分け [Kyoto University Programming Contest 2020 Spring A]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/A 解説 チームの組み合わせはC(4,2)/2通りしかないので、全通り試して実力差が最も小さいものを答えよう。 実装では、1234の順列を全列挙して、前半2人と後半2任でグループを作る…

Many Quotients hard [灘校75回生中学卒業記念コンテスト]

https://www.hackerrank.com/contests/75th/challenges/many-quotients 解説 https://www.hackerrank.com/contests/75th/challenges/many-quotients/submissions/code/1321983454 死ぬほどバグった。 分母を1からNまで増やして商を見てみると、途中から5,4,3…

I want to be a high achiever [灘校75回生中学卒業記念コンテスト]

https://www.hackerrank.com/contests/75th/challenges/i-want-to-be-a-high-achiever 前提知識 動的計画法 解説 重要なテクがあり、これが適用できれば、ACにだいぶ近づく。 「A[i]の平均がX以上 <=> A[i]-Xの総和が0以上」 平均を実際に求めようと思うと、…

Sashiming String [灘校75回生中学卒業記念コンテスト]

https://www.hackerrank.com/contests/75th/challenges/sashiming-string 解説 https://www.hackerrank.com/contests/75th/challenges/sashiming-string/submissions/code/1321979741 まず、何かしらの全探索対象を探す。 特徴的なのは、Sとingの位置なので…