ARC059 F バイナリハック

問題文

https://arc059.contest.atcoder.jp/tasks/arc059_d

 

sがどういう列なのかはどうでもよくて,sの長さだけが本質ということに気づけば終わり.というのも,例えば最終的に00,01,10,11が表示されるようなキーの押し方というのは全て等しい(偏りはない)はずだから.

よって dp[i][j]=i回キーを押して長さjの文字列が表示されるようなキーの押し方が何通りか というDPでdp[N][|s|]を求めて,2^|s|で割ればいい.

続きを読む

ARC078 E Awkward Response

問題文

https://beta.atcoder.jp/contests/arc078/tasks/arc078_c

 

Nを答えとする.「? n」と質問すると,Nとnを文字列として比較したときの大小と数値として比較したときの大小が同じならばYes,そうでなければNoが返ってくる.

Nのケタ数を決定する方法をかんがえてみる.例えば「? 10000」と質問すると,Nが10のべき乗でなければ,Nが5ケタ以上の整数ならばYes,そうでなければNoが返ってくるのでこれを利用してにぶたんが出来そう.

「? 1000000000」と質問すると,Nが10のべき乗のときYes,そうでないときNoが返ってくるので,これを用いてあらかじめNが10のべき乗の場合は弾いておく.

もしNが10のべき乗であることがわかったらあとは簡単なので略(コーナーケースに注意).

以下,Nは10のべき乗でないとする.

先にのべた方法でケタ数dを決定し,上のケタから順番に数字を決定していこう.

「? (これまでにわかっているケタ)M(全体がd+1ケタになるまで0を並べた列)」と質問すると,Yesが返ってきたらこのケタの数字はM未満,Noが返ってきたらこのケタの数字はM以上であることがわかり,これを利用してにぶたんが出来る.

ただし,例えばN=1230の3ケタ目を決定しようとして「? 12300」と質問すると,Yesが返ってきて3ケタ目は3未満ということになってしまう.そこで,Yesが返ってきたときは「? (これまでにわかっているケタ)M-1(全体がd+1ケタになるまで9を並べた列)」という質問もする.このときYesが返ってきたらNは(これまでにわかっているケタ)M(全体がdケタになるまで0を並べた列)という形になっていることがわかり,Noが返ってきたら本当にこのケタがM未満であることがわかる.

候補が10個あるときにぶたんに必要な質問は高々3回で,この全てがYesだとすると必要な質問は6回.これを9ケタでやると6×9=54回で,10のべき乗かどうか判定する質問と,ケタ数を決定するのに必要な質問を含めても60回程度で済むことがわかり,とけた.

続きを読む

ARC074 E RGB Sequence

問題文

https://beta.atcoder.jp/contests/arc074/tasks/arc074_c

 

すでに今いる場所より左のぬり方が決まっているとして,今いる場所に色cをぬれるかを判定するには,今いる場所に色cをぬったとき,違反する条件がないかチェックすればいい.つまり,l番目からr番目までにぬられている色がx種類という条件について,色cをぬったことによって色の種類がx種類をこえたらダメ.また,今いる場所がr番目のときは,ぬり終わった時点で色の種類がちょうどx種類になっていなくてもダメ.

という訳で,左のぬり方を状態とすればDP出来ることがわかったが,当然状態が多すぎるので上手く状態をまとめたい.

かんがえてみると,i番目に色cがぬれるか判定するには,i番目を含む区間についてその区間内の色の種類を数えられればいいのだから,ぬり方を全て覚えておく必要はなくて,各色がぬられているマスのうち最も近いものだけ覚えておけばいい.

また,3色のうち1色はかならず直前のマスにぬっているので結局(直前のマスにぬった色,他の2色をぬった最も近いマス)を状態とすればいいことになり状態数はO(N^2).

判定にO(M)かかるので全体の計算量はO(N^3M)となって間に合う.

800点自力ACが続いていていい.

続きを読む

ARC080 E Young Maids

問題

https://beta.atcoder.jp/contests/arc080/tasks/arc080_c

 

辞書順最小を作りたかったら出来るだけ小さいものを置いていく貪欲で上手くいくので,その方針でかんがえる.

あるペアを先頭に置ける条件をかんがえると,(偶数長の列)A(偶数長の列)B(偶数長の列)となっていればABを先頭に置けることがわかる.よってAは奇数番目の要素,BはAよりうしろにある偶数番目の要素でなければならない.

そこで奇数番目の要素の中の最小値をさがし,そのうしろにある偶数番目の要素の中の最小値をさがすことで先頭に来るペアを決定することが出来る(与えられる数列は1~Nの順列であるから同じ要素が2つ以上含まれることがないのが嬉しい).

この2つの要素を消すと,数列は高々3つの区間に分割され,区間内でペアを作るのは自由だが,区間をまたいでペアを作ることは出来ないという状況になる.

あとは各区間について同じことをやって次に置ける最小ペアを見つけては置くということを繰り返すだけなのだが,ここを高速化したい.

たくさん区間があるとき,次に置ける最小ペアを含んでいる区間をどう見つければよいのだろうか.それは簡単で,各区間内の奇数番目の要素の最小値をあらかじめ計算してタグをつけておき,そのタグが最小である区間を選んでくれば良い.これはプライオリティーキューで高速に実現できる.

あとはその区間内ではじめに説明したようにペアを作って区間を分割し,分割された各区間について新たにタグをつけてやればいい.奇数番目,偶数番目の要素の最小値を計算するパートは,RMQのセグメント木で出来る.結局,区間を選んでくる操作はN/2回行い,各区間についてO(logN)の操作を行うので全体の計算量はO(Nlog^2N)になって間に合う.

割とすんなり難しい問題が通せるようになってきていて嬉しい.

続きを読む

ARC084 E Finite Encyclopedia of Integer Sequences

問題文

https://beta.atcoder.jp/contests/arc084/tasks/arc084_c

 

Kが偶数のときは,先頭がK/2以下の数列と先頭がK/2より大きい数列が同数あるので,真ん中にあるのはK/2のうしろにKがN-1個並んだ数列だとわかる.

以下,Kは奇数とする.

真ん中にある数列が,K=5 N=3のとき{3,3,2},K=5 N=4のとき{3,3,3,1},K=5 N=5のとき{3,3 3,3,1}であることからわかるように,(K+1)/2=Mとすると,答えはM M M ... M 〇 〇 ... 〇という形になる.

まず,先頭が1,2,...,Kの数列が同数ずつあることから,明らかに答えの先頭はM.

そこで先頭がMの数列についてかんがえると,長さ1の数列が1つあり,長さ2以上の数列については2番目の数が1,2,...,Kの数列が同数ずつある.そこでこの中で真ん中にある数列がどこのグループに入るかかんがえると,Nが十分大きければやはり2番目の数がMのグループに入る.

ただし,長さ1の数列が前にあることで1つ順番がずれることに注意.

今,K=5で,先頭が1,2,...,5である数列がそれぞれ31個ずつあるとしよう.すると,この中で真ん中に来るのは先頭が3である数列の中で15番目にあるものになる(全体で156個の数列があるので真ん中は78番目,78=1+31+31+15より先頭が3である数列の中で15番目).31個の数列の真ん中は16番目であるから,長さ1の数列の分で求める数列が1つ前にずれている.一般に,先頭が1,2,...,Kである数列がそれぞれX個あるとき,Xが奇数なら求める数列は先頭がMの数列のうち真ん中より1つ前になる(偶数なら真ん中).

同様にかんがえて上のケタから決定していくと,すこしずつ真ん中からのずれが増えていく.ずれの量をYとすると,X/2>Yである間はMが並ぶが,ある所でX/2≦Yとなると数列にM以外が現れることになる.

しかし,ここで候補が十分すくなくなっていることを利用すると,真ん中からYだけ前にある数列を気合で求めることが出来て,答えが出る.

自力で800点問題がACできて良かった.アルゴリズム自体は比較的すぐ浮かんだが,ややこしくて細かい所を詰めるのに時間がかかった.

想定解は,MがN個並んだ数列より前にある数列が,後ろにある数列よりN-1個多いので,MがN個並んだ数列の(N-1)/2個前を答えるというものだった.たしかにずっと楽ですごい.

続きを読む

ARC094 E Tozan and Gezan

問題文

https://beta.atcoder.jp/contests/arc094/tasks/arc094_c

 

はじめからAとBが等しいときは0が答えとなるので,そうでないときをかんがえる.

このとき,とざん君がA[i]>B[i]となるようなiを1つ選び,i番目以外の要素から1減らすことにすると,i番目以外の要素が全て0になるまでこの操作を続けられることがわかる(お互いに1減らすことしかできないのでげざん君がどう操作してもA[i]>B[i]のままだから).

このあと,とざん君はA[i]から1減らし続けるしかなく,やがてA[i]=B[i]となって終了する.

結局,高橋くんが食べる飴は(A[i]の合計)-(A[i]>B[i]を満たすiについてのB[i]のmin)個になる.

これが最適であることの証明はここにある.

知識は不要で,それぞれの立場での良さげな戦略をかんがえてみるとわかるという問題だった.

続きを読む

ARC095 E Symmetric Grid

問題文

https://beta.atcoder.jp/contests/arc095/tasks/arc095_c

 

まず点対称なグリッドを図示してみると,i番目の行とH-i+1番目の行は反転の関係になっていることがわかる.(Hが奇数の場合,真ん中の行は左右対称になっている).

そこで,列の入れ替え方法を適当に固定したとき,行を入れ替えて点対称に出来るかどうかは,反転の関係になっている行がH/2ペアあるかどうかで判定できることがわかる(Hが奇数のとき,余った行が左右対称かも見る).

問題は列の入れ替え方法が最大12!通りもあって間に合わないことだが,実は本質的に同じ入れ替えがたくさんあるので全て試す必要はない.

例えば2つの文字列abcdeとedcbaがあるとする.このとき対称の位置にある2番目と4番目の文字を入れ替えるとadcbeとebcdaになり,1番目,5番目の文字と2番目,4番目の文字を入れ替えるとbacedとdecabになって,どちらも反転の関係を保っている.

このことから,どの列をペアにする(対称の位置に置く)かだけが本質だとわかって,出来る.

わかってもすっきり書くの難しくない...?

続きを読む