https://atcoder.jp/contests/abc142/tasks/abc142_d 前提知識 最大公約数計算、素因数分解 解説 https://atcoder.jp/contests/abc142/submissions/7771060 AもBの公約数を列挙する。 といっても、公約数は最大公約数の約数となるので、とりあえず、最大公約…

https://atcoder.jp/contests/abc142/tasks/abc142_f BFS 解説 https://atcoder.jp/contests/abc142/submissions/7770966 まず、どこから手を付けようかという感じであるが、NもMも制約がゆるい。 うーん。 作りたいグラフはサイクルである。 サイクルだけの…

https://atcoder.jp/contests/abc142/tasks/abc142_b 解説 https://atcoder.jp/contests/abc142/submissions/7771123 全探索。 仲間全てに対してK以上かをチェックして、条件を満たす人数を数える。 int N, K, H[101010]; //-------------------------------…

https://atcoder.jp/contests/abc142/tasks/abc142_c 解説 https://atcoder.jp/contests/abc142/submissions/7771093 最初に来た生徒では1人の記録があるはず。 二番目に来た生徒では2人の記録があるはず。 という感じで、記録された人数と来た順番は一致す…

https://atcoder.jp/contests/abc142/tasks/abc142_e 前提知識 bitDP 解説 https://atcoder.jp/contests/abc142/submissions/7771023 Nの制約がかなり小さい。 212は4000くらい。 Mも1000であり、4000×1000は間に合う量である。 bitDPをしよう。 dp[i][msk] …

https://atcoder.jp/contests/abc142/tasks/abc142_a 解説 https://atcoder.jp/contests/abc142/submissions/7771154 奇数の個数cntはN/2の切り上げになる。 cnt/Nをdouble型で計算して、答えると答え。 小数提出に慣れていないと、少し戸惑うかもしれない。…

https://products.sint.co.jp/hubfs/resource/topsic/pgb/3-4.pdf 前提知識 累積和によるDP更新最適化 解説 入力例で正しいことしか確認できていません！落ちる可能性ありますので、ご注意ください （本番では、O(N2 logN)で出しちゃって落ちた） 公式解説 …

https://products.sint.co.jp/hubfs/resource/topsic/pgb/3-2.pdf 解説 公式解説 シミュレートしていくのだが、効率よくしていかないと間に合わない。 効率的にシミュレートする方法として、2フェーズに分けるという方法がある。 座る方法としてフェーズ1「…

https://products.sint.co.jp/hubfs/resource/topsic/pgb/3-3.pdf 前提知識 マンハッタン距離は45度回転 二次元累積和 解説 公式解説 「マンハッタン距離は45度回転」という知識が無いと永久に解けない。 知らなかった場合は運が悪かったと思おう。 ある頂点…

https://products.sint.co.jp/hubfs/resource/topsic/pgb/3-1.pdf 解説 入力例で正しいことしか確認できていません！落ちる可能性ありますので、ご注意ください （本番では、Aの配列サイズをNにしていて落ちた） 公式解説 とりあえず、入力の配列の順番に特…

https://products.sint.co.jp/hubfs/resource/topsic/pgb/2-1.pdf 解説 入力例で正しいことしか確認できていません！落ちる可能性ありますので、ご注意ください 公式解説 シミュレーションをする。 アライグマは最低限汚さをKにするまで洗濯すればいい。 そ…

https://products.sint.co.jp/hubfs/resource/topsic/pgb/2-3.pdf 前提知識 BFS 解説 入力例で正しいことしか確認できていません！落ちる可能性ありますので、ご注意ください 公式解説 選手を頂点、パスを辺とすると無向グラフとみなすことができる。 問われ…

https://products.sint.co.jp/hubfs/resource/topsic/pgb/2-2.pdf 解説 入力例で正しいことしか確認できていません！落ちる可能性ありますので、ご注意ください 公式解説 まずO(N2)の解法はすぐに思いつく。 生物aがx匹、生物bがy匹、生物cがz匹とすると、x…

https://products.sint.co.jp/hubfs/resource/topsic/pgb/2-4.pdf 前提知識 平面走査 座標圧縮 区間minセグメントツリー 解説 入力例で正しいことしか確認できていません！落ちる可能性ありますので、ご注意ください 公式解説 ライブラリ力があれば、セグメ…

https://products.sint.co.jp/hubfs/resource/topsic/pgb/1-4.pdf 前提知識 ダイクストラ 解説 入力例で正しいことしか確認できていません！落ちる可能性ありますので、ご注意ください 公式解説 rep(i,a,b)はfor (int i=a; i < b; i++)です。 都市と道路の関…

https://products.sint.co.jp/hubfs/resource/topsic/pgb/1-3.pdf 解説 入力例で正しいことしか確認できていません！落ちる可能性ありますので、ご注意ください 公式解説 rep(i,a,b)はfor (int i=a; i < b; i++)です。 ピンがM本立っているが、隙間なく並ん…

https://products.sint.co.jp/hubfs/resource/topsic/pgb/1-2.pdf 解説 入力例で正しいことしか確認できていません！落ちる可能性ありますので、ご注意ください 公式解説 rep(i,a,b)はfor (int i=a; i < b; i++)です。 SがAtCoderと等しい場合は、C++であれ…

https://products.sint.co.jp/hubfs/resource/topsic/pgb/1-1.pdf 解説 入力例で正しいことしか確認できていません！落ちる可能性ありますので、ご注意ください 公式解説 向こう岸までジャンプできる条件は「こちら側から中洲へジャンプできる」かつ「中洲か…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0410 解説 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0410/judge/3897232/C++14 全探索で考えてみるが、日付を全探索するのは難しそう。 p1, p2, ..., …

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0409 解説 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0409/judge/3897204/C++14 シミュレーションをする。 つまり、タイルを敷き詰めをしていく訳だが…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0407 解説 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0407/judge/3897181/C++14 問題へのアプローチに迷ったときは、まずは全探索を考えると良いだろう…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0408 前提知識 スタック 解説 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0408/judge/3897197/C++14 問題文で定義されている横穴は、プログラミングの世…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0405 解説 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0405/judge/3897173/C++14 アルファベットかどうかの判定には、便利な方法がある。 'A' <= x and …

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0406 解説 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0406/judge/3897175/C++14 2の累乗を順番に見ていって、N以下で最大の数を答える。 whileを使いな…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0404 解説 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0404/judge/3897167/C++14 プログラミングの基礎を問う問題。 柴犬の総数は、数えた数の総数なの…

https://yukicoder.me/problems/no/894 解説 https://yukicoder.me/submissions/384924 出発回数を計算するが、包除原理を用いる。 (バス1が出発 または バス2が出発) = (バス1が出発) + (バス2が出発) - (バス1が出発 かつ バス2が出発) これをそれぞれ計算…

https://yukicoder.me/problems/no/895 解説 https://yukicoder.me/submissions/384932 最後の条件がなかなか見慣れないので、考えてみよう。 これは、全てのビットかかぶらず、かつ、下位a+b+cビットに全部集まっていることを示している。 なので、a+b+c個…

https://yukicoder.me/problems/no/892 解説 https://yukicoder.me/submissions/384922 2等分にするためには全体を足したときに偶数であればいい。 なので、ABそれぞれあるが、それぞれが偶数であるか奇数であるかのみ興味がある。 Aが奇数ならば、それをど…

https://yukicoder.me/problems/no/893 解説 https://yukicoder.me/submissions/384923 シミュレーションする。 Pの上限が102なので、最高でも100周はする。 レジが103個あるので、1周に103回確認するとしても、 全体の確認回数は105回なので間に合う。 先頭…

https://www.hackerrank.com/contests/kodamanwithothers/challenges/powerful-sum 解説 https://www.hackerrank.com/contests/kodamanwithothers/challenges/powerful-sum/submissions/code/1316487336 Nがとても大きいので、普通に計算するんじゃないんだ…