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

hamayanhamayan's blog

競技プログラミング

エレベーター [yukicoder No.801]

https://yukicoder.me/problems/no/801 前提知識 動的計画法更新最適化(累積和, imos) 解法 https://yukicoder.me/submissions/325930dp[k][floor] := k回移動後にfloor回にいる組合せ でDPしよう。 dp[k][???]からdp[k+1][???]を高速に更新することを考え…

四平方定理 [yukicoder No.800]

https://yukicoder.me/problems/no/800 解説 https://yukicoder.me/submissions/325337まずはz,wを全列挙しよう。 z,wがわかっていれば、d = w^2 + D - z^2とおくと、 x^2 + y^2 = d を満たすx,yの組が分かれば、それを答えに足せばいいと分かる。 よって、z…

赤黒かーどげぇむ [yukicoder No.799]

https://yukicoder.me/problems/no/799 解説 https://yukicoder.me/submissions/325296「全通り-被ってしまった場合」で答えを出す。 全通りは、(B-A+1)*(D-C+1)である。 被ってしまった場合は、同じ数がでてきた場合になるので、[A,B]と[C,D]が重なっている…

Reversi [AtCoder Grand Contest 031 B]

https://atcoder.jp/contests/agc031/tasks/agc031_b 前提知識 動的計画法更新最適化(累積和) 解説 https://atcoder.jp/contests/agc031/submissions/4597345まず、もともとの数列で同じ色の石が連続していても数え上げには影響が無いので、圧縮しておく。…

Differ by 1 Bit [AtCoder Grand Contest 031 C]

https://atcoder.jp/contests/agc031/tasks/agc031_c 解法 https://atcoder.jp/contests/agc031/submissions/4606271!!注意!!もっとスマートな解法があります!!まず、"NO"となるのは、AとBで立っているビット数のパリティが一致しているとき。 まずパ…

コレクション [yukicoder No.798]

https://yukicoder.me/problems/no/798 前提知識 DPテク2「選択するものを最初にソートしておくと、DPできたり、状態を同一化できたりする」 解説 https://yukicoder.me/submissions/323864買うか買わないかという問題なので、ナップサック系DP感があるので…

Noelちゃんとピラミッド [yukicoder No.797]

https://yukicoder.me/problems/no/797 解説 https://yukicoder.me/submissions/323248二項定数を使って解く。 パスカルの三角形っぽかったので、N=4くらいで実験したら、二項定数だったので、それで通した。 a[i]*aCb(N-1,i)の総和を取って答えとする(iは0…

well known [yukicoder No.796]

https://yukicoder.me/problems/no/796 解説 https://yukicoder.me/submissions/3232233つの条件を見たときに、一番制約が厳しいのが最後の条件である。 なるべく小さい数の方が良いので、その方向で考える。 全部1にして、1つだけ3にすれば、下2つの制約は…

Restrictions!!!!!!!!!!!!!! [yukicoder No.795]

https://yukicoder.me/problems/no/795 解説 https://yukicoder.me/submissions/323204制約をよく見てみると、M=10Nとある。 つまり、100円玉の総額と、10円玉の総額は等しいことになる。 よって、asdf1君は全部100円で、asdf2君は全部10円で受け取れば同じ…

約数ゲーム / Divisor Game [Ritsumeikan University Competitive Programming Camp 2019 Day 3 C]

https://onlinejudge.u-aizu.ac.jp/services/room.html#RitsCamp19Day3/problems/C 前提知識 素因数分解 解説 https://onlinejudge.u-aizu.ac.jp/services/review.html#RitsCamp19Day3/3419470実験しながら考察すると 最小回数は、素因数を1つだけ削った数だ…

括弧を語る数 / Parentheses Number Ritsumeikan University Competitive Programming Camp 2019 Day 3 B]

https://onlinejudge.u-aizu.ac.jp/services/room.html#RitsCamp19Day3/problems/B 解説 https://onlinejudge.u-aizu.ac.jp/services/review.html#RitsCamp19Day3/3419433貪欲に構築していこう。 )を入れる前に(の数が足りない場合は、その分入れる。 足りて…

情報検索 / Information Search Ritsumeikan University Competitive Programming Camp 2019 Day 3 A]

https://onlinejudge.u-aizu.ac.jp/services/room.html#RitsCamp19Day3/problems/A 解説 https://onlinejudge.u-aizu.ac.jp/services/review.html#RitsCamp19Day3/3419402尺取法っぽくやっていこう。 順番に見ていって、一緒ならand,orどっちもにも入れて、…

First Kiss [Ritsumeikan University Competitive Programming Camp 2019 Day 2 G]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp19Day2/problems/G 前提知識 Grundy数 解説 https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp19Day2/3419060Grundy数が分からない場合は、そちらを先に勉強しよう。 逆にそれがわかっ…

こたつがめを燃やさないで [Ritsumeikan University Competitive Programming Camp 2019 Day 2 E]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp19Day2/problems/E 前提知識 ダイクストラ 解説 https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp19Day2/3419049ダイクストラで解く。 dis[y][x] := (x,y)へ到達するための最小コスト …

Phone Number [Ritsumeikan University Competitive Programming Camp 2019 Day 2 C]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp19Day2/problems/C 解説 https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp19Day2/3419010方針としては、答えとしてあり得る盤面を全列挙する。 盤面は全部で9!通りなので、これは列挙…

Lunch [Ritsumeikan University Competitive Programming Camp 2019 Day 2 A]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp19Day2/problems/A 解説 https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp19Day2/3419004A,B,Cのうち最大の数を答える問題。 実装はそれぞれだと思うが、自分の実装は以下の通り。 int…

LISum [Ritsumeikan University Competitive Programming Camp 2019 Day 1 E]

https://onlinejudge.u-aizu.ac.jp/services/room.html#RitsCamp19Day1/problems/E 前提知識 LIS 解説 https://onlinejudge.u-aizu.ac.jp/services/review.html#RitsCamp19Day1/3418982LISをセグメントツリーで解く場合は、 st[i] := 最後の数がiとなる増加…

場所当てゲーム [Ritsumeikan University Competitive Programming Camp 2019 Day 1 D]

https://onlinejudge.u-aizu.ac.jp/services/room.html#RitsCamp19Day1/problems/D 前提知識 インタラクティブ 解説 N≦10の場合は全て聞けば答えが求まるので、solve1で解く。 10<Nのsolve2での解き方が問題である。 リアクティブ問題は微妙に方針が決まっ…

たぬきつね [Ritsumeikan University Competitive Programming Camp 2019 Day 1 B]

https://onlinejudge.u-aizu.ac.jp/services/room.html#RitsCamp19Day1/problems/B 解説 https://onlinejudge.u-aizu.ac.jp/services/review.html#RitsCamp19Day1/3415072シミュレーションする。 関数Mを作ろう。M(T,F)だけ例外的なので、これに注目すると作…

タイル貼り [Ritsumeikan University Competitive Programming Camp 2019 Day 1 A]

https://onlinejudge.u-aizu.ac.jp/services/room.html#RitsCamp19Day1/problems/A 解説 https://onlinejudge.u-aizu.ac.jp/services/review.html#RitsCamp19Day1/3415062覆われていない部分の面積=長方形の面積ー覆われている面積 これで計算する。 長方形…

Decayed Bridges [AtCoder Beginner Contest 120 D]

https://atcoder.jp/contests/abc120/tasks/abc120_d 前提知識 UnionFind 解説 https://atcoder.jp/contests/abc120/submissions/4460557「連結を分離させていく操作は、時間を逆に見て連結させていく操作で考える」というテクを使う。 連結成分を分けること…

Unification [AtCoder Beginner Contest 120 C]

https://atcoder.jp/contests/abc120/tasks/abc120_c 解説 https://atcoder.jp/contests/abc120/submissions/4460380全ての操作後を考えてみると、0のみか1のみになっていることが分かる。 かつ、全ての操作は0と1が1つずつ消えていくので、キューブを取り除…

K-th Common Divisor [AtCoder Beginner Contest 120 B]

https://atcoder.jp/contests/abc120/tasks/abc120_b 解説 https://atcoder.jp/contests/abc120/submissions/4460300答えの候補は、A,B≦100なので、1~100である。 これを大きい方から見ていって、AもBも割り切るなら、配列vに入れていく。 入れた中でK番目…

Favorite Sound [AtCoder Beginner Contest 120 A]

https://atcoder.jp/contests/abc120/tasks/abc120_a 解説 https://atcoder.jp/contests/abc120/submissions/4459527所持品で鳴らせる音の回数と最大回数の小さい方が答えになる。 つまり、min(B/A,C)が答え int A, B, C; //-------------------------------…

Lazy Faith [AtCoder Beginner Contest 119 D]

https://atcoder.jp/contests/abc119/tasks/abc119_d 解説 https://atcoder.jp/contests/abc119/submissions/4378458まず、lower_boundを知らない場合は学ぼう。 これを使うと、あるx以上で最も近い、Sの要素、Tの要素がO(logN)で得られる。 要素の添字を-1…

Synthetic Kadomatsu [AtCoder Beginner Contest 119 C]

https://atcoder.jp/contests/abc119/tasks/abc119_c 解説 https://atcoder.jp/contests/abc119/submissions/4378296与えられた操作は順番によって、状況が変化したり、損をすることが無いので、別々に考えよう。 何か全探索する所を探すと、ある竹について…

Digital Gifts [AtCoder Beginner Contest 119 B]

https://atcoder.jp/contests/abc119/tasks/abc119_b 解説 https://atcoder.jp/contests/abc119/submissions/4378009単位変換をする問題であるが、問題にあることをそのまま実装する。 BTCのものだけ円に変換して、総和を取ると答え。 自分は小数を出力する…

Still TBD [AtCoder Beginner Contest 119 A]

https://atcoder.jp/contests/abc119/tasks/abc119_a 解説 https://atcoder.jp/contests/abc119/submissions/4377976入力が少し複雑なのだが、C++ならscanfという便利な関数があるので、これを利用するとスマートに入力が得られる。 あとは、平成との比較だ…

Gourmet choice [Codeforces Round #541 (Div. 2) D]

https://codeforces.com/contest/1131/problem/DN要素の配列X、M要素の配列Yを構築する。 A[x][y] := X[x]とY[y]の大小関係。<ならX[x]<Y[y]、>ならX[x]>Y[y]、=ならX[x]=Y[y] 配列Aが与えられたときに、配列X,Yを構築できるか判定し、できるなら構築せ…

Dangerous Hopscotch [「みんなのプロコン 2019」決勝 D]

https://atcoder.jp/contests/yahoo-procon2019-final/tasks/yahoo_procon2019_final_d 前提知識 半環問題 解説 https://atcoder.jp/contests/yahoo-procon2019-final/submissions/4353743半環をSegtreeであつかうテクを使う。 このテクを知らない場合は、先…