https://beta.atcoder.jp/contests/tenka1-2018/tasks/tenka1_2018_c 解説 https://beta.atcoder.jp/contests/tenka1-2018/submissions/3509652構築問題。 最適な構築を考えてみる。 今回は400点問題なので、なるべく簡単に構築できるように考える。 絶対値…

https://beta.atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_b 解説 https://beta.atcoder.jp/contests/tenka1-2018-beginner/submissions/3509545シミュレートしよう。 int A, B, K; //---------------------------------------------------…

https://beta.atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_a 解説 https://beta.atcoder.jp/contests/tenka1-2018-beginner/submissions/3509515 S =3のときの最初と最後をスワップ処理を書いて、Sを出力しよう。 C++であればswap関数を使…

https://beta.atcoder.jp/contests/qupc2018/tasks/qupc2018_c 前提知識 BFS 解説 https://beta.atcoder.jp/contests/qupc2018/submissions/3436552二回bfsをして答える。 関数bfs1 イノシシがX回の移動で移動できるマスにngフラグを立てる。 よくある手法な…

https://beta.atcoder.jp/contests/qupc2018/tasks/qupc2018_b 解説 https://beta.atcoder.jp/contests/qupc2018/submissions/3436323まず総額が奇数ならば、同数に分割はできない。 片方が総数/2を実現できるかを判定する。 ピッタリに払う最適戦略として、…

https://beta.atcoder.jp/contests/qupc2018/tasks/qupc2018_a 解説 https://beta.atcoder.jp/contests/qupc2018/submissions/34361161回後になると+4年されるので、2014+4(N-1)でいい。 int N; //--------------------------------------------------------…

https://yukicoder.me/problems/no/748 前提知識 最小全域木 解説 https://yukicoder.me/submissions/293889最小全域木を構築するように計算していく。 プリム法がわかっていれば、それをやるだけ。 違いは、最初にK本の道路を使って、両端を連結させておく…

https://yukicoder.me/problems/no/747 解説 https://yukicoder.me/submissions/293314Easyと方針は同じ。 (N^K)%6が求まれば答えが求まる。 (N^K)%6=((N%6)^K)%6 となるので、とりあえずNは%6とした値としておく。 上の桁から1桁ずつ%6しながら足し合わせる…

https://yukicoder.me/problems/no/746 解説 https://yukicoder.me/submissions/293320サンプルのN=100をみると、真面目に計算する感じではない。 サンプルを見るに循環小数っぽくなってる。 循環小数を答えればいいのでは？ "142857"をN個分から答えていく…

https://yukicoder.me/problems/no/745 解説 https://yukicoder.me/submissions/293887クリアできない場合を先に処理しよう。 D=10ならばクリアできないので"Impossible" 最適戦略を考えると、倍率が高い状態でperfectを出したいので、 最初になるべくgreat…

https://yukicoder.me/problems/no/744 解説 https://yukicoder.me/submissions/293316 N 数 1 2 2 8 3 5 4 7 5 1 6 4 7 2 8 8 9 5 10 7 6で周期性があるので、N%6にしてみる N%6 数 1 2 2 8 3 5 4 7 5 1 0 4 1 2 2 8 3 5 4 7 となるので、N%6で答える。 "42…

http://codeforces.com/contest/1066/problem/DN個の物体があり、重さはA[i]である。 重さK分入る箱がM個ある。 物体を左から順に箱詰めするが、以下のルールで箱詰めする。 箱詰め前に左から任意の個数捨てる 捨てた後、順番に箱に入れていく 入れれるだけ…

http://codeforces.com/contest/1066/problem/C以下のクエリを処理せよ。 L id := キューの左端にidを追加する R id := キューの右端にidを追加する ? id := キューの中のidのmin(左から何番目, 右から何番目)を出力する 解法 http://codeforces.com/contest…

https://yukicoder.me/problems/no/602 解法 https://yukicoder.me/submissions/291604解くときに使った、もう少し強いサンプルを先に載せておきます。 4 3 5 4 13 8 0 1 5 -2 -3 1 14 51 4 1 7 7 7 1 9 0 4 1 3 0 5 1 3 0 4 答え 2 1 -1 2 2 -1 2 0回で移動…

http://codeforces.com/contest/1066/problem/BN個のヒーターがあり、位置posにあるヒーターは[pos-R+1, pos+R-1]を温めることができる。 N個のヒーターのうち、一部しか電源がついていない。 ここからいくつかのヒーターを消して、全ての位置が暖められるよ…

http://codeforces.com/contest/1066/problem/A[1,L]の数直線上のvの倍数にランタンがある。 [l,r]以外の部分にあるランタンの個数は？ 解法 http://codeforces.com/contest/1066/submission/44190486「countMultiple(l,r,v) := [l,r]の数の中でvの倍数であ…

http://codeforces.com/contest/1033/problem/DN要素の配列Aがある。 各要素は必ず約数が3～5個になっている。 配列の要素の総積を取ったとき、これの約数の個数は何個か。 解法 http://codeforces.com/contest/1033/submission/43979011約数の制約を言い換…

https://beta.atcoder.jp/contests/abc112/tasks/abc112_d 解法 https://beta.atcoder.jp/contests/abc112/submissions/3348509全ての要素の公約数としてgがある場合を考える。 全ての要素がgの倍数になれば、公約数がgになる。 まず、満たすべき条件としてM…

https://beta.atcoder.jp/contests/abc112/tasks/abc112_c 解法 https://beta.atcoder.jp/contests/abc112/submissions/3347708ピラミッドの中心座標を全探索しよう。 高度を見ると、「H-中心とのマンハッタン距離」になっているので、 逆に中心は「h[i]+中…

https://beta.atcoder.jp/contests/abc112/tasks/abc112_b 解法 https://beta.atcoder.jp/contests/abc112/submissions/3348993t[i]≦Tを満たす中のc[i]の最小値が答え。 もし満たすものがなければ、TLEと答える。 int N, T, c[101], t[101]; //-------------…

https://beta.atcoder.jp/contests/abc112/tasks/abc112_a 解法 https://beta.atcoder.jp/contests/abc112/submissions/3345807Nの値で場合分けをする。 N=2の場合は場合分け先で読み込もう。 int N, A, B; //---------------------------------------------…

https://yukicoder.me/problems/no/743 解法 https://yukicoder.me/submissions/289965A[i]＜B[i]となるように整形しておく。 すると、線分iと線分jが交わる条件は A[j]＜A[i]かつA[i]＜B[j]＜B[i] または A[i]＜A[j]＜B[i]かつB[i]＜B[j] である。 そのため…

https://yukicoder.me/problems/no/742 解法 https://yukicoder.me/submissions/289941ある猫についてiからM[i]へ移動するときにすれ違う猫の条件は [0,i)にいる猫で到着先が[M[i], N) または [i+1,N)にいる猫で到着先が[0,M[i]] である。 そのため、長方形…

https://yukicoder.me/problems/no/741 前提知識 桁DP 解法 https://yukicoder.me/submissions/289853この問題はN桁以下の数でAscNumberである数の個数を求めている。 桁DPをする。 DP[dgt][lst] := dgt桁まで確定していて最下位の桁の数がlstである組み合わ…

https://yukicoder.me/problems/no/740 解法 https://yukicoder.me/submissions/289816シミュレートしよう。 注意点は特に無いが、自分の実装例は以下の通りである。 whileを使った実装をおすすめする。 int N, M, P, Q; //--------------------------------…

https://yukicoder.me/problems/no/739 解法 https://yukicoder.me/submissions/2897912回読み上げられるためにはNが偶数である必要がある。 奇数ならNOとしよう。 後は、0番目とN/2番目、1番目とN/2+1番目、…が全て等しいか判定しよう。 string S; //------…

https://beta.atcoder.jp/contests/kupc2018/tasks/kupc2018_b 考察過程 1. 答えは最高10桁でそれぞれ3パターンあるので、組み合わせ数は3^10 2. これは普通に全探索できる 解法 https://beta.atcoder.jp/contests/kupc2018/submissions/3313684答えを全探索…

https://beta.atcoder.jp/contests/kupc2018/tasks/kupc2018_a 解法 https://beta.atcoder.jp/contests/kupc2018/submissions/3313658実装問題。 int N, S[101], A[101]; //------------------------------------------------------------------------------…

条件を満たす3頂点を答えよ x,y座標が[0,3000]に収まる できる三角形の外周がperimeterであり、面積がarea 解法 どのような三角形も回転や平行移動をすれば、(0,0)を通るようにできる。 なので、1つの頂点は(0,0)で他の2頂点を考えよう。 他の2頂点は外周が…

前は傾向と対策とか書いていたけど、だいぶ無責任な記事になっている（しかも古かった）ことに気が付いたので、ただの解説まとめにした。 過去問｜パソコン甲子園2020 AOJ-PCK(パソコン甲子園過去問) 2020年 # 点数 題名 要求（白塗りしてあるので選択で見て…