はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミング

Number of Amidakuji [AtCoder Beginner Contest 113 D]

https://beta.atcoder.jp/contests/abc113/tasks/abc113_d 前提知識 https://www.hamayanhamayan.com/entry/2017/02/27/021246:titie=動的計画法 解説 https://beta.atcoder.jp/contests/abc113/submissions/3558659dpで解く。 1,2,3,...,W本目ではなく、0,1…

ID [AtCoder Beginner Contest 113 C]

https://beta.atcoder.jp/contests/abc113/tasks/abc113_c 解説 https://beta.atcoder.jp/contests/abc113/submissions/3558586流れは以下の通り。 1. 県ごとに市を分ける 2. 県ごとに市の誕生年でソートし、順番に認識番号を作る 3. 最後に順番に答えていく…

Palace [AtCoder Beginner Contest 113 B]

https://beta.atcoder.jp/contests/abc113/tasks/abc113_b 解説 https://beta.atcoder.jp/contests/abc113/submissions/3558578温度がT-H[i]*0.006であり、小数になる可能性があるので、doubleで計算していこう。 全ての高さについて全探索しよう。 温度差は…

Discount Fare [AtCoder Beginner Contest 113 A]

https://beta.atcoder.jp/contests/abc113/tasks/abc113_a 解説 https://beta.atcoder.jp/contests/abc113/submissions/3558553答えはX+Y/2になる。 計算して求めよう。 今回の問題では大丈夫だが、整数の割り算をするときは小数点以下切り捨てになることを…

Align [Tenka1 Programmer Contest C]

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

Exchange [Tenka1 Programmer Beginner Contest B]

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

Measure [Tenka1 Programmer Beginner Contest A]

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関数を使…

Ito Campus [九州大学プログラミングコンテスト2018 C]

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

Tapu & Tapi [九州大学プログラミングコンテスト2018 B]

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

QUPC [九州大学プログラミングコンテスト2018 A]

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

yuki国のお財布事情 [yukicoder No.748]

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

循環小数N桁目 Hard [yukicoder No.747]

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しながら足し合わせる…

7の倍数 [yukicoder No.746]

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

letinopia raoha [yukicoder No.745]

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

循環小数N桁目 Easy [yukicoder No.744]

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…

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

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

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

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

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

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

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

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

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

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

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

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

Partition [AtCoder Beginner Contest 112 D]

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

Pyramid [AtCoder Beginner Contest 112 C]

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

Time Limit Exceeded [AtCoder Beginner Contest 112 B]

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

Programming Education [AtCoder Beginner Contest 112 A]

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

Segments on a Polygon [yukicoder No.743]

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

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

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

AscNumber(Easy) [yukicoder No.741]

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

幻の木 [yukicoder No.740]

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

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

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