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

Boxes Packing [Codeforces Round #515 (Div. 3) D]

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

Books Queries [Codeforces Round #515 (Div. 3) C]

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回で移動…

隠されていたゲーム2 [yukicoder No.602]

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

Heaters [Codeforces Round #515 (Div. 3) B]

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の倍数であ…

Vova and Train [Codeforces Round #515 (Div. 3) A]

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

Divisors [Lyft Level 5 Challenge 2018 - Elimination Round D]

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

Partition [AtCoder Beginner Contest 112 D]

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

Pyramid [AtCoder Beginner Contest 112 C]

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]; //-------------…

Time Limit Exceeded [AtCoder Beginner Contest 112 B]

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

Programming Education [AtCoder Beginner Contest 112 A]

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] である。 そのため…

Segments on a Polygon [yukicoder No.743]

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]] である。 そのため、長方形…

にゃんにゃんにゃん　猫の挨拶 [yukicoder No.742]

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

AscNumber(Easy) [yukicoder No.741]

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

幻の木 [yukicoder No.740]

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

大事なことなので２度言います [yukicoder No.739]

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

弾幕ゲーム [Kyoto University Programming Contest 2018 B]

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

立て看板 [Kyoto University Programming Contest 2018 A]

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

FindThePerfectTriangle [TopCoder SRM 738 Div1 Easy]

パソコン甲子園は地域枠というのがあるので、地方ならばかなり有利です！！ あと、自分自身パソコン甲子園出たこと無いし、運営という訳でもないので、参考程度にご覧ください。 はじめに 目標 都市にお住まいの方→6割くらい必要（8,9問解く）で10位以内に入…

パソコン甲子園 プログラミング部門 予選の傾向と対策

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0388 考察過程 1. 制約を見るとN^2はいけるので、2点を結ぶ全ての直線は列挙できる 2. ここからK個以上の同じ点が同じ直線上に存在することを判定できないか考える 3. 同じ直線状にあるなら…

直線状の点 [パソコン甲子園2018 予選 I]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0387 考察過程 1. タクシーはタクシー乗り場を後ろにしか移動できないので、後ろのタクシーから客を確定させていく 2. どの客を乗せればいいかだけを決めれば、どのタクシーがどの客を乗せ…

タクシー [パソコン甲子園2018 予選 H]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0386 考察過程 1. mod10^9+7なのでDP数え上げ感がある 2. dpをまず考えるが、制約を見ると「dp[i] := 星iにたどり着く組み合わせ数」っぽい 3. 更新はそれより前の星の今いる出口と同じ文字…

ワープ装置 [パソコン甲子園2018 予選 G]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0385 考察過程 1. 愚直にシミュレートして行けば良さそう 2. そのためには昇順になったかを高速に判定する必要がある 3. Aを昇順にしたものと同じ場所になった個数を数えればいい？ 4. 同じ…

ボゾソート [パソコン甲子園2018 予選 F]

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…

デュードニー数 [パソコン甲子園2018 予選 E]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0383 考察過程 1. まだ難しくなる段階じゃない 2. 何か全探索する対象を探す 3. 1リットルを買う個数を全探索し、足りない分を500ミリリットル買うことにする 解法 https://onlinejudge.u-a…

熱中症対策 [パソコン甲子園2018 予選 D]

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つにまとめて、再分配することを考える。 自分を入…

ケーキパーティー [パソコン甲子園2018 予選 C]

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関数で絶対値…

赤とんぼ [パソコン甲子園2018 予選 B]

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; //---------------------…

摂氏華氏 [パソコン甲子園2018 予選 A]

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をする。…

力持ち [パソコン甲子園2014 予選 I]

https://beta.atcoder.jp/contests/arc103/tasks/arc103_c 考察過程 1. 実験してみると、作れる最低条件が3つ見つかる 2. 「S[0]は1」「S[N-1]は0」「Sの[0,N-2]は回分になっている」 3. これ以外なら作れると仮定して考える 4. 1なら普通に辺を伸ばせば大丈…

Tr/ee [AtCoder Regular Contest 103 E]