記事一覧
D - Wizard in Maze
・問題URL https://atcoder.jp/contests/abc176/tasks/abc176_d ・思考・DFSかBFSで迷うけど、何回のワープでたどり着けるか、0,1,2....回の順に決まっていくイメージだ…
D - Coloring Edges on Tree
・問題URL https://atcoder.jp/contests/abc146/tasks/abc146_d ・思考・各頂点から出てる辺の最大値が使う種類なのはわかる ・問題は各辺の色をどうやって復元するか ・…
E - Integer Sequence Fair
・問題URL https://atcoder.jp/contests/abc228/tasks/abc228_e ・思考・配列の個数はK^N個、点数の付け方それぞれの配列にM通り、あれ？答えMのK^N乗じゃね？(本番はこ…
D - Happy Birthday! 2
・問題URL https://atcoder.jp/contests/abc200/tasks/abc200_d ・思考・Aは200で割った余りにしといてよさそう(あんま意味ない) ・Aからいくつかとってできたある数列20…
D - Preparing Boxes
・問題URL https://atcoder.jp/contests/abc134/tasks/abc134_d ・思考・当たり前だが、入れる/入れないのbit全探索は無理。 ・N番目の箱に入れるかは決まってる。 ・と…
D - Sum of Large Numbers
・問題URL https://atcoder.jp/contests/abc163/tasks/abc163_d ・発想・10¹⁰⁰？なんだこれ。 ・例えばi個取り出す際、その取り出し方を全部調べて何種類あるか…みた…
B - Increasing Triples
・問題URL https://atcoder.jp/contests/arc123/tasks/arc123_b ・発想・爆死回で解けなかったやつ。もう一回冷静に考えたら解けた。 ・とりあえずABCをsortしてもええや…
D - Rectangles
・問題URL https://atcoder.jp/contests/abc218/tasks/abc218_d ・発想・4重ループは無理。 ・3重ループに出きれば長方形は確定するのにと思ったが、対角線上の2 点決ま…
076 - Cake Cut（★3）
・問題URL https://atcoder.jp/contests/typical90/tasks/typical90_bx ・発想・輪になってんのうざいから直線にしたれ。ってのは思いついたけど、前は二分探索知らなく…
D - Cooking
・問題URL https://atcoder.jp/contests/abc204/tasks/abc204_d ・発想・Tの各要素を２つのうちどちらかのオーブンに割り振って、できるだけ均等になるようにする。んで…
D - Pair of Balls
・問題URL https://atcoder.jp/contests/abc216/tasks/abc216_d ・発想・本番で解けなかったやつ。 ・”筒”がいかにもqueueやstackを匂わせている。 ・解法「毎回筒の…
D - Ki
・問題URL https://atcoder.jp/contests/abc138/tasks/abc138_d ・発想・youtubeのBFSゆっくり解説でみた問題。 ・愚直にシミュレーションをするとO(NQ)でアウト。 ・解…
D - Wandering
・問題URL https://atcoder.jp/contests/abc182/tasks/abc182_d ・発想・ぜんぶでN²/2回くらい動くのでシミュレーションは無理。 ・最初見たとき「累積和の累積和」的な…
D - RGB Triplets
・問題URL https://atcoder.jp/contests/abc162/tasks/abc162_d ・発想・ijk３つの全探索は無理 ・ijだけ全探索すると間に合い、j+1番目からN番目までで、i,j番目の要素…
D - Querying Multiset
・問題URL https://atcoder.jp/contests/abc212/tasks/abc212_d ・発想・本番であと一歩のところ？で解けなかったやつ ・P=2で毎回足すのは無理だから足したふりをして答…
D - Gathering Children
・問題URL https://atcoder.jp/contests/abc136/tasks/abc136_d ・発想・10¹⁰⁰回シミュレーションするのは無理。 ・出力例を見ると、00120003400みたいに0の塊と1以上…
D - Wizard in Maze
・問題URL
https://atcoder.jp/contests/abc176/tasks/abc176_d
・思考・DFSかBFSで迷うけど、何回のワープでたどり着けるか、0,1,2....回の順に決まっていくイメージだからBFSがよさげ
・BFSで迷路を進み、壁に当たったら一歩前から5×5マスにワープで移動できるマス探してcost++すればいいかな？…
・キーワード・0-1BFS
・
D - Coloring Edges on Tree
・問題URL
https://atcoder.jp/contests/abc146/tasks/abc146_d
・思考・各頂点から出てる辺の最大値が使う種類なのはわかる
・問題は各辺の色をどうやって復元するか
・辺に色塗るの初めてでやばい
・キーワード・DFS
・解法・答えはiの昇順に出力しなきゃダメだから、隣接リストにつながってる頂点だけでなく辺のindexも入れる。pair使えばいい
E - Integer Sequence Fair
・問題URL
https://atcoder.jp/contests/abc228/tasks/abc228_e
・思考・配列の個数はK^N個、点数の付け方それぞれの配列にM通り、あれ？答えMのK^N乗じゃね？(本番はこれからです…)
・キーワード・繰り返し二乗法
・フェルマーの小定理
・解法・以下P=998244353とする。
・M^(K^N)modP≠M^((K^N)modP)modP
D - Happy Birthday! 2
・問題URL
https://atcoder.jp/contests/abc200/tasks/abc200_d
・思考・Aは200で割った余りにしといてよさそう(あんま意味ない)
・Aからいくつかとってできたある数列201種類を持ってくるとその中に200で割った余りが等しいものが存在する
・Nがでかいときも、Aのうち初めの数個全探索すればいいのでは
・キーワード・鳩ノ巣の原理
・bit全探
D - Preparing Boxes
・問題URL
https://atcoder.jp/contests/abc134/tasks/abc134_d
・思考・当たり前だが、入れる/入れないのbit全探索は無理。
・N番目の箱に入れるかは決まってる。
・となると、N-1、N-2...みたいに大きい順から決まっていきそうだけど、例えば8、4、2みたいな共通する約数を持つ箱はどうしよう
・キーワード・調和級数
・解法・大きい箱から
D - Sum of Large Numbers
・問題URL
https://atcoder.jp/contests/abc163/tasks/abc163_d
・発想・10¹⁰⁰？なんだこれ。
・例えばi個取り出す際、その取り出し方を全部調べて何種類あるか…みたいなのは無理。
・解法・10¹⁰⁰は、Nに対してバチクソでかい。これは、取り出す個数が変わると10¹⁰⁰+iのiが無視出来て、絶対に総和が同じ値にはならないということを意味する。
B - Increasing Triples
・問題URL
https://atcoder.jp/contests/arc123/tasks/arc123_b
・発想・爆死回で解けなかったやつ。もう一回冷静に考えたら解けた。
・とりあえずABCをsortしてもええやろ。
・解法・Aは出来るだけ小さいの使いたい。
・となるとBのうち、minA以下の要素はもうつかわない。
・次にBもできるだけ小さいの使いたい。
・となるとCのうち、残ってる
D - Rectangles
・問題URL
https://atcoder.jp/contests/abc218/tasks/abc218_d
・発想・4重ループは無理。
・3重ループに出きれば長方形は確定するのにと思ったが、対角線上の2
点決まれば長方形は確定。
・setに座標ぶち込んでいって、2重ループで所属判定すればギリ間に合いそう。どうだろ。
・解法発想の通り。最後２で割るの忘れない(こーゆーのは忘れてもサンプル
076 - Cake Cut（★3）
・問題URL
https://atcoder.jp/contests/typical90/tasks/typical90_bx
・発想・輪になってんのうざいから直線にしたれ。ってのは思いついたけど、前は二分探索知らなくて無理だった。
・解法ケーキを直線にして同じのもう一個つなげると「連続するピース」が扱いやすい。（別に３個以上連続してもその区間は答えにならないから、３個以上つなげてもいい。）
D - Cooking
・問題URL
https://atcoder.jp/contests/abc204/tasks/abc204_d
・発想・Tの各要素を２つのうちどちらかのオーブンに割り振って、できるだけ均等になるようにする。んで大きいほうが答え(すなわちΣT-(Tから合計が(ΣT)/2を超えないように選んだ時の最大値))ってのはすぐに分かり、これはナップサックDPとかいうやつだなと思ったが知らんので調べる。
D - Pair of Balls
・問題URL
https://atcoder.jp/contests/abc216/tasks/abc216_d
・発想・本番で解けなかったやつ。
・”筒”がいかにもqueueやstackを匂わせている。
・解法「毎回筒の先頭を全部見て、同じのがあったら消してシフト」みたいなことをするとO(NM)はかかるのでダメ。もう一本筒QUEを作り、M本の筒の先頭にある色iの個数=2ならその色をQUEに
D - Wandering
・問題URL
https://atcoder.jp/contests/abc182/tasks/abc182_d
・発想・ぜんぶでN²/2回くらい動くのでシミュレーションは無理。
・最初見たとき「累積和の累積和」的なものをN種類求めてうまくいくのでは？と考えたが間違い。なぜなら各動作の終わりで最大になるとは限らないから。
・解法各動作を独立として考えたとき、移動前と後の相対座標の最大値をそれ
D - RGB Triplets
・問題URL
https://atcoder.jp/contests/abc162/tasks/abc162_d
・発想・ijk３つの全探索は無理
・ijだけ全探索すると間に合い、j+1番目からN番目までで、i,j番目の要素と異なるものの個数がわかればよさそう。これは３色とも累積和でO(N)で求められる
・２つ目の条件どーしよー
・解法累積和でSのx文字目までのRGBの数を全部求めておき、i
D - Querying Multiset
・問題URL
https://atcoder.jp/contests/abc212/tasks/abc212_d
・発想・本番であと一歩のところ？で解けなかったやつ
・P=2で毎回足すのは無理だから足したふりをして答えだすときに足す
・setの重複ありverみたいなのあれば解けそう
・解法発想は〇。setの重複ありverはpriority_queueにひと手間加えるだけでいいらしい。くやしい
D - Gathering Children
・問題URL
https://atcoder.jp/contests/abc136/tasks/abc136_d
・発想・10¹⁰⁰回シミュレーションするのは無理。
・出力例を見ると、00120003400みたいに0の塊と1以上の塊がある。そうか、RLで挟まれるとそこを右往左往するだけか。しかも端っこは抜け出せないようになってるから絶対RRR・・・RRLL・・・LLLが何回か続く形の入力。
・