Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

yukicoder contest No.222 反省会

鬼のセグメントツリー祭。★の数的に頭の3問しか勝負にならなそうなので、これだけは解くぞと思って望んだが、Cが解けなかった。2完。順位は77/133 A No.875 Range Mindex Query - yukicoder ただ最小値を求めるだから簡単だが、そのインデックスを求めろとい…

【DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 C ロト2】約数の数に問題を圧縮する系

なるほどなーと思う問題でした。自力AC出来なかったです。109の約数がたかだか1300個程度しかないという知識を活かして問題を圧縮する系です。今回もそんな臭いはしたけど、一歩踏み込めなかったです。 C - ロト2 問題 長さNの数列aが与えられる。このうちai…

【第5回 ドワンゴからの挑戦状 予選 B Sum AND Subarrays】本当に400点なのか?

XORを扱う問題は多いけどANDを扱う問題は少ない。大変良く出来た問題だと思ったのでまとめ。 B - Sum AND Subarrays 問題 長さNの数列が与えられる。(N=103) この数列のうち、範囲[l,r]の和はN(N-1)/2個あるが、この中からK個選び、ANDをとりたい。その時の…

【ARC076-B Built?】クラスカル法の理解「どうせ選ばれない枝には興味がない」

D - Built? 問題 平面上にN個の点がある。点(a,b)と点(c,d)を結ぶ時、コストmin(|a-c|,|b-d|)がかかる。いくつかの点を結んで、N個の点を連結させたい。その時の合計コストはいくらか? 方針 最小全域木のコストを調べればよい。(閉路があるなら、枝を削除…

【AGC034-A Kenken Race】ある瞬間に着目する

A - Kenken Race 問題 N個のマスがあり、石が置いてあったり置いてなかったりする。Nは5乗。 すぬけくんはAから、ふぬけくんはB(A<B)から、それぞれCとDを目指す。一回の操作につき、自分の1つ右か自分の2つ右にしか移動出来ない。石のあるマスや、相方がいるマスには移動出来ないとすると、これは達成可能か? 方針 一人でやるならば簡単。 C<Dの時も簡単。まずはふぬけを動かしてからすぬけを動かせば一人でやるのに等しい。 C>Dは、すぬけくんがふぬけくんを追い越す必要があるため、追い越すとはどういうことなのかに注目する。 すると、 SF○ (○はすぬ</b)から、それぞれcとdを目指す。一回の操作につき、自分の1つ右か自分の2つ右にしか移動出来ない。石のあるマスや、相方がいるマスには移動出来ないとすると、これは達成可能か?>…

【AGC032-A Limited Insertion】最終図を想像する + 厳しい方から攻める + 逆算する

AGCはAでもすでに難しいことがある。早くB,Cで打率5割マンになりたい。 A - Limited Insertion 競プロあるあるな考え方なので紹介します。 問題 長さNの数列を以下のようにして作る。 i(1<=i<=N)番目の操作ではj(1<=j<=i)をj番目に挿入する こうやって出来た…

【TTPC2019-F Road Construction】グラフの変形

コンテスト中に解けなかったので解いておきます。 F - Road Construction 問題 コストつきのグラフが与えられる。これらの辺は最初、有効になっていない。このうち、いずれかの辺を有効化して、wからx、yからzの両方が通るようにしたい。最小のコストはいく…