https://atcoder.jp/contests/abc153/tasks/abc153_f 前提知識 尺取り法 imos法 解説 https://atcoder.jp/contests/abc153/submissions/9784254 何から手を付ければいいかわからないかもしれない。 全探索対象も無いし、最小値を求めよとか言われるし、 こう…

https://atcoder.jp/contests/abc153/tasks/abc153_e 前提知識 動的計画法 解説 https://atcoder.jp/contests/abc153/submissions/9783902 制約と最小化でDPかなという感じがする。 雑な初手であるが、DPをむちゃくちゃやったらこういう思考になる。 103とい…

https://atcoder.jp/contests/abc153/tasks/abc153_d 解説 https://atcoder.jp/contests/abc153/submissions/9783601 操作について考えてみる。 モンスターの体力が1なら、体力は0になる。 これは分岐もしないので、そうなる。 モンスターの体力がXなら、X/2…

https://atcoder.jp/contests/abc153/tasks/abc153_c 解説 https://atcoder.jp/contests/abc153/submissions/9783372 int N, K, H[201010]; //--------------------------------------------------------------------------------------------------- void _…

https://atcoder.jp/contests/abc153/tasks/abc153_b 解説 https://atcoder.jp/contests/abc153/submissions/9783343 同じ必殺技を2度以上使うことなく勝てるかという問題を言い換えて考える。 必殺技をそれぞれ1回使うことで勝てるかを考える。 つまり、放…

https://atcoder.jp/contests/abc153/tasks/abc153_a 解説 https://atcoder.jp/contests/abc153/submissions/9783316 制約を見ると、どんな感じに解いても問題なさそう。 シミュレートしてもいいし、自分の解法のように数学的に解いてもいい。 答えはHをAで…

https://atcoder.jp/contests/abc152/tasks/abc152_f 前提知識 包除原理 解説 https://atcoder.jp/contests/abc152/submissions/9706801 条件の弱い所を探すと、N=50, M=20である。 N=50はまあまあ見るのでいいとして、M=20がどう見ても不自然。 ここから考…

https://atcoder.jp/contests/abc152/tasks/abc152_e 前提知識 LCM 解説 https://atcoder.jp/contests/abc152/submissions/9706493 条件を簡単にしよう。 条件をよくみると、A[i]B[i]=A[j]B[j]が全組み合わせある感じである。 ということは、全てのA[i]B[i]…

https://atcoder.jp/contests/abc152/tasks/abc152_d 解説 https://atcoder.jp/contests/abc152/submissions/9706396 まず、全列挙を考えると難しそう。 片方のAを固定すると、もう片方のBの先頭数と末尾数は決定する。 これで2桁減るので、全体108通りくら…

https://atcoder.jp/contests/abc152/tasks/abc152_c 解説 https://atcoder.jp/contests/abc152/submissions/9706322 指定されている条件が難しく書かれている。 これを整理すると自ずと解法が出てくる。 ある条件を満たすiの条件は、A[0]～A[i]の最小値がA[…

https://atcoder.jp/contests/abc152/tasks/abc152_b 解説 https://atcoder.jp/contests/abc152/submissions/9706301 2種類の文字列は構築可能なので、構築しよう。 C++だとstringの比較演算は辞書順比較なので、普通に比較をしてやって小さい方を答える。 i…

https://atcoder.jp/contests/abc152/tasks/abc152_a 解説 https://atcoder.jp/contests/abc152/submissions/9706297 ACしている時は全問通っているときなので、N=MであればYes そうでないならNoとなる int N, M; //---------------------------------------…

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

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

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

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

LOGGING BEST PRACTICES: THE 13 YOU SHOULD KNOW https://www.scalyr.com/blog/the-10-commandments-of-logging/ ロギングに関するプラクティス集 原文はCC BY 4.0であるので、本記事もそれを継承しておく（CCってライセンスの継承義務ってあるんかな？） …

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

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

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

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

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

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

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

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

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

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

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

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

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