2018-01-01から1年間の記事一覧
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年 # 点数 題名 要求(白塗りしてあるので選択で見て…
https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0388 考察過程 1. 制約を見るとN^2はいけるので、2点を結ぶ全ての直線は列挙できる 2. ここからK個以上の同じ点が同じ直線上に存在することを判定できないか考える 3. 同じ直線状にあるなら…
https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0387 考察過程 1. タクシーはタクシー乗り場を後ろにしか移動できないので、後ろのタクシーから客を確定させていく 2. どの客を乗せればいいかだけを決めれば、どのタクシーがどの客を乗せ…
https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0386 考察過程 1. mod10^9+7なのでDP数え上げ感がある 2. dpをまず考えるが、制約を見ると「dp[i] := 星iにたどり着く組み合わせ数」っぽい 3. 更新はそれより前の星の今いる出口と同じ文字…
https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0385 考察過程 1. 愚直にシミュレートして行けば良さそう 2. そのためには昇順になったかを高速に判定する必要がある 3. Aを昇順にしたものと同じ場所になった個数を数えればいい? 4. 同じ…
https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0384 考察過程 1. 点数に比べて問題設定が難しい 2. とりあえず全探索対象を探そう 3. y+aを全探索すれば、10^4が最大なので、全探索できるっぽい 解法 https://onlinejudge.u-aizu.ac.jp/s…
https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0383 考察過程 1. まだ難しくなる段階じゃない 2. 何か全探索する対象を探す 3. 1リットルを買う個数を全探索し、足りない分を500ミリリットル買うことにする 解法 https://onlinejudge.u-a…
https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0382 解法 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0382/judge/3162071/C++14持ってきたケーキを1つにまとめて、再分配することを考える。 自分を入…
https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0381 解法 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0381/judge/3162047/C++142つの数の差を取ればいい。 条件分岐を使っても良いし、abs関数で絶対値…
https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0380 解法 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0380/judge/3162045/C++14計算式通りにCを計算する。 実装問題。 int F; //---------------------…
https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0303?year=2014 前提知識 区間DP 解法 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0303/judge/3162012/C++14二段階でDPして解く。 まず、区間DPをする。…