Hatena::ブログ(Diary)

merom686の日記 このページをアンテナに追加 RSSフィード

2018-05-26

ARC098

3完。3問目をガチのスピードで解きに行けるようになりたいね。

C - Attention

WとEがどっちの向きを指しているのかわからない。もちろん少し考えればわかるけど、問題を解くうえで何度も使う概念、思考を要するようでは話にならない。さすがに問題文に東西がわからん人でも解けるよう説明があるはずと思い数秒探したが見つからず。今見たら「西から i 番目」と書いてあったのでこれでわかりますねー。やはり先週ほどではないけど体調は万全じゃない。落ち着いて「ギューン」と考えたいね。

300点にしては難しいという感覚。とはいえ時間をかけて問題を見ていれば、累積和があれば(牛刀かもしれないけど)解けるとわかる。300点だから思考停止で解けるのだ。そのまま深く考えず実装した。

D - Xor Sum 2

怖い問題名(1はまだ解いてない)。条件はどんなのかすぐわかった(O(N^2)でよければすぐ解けた)のだけど、そこからがやはり難しい。少ししてAが20bitで表せる制約なことに気づく(思い出す)。難しいのでその制約を足がかりにアイデアを出し、20個の各bit位置に対して直近の現れた位置を記録していく方法を思いついた。Aをなめていって、現在の位置を終端とする通り数を求める。直前の被ったbitがある場所の次から全部が条件を満たすはず。

実装したが、サンプルが通らない(サンプルに助けられた)。しばらく考えて、現在の位置と被るかしか見てないのはダメだと気づいた。真ん中に衝突してるペアが含まれてたら当然ダメ。なのでそれをとりあえず書き足した。衝突はその都度記録できるはず。衝突したペアの若い番号のほうの次からOK。サンプルが通った。今回は即座に提出した。AC。自信はなかった。ダメだった原因の一つを潰しただけだから。

と思ってたらしゃくとりで行けたらしい。はー。

E - Range Minimum Queries

いくつかの例を考える。333331333332333313333(3で揃える)、634193341431499(1で揃える)。こういうのをどれも解けるような解法でなければならない。やはり難しい。かなり考えてから、また制約を頼りに(あまり行儀のよろしくないメタ読みで)解法を探る。Nが2000なのでO(N^2logN)になりそうだ。tourist回のbitDPもちょっと思い出していた。2乗だから3乗の解法を2乗に落とすか、あるいは2乗も色々な方向が考えられる。

色々考えて行けそうな方針が出てきた。最小値(Y)をN通りに固定すると、それより小さいAで全体を区切れば、その区間内で小さいものから順に取ることは可能(「最小のものを取り除く」からね)。このときは、固定したY=A_iが最小だから必ず取れると思っていたが、Kより狭い区間に入ってたらダメだ。狭い区間からは取れないのわかってたのに、そこにすべてのYがあるという状況を考えられなかった。まあそこは b[q - 1] - b[0] と書いてたので問題にならず(b[0]をa[i]と書いていたらWAになるところだった)。

実装上の工夫として、区切って区間にする処理をするためAのvectorをN+2の長さとし、両端を-1にして必ず区切りになる番兵とした。あとそういえば最近、初期化する必要がない変数もわかりにくいバグを恐れて初期化するようになってきたな。

計算量は、全区間でソートしてもO(NlogN)以下で済むので大丈夫。実装はけっこう面倒で、元のAを壊してはいけないのでコピーしてソートになる。空のvectorにpushしていくのを考えたが、実行時間が気になる。reserveしても使ってからclearしたら解放されちゃう?一応N個のpush_backはO(N)なんだっけ?頭の中ではもう(定数倍も含めた)計算量のイメージが出来上がっており、それを変更するのはかなりの負荷になる。なのでメモリは最初に確保して自分で管理する実装にした。この実装はパターン化されているので速いしバグも入りにくい。小さい数をかき集めたら、改めてソートしてX-Yで最小値を更新する。長い長い実装だったが、ある程度の時間を残して書き切ることができた。

F - Donation

まあ解けないと思って読んでるわけですよ。残り時間もないし。ARC全完ってそれがそのまま早解きなんだなーって思う。早解きできても難しい問題が解けるとは限らないが、難しい問題をコンテスト中に通す人は早解きできている。

色々考えて、逆からやるとよさそうだなあと思う。逆から見れば、寄付はその頂点に初めて着いたときにするとしていいし、探索とかするのにもA円の制限は頂点に着いた時点でWを調節すればいい、お金は増える一方だから同じ頂点は何も考えず再訪できる。まあしかし、どこからスタート(ゴール)するのとか全然わからんしね。Bだけで決まるわけでもないし、A-Bみたいな量を使ったりするのかなとか思ったけど。まあO(N^2)が通らない制約なのでなんか上手いDPをするんだろうなという感じ。

2018-05-20

AGC024

AとCの2完。仮にBを考えていた時間でBが解けていたとしてもパフォーマンス1800行かないくらいなので、なんだこりゃ。Cを通したとき「人権を得た」と思ったけどそんなことなかった。青パフォ(1600以上)取れなかったのはすごく久しぶり。3月から競プロの時間を削ってぷよぷよやってたので、ようやくその成果が出てきたか。いやいや、1回の結果では何もわからんでしょ。ぷよぷよで3連勝したからって自分のほうが強いかどうかは全くわからないのだ。まあしかし、ここ最近パフォーマンス1900超えを連発できてたのはかなり謎。

A - Fairness

整数がどう変化していくかに興味を持った。Kはすごく大きいんだけどね。3回操作を行ったところまで計算して、差が規則的なことに気づいた(ここまで差を計算してない)。ACまで7分なのでけっこうかかっている。Unfairってソースにとりあえず書いたのとか裏目すぎて「ああこういうゲームじゃないのかー」という感じ。最初から差にだけ興味を持っておけばよかったのだが、よくわからん。結果論にも思えるし、俺は何か間違っていたのか?

B - Backfront

どうもカッチリ考えることができない。先頭にしか移動できないとしても(制限してより簡単な問題に変えても)この貪欲でいいことの証明が浮かばない。さすがにこれは正しいんだろうけどなあ。それをとりあえず両側からやる。BITを使った。今度は、先頭に動かしたあとで末尾に動かすという制限でやってみる。なんかO(NlogN)で行ける気がしたけど、結局できたと思ったのも勘違いで、できなかった。二分探索を考えたときは「これでO(N(logN)^2)は複雑すぎる、他に何かあるんじゃ?」と考え直してみたが、何もできず。BITに最小値を持たせることできたっけ、使い方に制限を加えればできたはず、とか考えてた。まあセグ木を使えばいいんだけど。2,4,1,3というケースで、1を処理したら逆から見たときに2より小さいものが2の右から消えてるんだよね。左右から見たときそれぞれの処理すべき数に印を付けそれぞれどこまで担当するのが最善か、みたいな。無理。

Cが解ける場合でも、さすがにBは最終的に解けるはずと時間を投入。50分弱考えてCに行った。

Cを通して帰ってきた。逆に考える。A_iとiをペアにしてA_iでソートしてiを見る。そのiを、端から好きな場所へ動かして何回で1,2,3,4,5に戻せるかを考えればいい。x,x,1,y,y,y,8,zみたいなとき、xとzは動かす必要がある。yはソート済みであればそのままでいいが、そうでないとき、最も長いソート済みの連続した部分列を残して(xzを処理したあとで)1や8を動かして削り取り再び中へ入れればいい。その1や8を動かすパートが片方しか必要でない場合もあるので面倒だ。さて、1と8が順に並んでいないケースに気づいた。残り15分。ちょっと修正できなかった。

C - Sequence Growing Easy

わりと限られた列しか出現しなさそう。入力例3を見ると1,2,2という部分がある。そういうのもあるのか。これは右の2を作ってから左の2を作るわけだ。適当な例を作って手を動かしてみる。1より多く増える場所があればダメだし、なければ作れるかな?思ったより作れる範囲が広い。後ろから考えていけばよさそう。一番後ろの正の数を作ったらそれを反映(3を作ったらその前の場所に1,2,3みたいに数を入れる)させて次へ、これでO(N^2)で解ける(もっと速いかもしれないけど)。反映にO(N)かかるのがいけないのだが解消できるだろうか。いやその、できそうなんだけど、オーダーが変わるような魔法があるとは思えない、魔法なしにオーダーが削減できそうなので怖がっているのだ。まあいけそうなのでそのまま実装、あっさり書けて、あっさりサンプルが通る。1分くらい見直して提出、AC。Bへ。

2018-05-18

yukicoder contest 191

4完。構築パラダイスだ。

No.687 E869120 and Constructing Array 1

本来なら1とn-1を出力したいところだが、nが20になり得るところ10以下で出力する必要がある。n/2と(n+1)/2にした。これは感覚的に上手く行くはず。nが1増えると和も1増える。こんな難しいことをせずともn/2とn-n/2にすればよかったか?いや、あっちのが簡単だろう。見えた答えが一番簡単だ。

No.688 E869120 and Constructing Array 2

状況がつかみにくいが、合計が2というのは1を2個と0を任意個選ぶということだ(ここまでにかなりの時間がかかった)。Nが30以下でできると保証されているので、Nと1の個数を全通り試せばいい。1がM個として、M個の中から2個を選びN-M個の各0について選ぶか選ばないか。

No.689 E869120 and Constructing Array 3

素数というのは難しそうだが、どうせ素数の性質は使わないのだろうと予想。Kは10000以下と比較的小さい。とりあえず1を140個でそのくらいになる。ここで、5,8というペアを使えば、1との組み合わせで素数になることはないので独立に個数を増やせる。5を1個とすれば8の個数で1ずつ調整可能。しかしNが250以下という制約に微妙に引っかかる。なので同じことをもう一段やる。こういうペアがもう一つあれば、今度はわりと余裕を持って構成できる。なかなか見つからない。素数って意外と多いんだよね。見つけるプログラムをパッと書いてというのが本来の姿だと思うが、プログラムを書く面倒臭さが手計算の面倒臭さを上回ってしまい、結局手で見つけた。1,5,8,13,34。あとは書くだけだが、ここはパターン化されていないので厄介だ。まあ空のfor文を書いて堅実に作っていった。

No.690 E869120 and Constructing Array 4

木か?と思ったけど木じゃない。どうやって組合せを爆発させるかわからない。2乗っぽく見える。Kが10^9でNが32なので、スタートとゴールの2頂点を除いて2^30を作るということか?実際、その30頂点のそれぞれを通るか通らないかで2^30通りにできそう。本当か?いやあ、慣れないと感覚が全然だね。そもそもパスカルの三角形的な、経路を数えるやつと同じなんだけど、グラフという形で目の前に現れても、それが同じものだと気づかない。気づいても確信できない。

さて、どうやってKを作るか。けっこう複雑そうに思える。とりあえず全ての辺を張ってから、スタート地点からの1本を切ってみる。それで減るのは、そこからゴールまでの各頂点を通るかどうか。2冪を簡単に引ける?こんな簡単なの?感覚と違ったが、解けてることに反論できないので実装する。スタートからゴールへの辺はナシにする。これで2^30-1まで作れる。

No.691 E869120 and Constructing Array 5

難しそうなので撤退していた(やる気ないときは無理しないのだ)。まず、解けそうだと思った。方針としては、30個のe_iにほぼ均等に割り振り、大きさ順に並べたとき隣との差29個が対数のグラフ的になってるくらいにして、差が大きいほうから順に調整していく。しかし、10000と10000を10001と9999にしても10^-10には届かない。調整できたとして調整回数が大きくなりそう。3個や4個を組み合わせればもっと精度が出るんだろうけど。解けそうという感覚は変わらないものの、自分には無理だという感覚になった。

2018-05-12

ARC097

低得点ARC。3完勝負になるのか、あるいは難しくて2完できれば御の字になるのか。まあ難しかったんだけど。普通に2完だった。CDは、たまにはこういう問題欲しいよねという感じのだった。開始前に順位表から最初の問題を開いておいて、時間になったらF5。

C - K-th Substring

5000だから2乗は通る。Cなのに解き方が全然見えない。Kが5以下と異様に小さいことに気づく。構成してみるか。Kが1なら簡単。辞書順最小の1文字を取ってくればいい。2だったら、その1文字の後の最小文字を探す、最後の文字だけなら別の文字を、けっこう面倒だな。5は無理じゃね。substringはO(N^2)個だし、ソートといえばトライ木とか?いや無理だろうな。色々なケースを考えてみる。aaaaaaみたいな文字列かもしれないし、ランダムっぽい文字列かもしれない。文字列のタイプによって(人間が出力を考えるなら)戦略が変わってくる。

ん、長さ5のsubstringを考えれば、それより辞書順で小さいsubstringを自明に生成できるな。文字数を減らせば、ことなる文字列になるし、辞書順でも小さくなる。答えはK文字以下としてよさそうだ。それなら力ずくソートできるのでは。オーダーは大丈夫そうだが、string(つまりvector)を大量に持ってそれをソートするのはどうなんだ。まあいけるやろ。ある位置からK文字取れないこともある。それはif文で除いた。実際はuniqueかけるから問題ないんだろうけど、ここはしっかり書いておくところ。あとはsortしてuniqueしてK番目を出力するだけ。uniqueの使い方はググった。今回は問題の制約から戻り値を使う必要がなかった。

D - Equals

p_i=iとなる最小のiを最大化したいのだと誤読。そう読むと、そういうiが存在しないケースについて問題文やサンプルの説明を探すことになる。まあ誤読だったわけだ。個数を最大化したいのね。制約で、xとyを入れ替えた実質的に同じペアが許容されているように見えたのが気になった。いつものように入力を0-indexedに修正する。そのとき、問題設定がやや複雑なので気分的な確認に少し時間を使った。

これは連結成分内なら好きなように配置できる。ライブラリのグラフを使うか。んー、そこまでする必要はない。UnionFindか。使うの久しぶりだなあ。さて、これでもう解けたと思いきや、どうやって数えるかがパッと出てこない。Nは10^5なのでO(N^2)が通らない。連結成分毎にO(N)とかかけてると定数倍は小さくてもTLEの恐れがある。

まあちゃんと考えれば方針は立つ。UnionFindのrootの値でソートしてrootの値で区切り、位置と数をそれぞれ配列に入れてsort, set_intersectionすればいい。O(NlogN)の処理を分割してやっているので速いはず。ただ、区切るのが相当面倒。このへんライブラリ化できなかったかなあとか思ってた。

面倒なので他の方法も頭の中で考える。位置と数、どちらも0以上N未満、それを両方横1列に(幅Nで該当位置に)並べて、同じところにあったらカウントする。これは連結成分毎にやらずとも、まとめてできるのではないか?連結成分のrootをIDとして書き込む。重複はない。全部埋まる(だからvectorの初期化は考えなくていい)。サンプルは通ったが、ちょっと確信がなくて30秒くらいコードを読み直した。まあそのまま提出してAC

解説を読むと、そうか各位置についてその数を既定の場所へ持って行けるか見ればいいのね(と書くために10分以上考えた(まだ正直理解があやしい))。連結成分内なら好きな順列が作れる、というところまでは考えたが、それをこういう捉え方はできなかったなあ。

2018-05-11

yukicoder contest 190

3完。ADBの順にやった。難しかった。

No.682 Average

iの範囲が決まってるし数字も小さいので、ループで数えるだけ。計算量のオーダーを落とす方法が存在するので怖い見た目になってる(そのことは考えずに解いた)。

No.683 Two Operations No.3

色々いじってみるも全然解ける気配がない。逆からやるのも考えたが見えない。糸口もつかめないので他の問題へ。

Dから帰ってきて、もう時間があんまりない。とりあえず逆からDFSを投げてTLEしないことを祈ってみよう。実装して提出するとMLE!?DFSの深さがってことか。そういえば123 0みたいなケースは考えてたのに忘れてた。片方が0になったら終わるように修正して投げるとAC。これでTLEしないことをまだ証明できない。

No.684 Prefix Parenthesis

Bのあとの(終了までの)数分考えただけ。でかい山を作りたいのだと思ったが、一定以上の谷もあっちゃいけないしどうするんだろ。

No.685 Logical Operations

XORなのでこれをやった。まずAND<=ORなのはわかる。それどころかXOR<=ORも言える。等号がポイントか。両方1なビット位置があればいい。XORは最上位ビットが打ち消し合うとANDより小さくなるので、yの最上位ビットの位置のxは0だ。

つまりそういうのを数えればいい。いけそう。ああそうか、Nが半端な値だから面倒なんだ。Nが2冪なら、yの最上位ビットの位置で場合分けしていける。そうでないときも半端なぶんを下位から2冪個ずつ数えていけばいい。具体的には、両方1な位置が存在しない場合の数を全体から引く。それだけ。でも実装が全然できなかった。何から手をつけていいのか全くイメージが湧いてこない。コーナーケースのことを思うと頭がどん詰まりになる。脳がのっぺりする。何も感じない。起伏がなければコードは書けない。最終的にはACできてよかった。