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

hamayanhamayan's blog

競技プログラミング

Swap and Flip [Keyence Programming Contest 2020 D]

https://atcoder.jp/contests/keyence2020/tasks/keyence2020_d 前提知識 BitDP 解説 https://atcoder.jp/contests/keyence2020/submissions/9583217 とある性質がある。 「位置が1だけずれると同時に裏返されるため、位置と色のパリティ(2で割った余り)は…

Subarray Sum [Keyence Programming Contest 2020 C]

https://atcoder.jp/contests/keyence2020/tasks/keyence2020_c 解説 https://atcoder.jp/contests/keyence2020/submissions/9582827 問題にかなりの弱点がある。 0≦K≦Nの部分である。 よって、大体はSをK個並べて、残りをINFにすればいい。 INFは最大が109…

Robot Arms [Keyence Programming Contest 2020 B]

https://atcoder.jp/contests/keyence2020/tasks/keyence2020_b 前提知識 動的計画法 解説 https://atcoder.jp/contests/keyence2020/submissions/9582655 DPをしよう。 200点でなので想定解は貪欲なんだろうという気もするが、DPでさくっとかけるので書いて…

Painting [Keyence Programming Contest 2020 A]

https://atcoder.jp/contests/keyence2020/tasks/keyence2020_a 解説 https://atcoder.jp/contests/keyence2020/submissions/9581432 なるべく最小回数でマスを塗っていきたいが、縦横塗れるのが大きい方でずっと塗ればいい。 これが上界であることは自明な…

選び方のスコア [yukicoder 972]

https://yukicoder.me/problems/no/972 解説 https://yukicoder.me/submissions/419463 難しい問題でした。 まず、kは奇数個のみ考えればいい。 kが偶数個の場合は中央値の計算に使われる2つのうち、大きい方を削除してもSの値が変わらないためである。 これ…

いたずらっ子 [yukicoder 971]

https://yukicoder.me/problems/no/971 解説 https://yukicoder.me/submissions/418655 まず、重要な性質に気づく必要がある。 「いたずらっ子によって最初の場所に戻されたとしても、始点から終点まで通るパスは、毎回同じである。」 戻されたときに違うル…

数列変換マシン [yukicoder 970]

https://yukicoder.me/problems/no/970 解説 https://yukicoder.me/submissions/418567 平均は分数の形になっていて少し扱いにくいので、b[i]をN-1倍して考える。 すると、b[i]はa[i]以外の総和になるので、この時点で全部の総和が分かれば答えられそうだな…

じゃんけん [yukicoder 969]

https://yukicoder.me/problems/no/969 解説 https://yukicoder.me/submissions/418493 あいこになるパターンは3パターンしかない。 どちらの手も同じになるパターンである。 どちらもグーなら和は0 どちらもチョキなら和は4 どちらもパーなら和は10 よって…

引き算をして門松列(その3) [yukicoder 968]

https://yukicoder.me/problems/no/968 解説 https://yukicoder.me/submissions/417572 この問題は、前の問題の下位互換ではない。 難易度が上がっている。 どこから考察を始めようかという感じであるが、何か使えそうな性質を探そう。 3種類の操作を1回ずつ…

引き算をして門松列(その2) [yukicoder 967]

https://yukicoder.me/problems/no/967 解説 https://yukicoder.me/submissions/417569 1つ前の下位互換の問題での方針ガチャによっては、ちょっと拡張するだけでこの問題が解ける。 (というか、この問題が解ければ、下位互換も同様に解ける) min,mid,max…

引き算をして門松列(その1) [yukicoder 966]

https://yukicoder.me/problems/no/966 解説 https://yukicoder.me/submissions/417566 3種類の操作があるが、3種類の操作を1つずつ行う操作では、全体の大小関係が変化しないので意味がない。 よって、操作を行う整数の対象は2つ以下である。 max,mid,minを…

門松列が嫌い [yukicoder 965]

https://yukicoder.me/problems/no/965 解説 https://yukicoder.me/submissions/417550 門松列は、A>B<Cであるか、A>B</cであるか、a>

2020 [yukicoder 964]

https://yukicoder.me/problems/no/964 解説 https://yukicoder.me/submissions/417549 構築問題では、いかにシンプルなルールで構築を行うかが重要になる。 今回でいうと、N種類の数をN個ずつ使うが、使う数は9から降順に使っていくと楽である。 降順に使っ…

Enclose All [AtCoder Beginner Contest 151 F]

https://atcoder.jp/contests/abc151/tasks/abc151_f 前提知識 幾何 解説 https://atcoder.jp/contests/abc151/submissions/9483086 「最小包含円」という有名問題がある。 これと同義の問題であるが、これのよく知られている解法はガチ解法なので、もっと分…

Max-Min Sums [AtCoder Beginner Contest 151 E]

https://atcoder.jp/contests/abc151/tasks/abc151_e 解説 https://atcoder.jp/contests/abc151/submissions/9477762 考察に行き詰まったときは、何か全探索できそうな対象を探す。 選び方の全探索は難しそうなので、他に問題文にあることで全探索できるもの…

Maze Master [AtCoder Beginner Contest 151 D]

https://atcoder.jp/contests/abc151/tasks/abc151_d 前提知識 BFSによる最短経路 解説 https://atcoder.jp/contests/abc151/submissions/9458353 制約を見るとかなり小さい。 なので、なるべく全探索できるものは、全探索していこう。 任意の二点間の最短距…

Welcome to AtCoder [AtCoder Beginner Contest 151 C]

https://atcoder.jp/contests/abc151/tasks/abc151_c 解説 https://atcoder.jp/contests/abc151/submissions/9452214 シミュレーション問題となる。 各問題についてACしているかどうかを保持する配列solvedとWA数を保持する配列waを定義しておいて、 時系列…

Achieve the Goal [AtCoder Beginner Contest 151 B]

https://atcoder.jp/contests/abc151/tasks/abc151_b 解説 https://atcoder.jp/contests/abc151/submissions/9448365 計算することで最適な点数を求めることもできそうだが、 今回は点数は最大100点満点なので、全探索で求めていこう。 最後の点数を全探索し…

Next Alphabet [AtCoder Beginner Contest 151 A]

https://atcoder.jp/contests/abc151/tasks/abc151_a 解説 https://atcoder.jp/contests/abc151/submissions/9444934 次の文字を表示すればいい。 C++であれば、文字を数字として扱うことで+1できるようになる。 あとは、それを文字に戻して答えると答え。 c…

Arrangement [Dwango Programming Contest 6th D]

https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_d 解説 https://atcoder.jp/contests/dwacon6th-prelims/submissions/9429060 条件を見てみると、Nが増えていくと大体作れそうな感じがする。 で、適当にdfsで全探索するとダメ。 ち…

Fusing Slimes [Dwango Programming Contest 6th B]

https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_b 解説 https://atcoder.jp/contests/dwacon6th-prelims/submissions/9426829 なんだか昨日も似た方針の問題を解いた気がするが、解くのに時間かかってしまった。 昨日の問題の解説…

Falling Asleep [Dwango Programming Contest 6th A]

https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_a 解説 https://atcoder.jp/contests/dwacon6th-prelims/submissions/9426401 名前がXの曲が出てきたら、時間計測を始めるように実装する。 自分の実装では、ansに-1を入れておき、…

Xor Shift [AtCoder Beginner Contest 150 F]

https://atcoder.jp/contests/abc150/tasks/abc150_f 解説 https://atcoder.jp/contests/abc150/submissions/9414606 自明な所から考えると、kを固定すると、a[i] = b[i+k] XOR xということは、 a[i] XOR b[i+k] = xなので、xは一意に定まる。 なので、kを固…

Change a Little Bit [AtCoder Beginner Contest 150 E]

https://atcoder.jp/contests/abc150/tasks/abc150_e 解説 https://atcoder.jp/contests/abc150/submissions/9413448 多分、何から考えていいかわからない人が多いだろう。 何か限定的に考えていける部分がないか見てみると、とりあえずf(S,T)を求めるにはど…

Semi Common Multiple [AtCoder Beginner Contest 150 D]

https://atcoder.jp/contests/abc150/tasks/abc150_d 解説 https://atcoder.jp/contests/abc150/submissions/9412419 式中に小数が出てくるのは面倒なので、小数が出てこないような形にしよう。 A[k]は偶数なので、A[k] = 2 * B[k]とおくと、 X = A[k] * (p …

Count Order [AtCoder Beginner Contest 150 C]

https://atcoder.jp/contests/abc150/tasks/abc150_c 解説 https://atcoder.jp/contests/abc150/submissions/9407367 パット見て難しい問題に見えるかもしれない。 この問題は制約から解法を考えていく問題である。 問題の解法を考えるときに、全探索できる…

Count ABC [AtCoder Beginner Contest 150 B]

https://atcoder.jp/contests/abc150/tasks/abc150_b 解説 https://atcoder.jp/contests/abc150/submissions/9406760 連続する3文字を抜き取る組み合わせは、N-2通りあり、 これは全列挙できるため、全列挙してABCが何個あるか数えよう。 int N; string S; /…

500 Yen Coins [AtCoder Beginner Contest 150 A]

https://atcoder.jp/contests/abc150/tasks/abc150_a 解説 https://atcoder.jp/contests/abc150/submissions/9405277 持っている金額の総額は500K円なので、これがX円以上あるか判定すればいい。 int K, X; //---------------------------------------------…

Numbers on Tree [Codeforces Round #612 (Div. 1) B]

https://codeforces.com/contest/1286/problem/B 解説 https://codeforces.com/contest/1286/submission/68319846 手がつかない問題は何かを仮定して考えていくしか無い。 まず、構築可能そうな場合は構築可能であるという仮定である。 子の個数

Garland [Codeforces Round #612 (Div. 1) A]

https://codeforces.com/contest/1286/problem/A 解説 https://codeforces.com/contest/1286/submission/68315998 0に数を入れていくが、2で割った余りだけが関係あるので、0に入れるべき数で 偶数の個数をresteven, 奇数の個数をrestoddとして数えておこう…