競プロを始めた白金燐子

あ……またTLE……(；ﾟДﾟ)

競プロを始めた白金燐子

あ……またTLE……(；ﾟДﾟ)

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 ・deque ・解法・queue使ったBFSじゃダメ。なぜなら、ワープで飛んでみ

競プロを始めた白金燐子

    • D - Coloring Edges on Tree

      ・問題URL https://atcoder.jp/contests/abc146/tasks/abc146_d ・思考・各頂点から出てる辺の最大値が使う種類なのはわかる ・問題は各辺の色をどうやって復元するか ・辺に色塗るの初めてでやばい ・キーワード・DFS ・解法・答えはiの昇順に出力しなきゃダメだから、隣接リストにつながってる頂点だけでなく辺のindexも入れる。pair使えばいいね ・void dfs(現在の頂点、今禁じられた色now(now=1,2,3..

      競プロを始めた白金燐子

      • 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じゃないので。 ・M%P=0のとき、答え0。 ・そうじゃないとき、この時に限って

        競プロを始めた白金燐子

        • D - Happy Birthday! 2

          ・問題URL https://atcoder.jp/contests/abc200/tasks/abc200_d ・思考・Aは200で割った余りにしといてよさそう(あんま意味ない) ・Aからいくつかとってできたある数列201種類を持ってくるとその中に200で割った余りが等しいものが存在する ・Nがでかいときも、Aのうち初めの数個全探索すればいいのでは ・キーワード・鳩ノ巣の原理 ・bit全探索 ・解法・N≤8の場合、2⁸=256だから、Aの各要素をB(あるいはC)に入

          競プロを始めた白金燐子

        D - Wizard in Maze

        競プロを始めた白金燐子

          D - Preparing Boxes

          ・問題URL https://atcoder.jp/contests/abc134/tasks/abc134_d ・思考・当たり前だが、入れる/入れないのbit全探索は無理。 ・N番目の箱に入れるかは決まってる。 ・となると、N-1、N-2...みたいに大きい順から決まっていきそうだけど、例えば8、4、2みたいな共通する約数を持つ箱はどうしよう ・キーワード・調和級数 ・解法・大きい箱から決めていく。まず箱Nが決まる。N-1以降で箱iに入れるかは、箱2i,3i,...

          競プロを始めた白金燐子

          D - Preparing Boxes

          競プロを始めた白金燐子

          D - Sum of Large Numbers

          ・問題URL https://atcoder.jp/contests/abc163/tasks/abc163_d ・発想・10¹⁰⁰？なんだこれ。 ・例えばi個取り出す際、その取り出し方を全部調べて何種類あるか…みたいなのは無理。 ・解法・10¹⁰⁰は、Nに対してバチクソでかい。これは、取り出す個数が変わると10¹⁰⁰+iのiが無視出来て、絶対に総和が同じ値にはならないということを意味する。 ・となると、0~Nをi個取り出した時の総和の種類を、K≤i≤N+1で、別々に求

          競プロを始めた白金燐子

          D - Sum of Large Numbers

          競プロを始めた白金燐子

          B - Increasing Triples

          ・問題URL https://atcoder.jp/contests/arc123/tasks/arc123_b ・発想・爆死回で解けなかったやつ。もう一回冷静に考えたら解けた。 ・とりあえずABCをsortしてもええやろ。 ・解法・Aは出来るだけ小さいの使いたい。 ・となるとBのうち、minA以下の要素はもうつかわない。 ・次にBもできるだけ小さいの使いたい。 ・となるとCのうち、残ってるBの中でのminB以下の要素は使わない。 ・条件を満たすCの要素のうち最小なのを

          競プロを始めた白金燐子

          B - Increasing Triples

          競プロを始めた白金燐子

          D - Rectangles

          ・問題URL https://atcoder.jp/contests/abc218/tasks/abc218_d ・発想・4重ループは無理。 ・3重ループに出きれば長方形は確定するのにと思ったが、対角線上の2 点決まれば長方形は確定。 ・setに座標ぶち込んでいって、2重ループで所属判定すればギリ間に合いそう。どうだろ。 ・解法発想の通り。最後２で割るの忘れない(こーゆーのは忘れてもサンプル見れば気づくが)。二重ループとその中の所属判定がボトルネックでO(N²logN)

          競プロを始めた白金燐子

          D - Rectangles

          競プロを始めた白金燐子

          076 - Cake Cut（★3）

          ・問題URL https://atcoder.jp/contests/typical90/tasks/typical90_bx ・発想・輪になってんのうざいから直線にしたれ。ってのは思いついたけど、前は二分探索知らなくて無理だった。 ・解法ケーキを直線にして同じのもう一個つなげると「連続するピース」が扱いやすい。（別に３個以上連続してもその区間は答えにならないから、３個以上つなげてもいい。）次に、小数は危険なので全部のピースを10倍して前から累積和を出す。累積和の配列を

          競プロを始めた白金燐子

          076 - Cake Cut（★3）

          競プロを始めた白金燐子

          D - Cooking

          ・問題URL https://atcoder.jp/contests/abc204/tasks/abc204_d ・発想・Tの各要素を２つのうちどちらかのオーブンに割り振って、できるだけ均等になるようにする。んで大きいほうが答え(すなわちΣT-(Tから合計が(ΣT)/2を超えないように選んだ時の最大値))ってのはすぐに分かり、これはナップサックDPとかいうやつだなと思ったが知らんので調べる。 ・本番では苦し紛れに「Tを降順にsortして、合計が少ない方に入れていく」という

          競プロを始めた白金燐子

          D - Cooking

          競プロを始めた白金燐子

          D - Pair of Balls

          ・問題URL https://atcoder.jp/contests/abc216/tasks/abc216_d ・発想・本番で解けなかったやつ。 ・”筒”がいかにもqueueやstackを匂わせている。 ・解法「毎回筒の先頭を全部見て、同じのがあったら消してシフト」みたいなことをするとO(NM)はかかるのでダメ。もう一本筒QUEを作り、M本の筒の先頭にある色iの個数=2ならその色をQUEに入れる。次にQUEから順番に色を取り出してその色があった二本の筒の中身をシフトす

          競プロを始めた白金燐子

          D - Pair of Balls

          競プロを始めた白金燐子

          D - Ki

          ・問題URL https://atcoder.jp/contests/abc138/tasks/abc138_d ・発想・youtubeのBFSゆっくり解説でみた問題。 ・愚直にシミュレーションをするとO(NQ)でアウト。 ・解法・まず入力の分だけカウントして１から追っていき、親のカウンターの数を足していっても同じ。これはO(N)ゆえ、BFS,DFSだとO(N+Q)で解ける。 ・コード・BFS.ver int main(){ int N,Q; cin>>N>>Q;

          競プロを始めた白金燐子

          D - Ki

          競プロを始めた白金燐子

          D - Wandering

          ・問題URL https://atcoder.jp/contests/abc182/tasks/abc182_d ・発想・ぜんぶでN²/2回くらい動くのでシミュレーションは無理。 ・最初見たとき「累積和の累積和」的なものをN種類求めてうまくいくのでは？と考えたが間違い。なぜなら各動作の終わりで最大になるとは限らないから。 ・解法各動作を独立として考えたとき、移動前と後の相対座標の最大値をそれぞれ別で求めておく。今の座標＋その最大値が答えか？それとも一回動作をすべてやった

          競プロを始めた白金燐子

          D - Wandering

          競プロを始めた白金燐子

          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,jで全探索(O(N²))。 二つ目の条件を満たさないとき、iとkの平均がjゆえ

          競プロを始めた白金燐子

          D - RGB Triplets

          競プロを始めた白金燐子

          D - Querying Multiset

          ・問題URL https://atcoder.jp/contests/abc212/tasks/abc212_d ・発想・本番であと一歩のところ？で解けなかったやつ ・P=2で毎回足すのは無理だから足したふりをして答えだすときに足す ・setの重複ありverみたいなのあれば解けそう ・解法発想は〇。setの重複ありverはpriority_queueにひと手間加えるだけでいいらしい。くやしい。勉強します…… ちなみにXをintにするとsumが結構大きくなって負の方向でオ

          競プロを始めた白金燐子

          D - Querying Multiset

          競プロを始めた白金燐子

          D - Gathering Children

          ・問題URL https://atcoder.jp/contests/abc136/tasks/abc136_d ・発想・10¹⁰⁰回シミュレーションするのは無理。 ・出力例を見ると、00120003400みたいに0の塊と1以上の塊がある。そうか、RLで挟まれるとそこを右往左往するだけか。しかも端っこは抜け出せないようになってるから絶対RRR・・・RRLL・・・LLLが何回か続く形の入力。 ・RLの変わり目に人があつまって（10¹⁰⁰がバカでかいので絶対全員変わり目に行き

          競プロを始めた白金燐子

          D - Gathering Children

          競プロを始めた白金燐子