狠狠撸

狠狠撸Share a Scribd company logo

Square869120 contest #2

?
?
A
AtCoder Inc.

Square869120 contest #2の解説です。

1 of 165
Downloaded 14 times
IOI列車で行こう 2 Take the IOI Train 2 解説
問題概要 ? I, Oからなる文字列 S が与えられる。 ? 文字列 S の部分列のうち, 「IOIOI, IOIOIOIOIOIOIOIのような文字列」 の最大の長さを求めなさい。 ? 1 ≦ |S| ≦ 10,000
部分点解法 ? 先ほど説明した, 「IOIOIのような文字列」 は, I, IOI, IOIOI, IOIOIOI, IOIOIOIOI,... のようになる。 ? そのような文字列をすべて判定することで, できるのではないか?
部分点解法 ? S が T の部分列であるか判定する 1. ptr = 1 とする 2. Tの1文字目から|T|文字目まで: 3. S の ptr 文字目が今指しているTの文字と等しければ ptr を1加算する 4. ptr=|S|であれば部分列である ? その方法を使って, で判定できる ? 全体の計算量は
満点解法 ? 部分点解法の方法では, |S|=10000 のときにTime Limit Exceededする場 合がある ? もっと高速化する方法はないか?
満点解法 ? 実は, I, IOI, IOIOI, IOIOIOI,...と調べていく必要はない ? IOIOIOIOI,...IOIOIOIOI のような長さ |S| 以上の文字列 T を用意し, 4ページ 目の部分列であるか判定するアルゴリズムの最終的な ptr を利用することがで きる ? ptr が 1 ? 列車が編成できない ? ptr が偶数 ? 長さ ptr-1 の列車が編成できる ? ptr が奇数 ? 長さ ptr-2 の列車が編成できる ? 全体の計算量は なのでAcceptedします
結果 / Result ? IOI に行っている人やIOI代表選手を決める選考会に参加している人な らば簡単に解けると思います ? A問題の解説を書いた人は上の条件に該当しないので解くのに10分くら いかかりました ? IOI列車に乗ってIOIに行きたいけどあと3000問は解かなければあまり現 実的ではないと思いました
結果 / Result ? First Acceptance… sigma425 (2分1秒) ? 得点分布
B問題 Division 2
問題概要 ? 1以上n以下の整数を書き、それに対して以下の操作をq回行う。 ? 書かれている全ての数に対して、a[i]で割り切れるのであればその 数をa[i]で割った数に書き換える。ただし、a[i]はi回目の操作におけ る割る数である。 ? 最終的に1が何個書かれているか、求めてください。 ? ただし、aの入力はa[1]からはじまりa[q]で終わるものとして考えます。
問題概要 ? 小課題1(25点)?1≦n≦1000000,1≦q≦24 ? 小課題2(75点)?1≦n≦10^13,1≦q≦24 ? どちらの小課題でも3≦a[i]≦50である。 ? うさぎは2で割るのが嫌いなため、a[i]=2ではない。
例 ? 例えば、n=10,q=3,a={3,4,6}のとき、 ? 最終的な1は{1,3,4}からの3つになります。 割る数 1 2 3 4 5 6 7 8 9 10 3 1 2 1 4 5 2 7 8 3 10 4 1 2 1 1 5 2 7 2 3 10 6 1 2 1 1 5 2 7 2 3 10
部分点解法(25点) ? 愚直に計算をします。 ? 配列を使ってx[i]=iにまず初期化します。x[i]というのは、i番目 の数は今現在何なのかということを表します。 ? q回の操作を以下のように行います。 ? x[1]からx[n]まで順番に見ていきます。その数字がa[i ](i回目の 操作の場合)で割り切れたらその数字を1回だけa[i]で割ります。
部分点解法(25点) ? コードでは、if(x[j]%a[i]==0){x[j]/=a[i]}ということです。 ? 4ページ目の表のように操作することをイメージすればわかりやすいで しょう。 ? 計算量は、各クエリにつきO(n),クエリがq個あるのでO(nq)となります。 n=1000000,q=24の場合2400万回となり、間に合います。 ? しかし、小課題2ではn=10^13,q=24が最大だから、計算量は10^14回を超 えてしまいます。?TLEをします。
考察1 ? Q≦24であることを利用できないか? ? 割れるなら「割る」、割れないなら「割らない」なので、Π(a[i]また は1)※Πはi=1からQまでの範囲で、しか可能性がないので は？ ? 例えば、a[i]={3,4,6}のとき、以下の8通りしか可能性はない。 1*1*1=1,1*1*6=6,1*4*1=4,1*4*6=24, ? 3*1*1=3,3*1*6=18,3*4*1=24,3*4*6=72
考察1 ? a[i]をいくつか選んだときの積であれば、その「選んだ場所」だ け割り、それ以外の場所では割らないことになる。 ? そうでない場合、どこで割っても1にならない。 ? なぜなら、割るときは必ずa[i]以外で割ってはいけないからで ある。また、a[i]を選んだ時の積の分だけ割れるので、それが ある数Cと一致している場合のみC/積=1になるからである。 ? ?考察は正しい
満点解法 ? 考察より、2^q通りしか可能性はないことが分かった。 ? ?これを全列挙できる!! ? まず、a[i]で割るか割らないかを0か1かで表される配列bのi番 目の要素に記録しておく。 ? h=0から2^q-1のときまでループし、そのときのb[i]は ? b[i]={h/(2^(i-1))}%2となる。
満点解法 ? そして、最初sum=1として、b[i]が1のときsumにa[i]をかけます。 (1≦i≦q) ? sumで最後1になるか試して、なれば答えに1を足します。 ? そのようにすれば、どのa[i]を選ぶかを全通り、重なりがなく調 べることができる。JOI2007-08予選5:Osenbeiなどが解法として は似ている。
満点解法 ? 通り数が2^q通り、1つの数字から始めると1になるかを調べるクエリ がO(q)だから、計算量はO(q*2^q)となる。 ? q=24のとき、約400,000,000回の計算が必要となる。 ? 制限時間が5secだから、定数倍が速いか普通だと、C++などの実 行速度の速い言語ではギリギリ通ります。 ? ちなみに、この解法での私のコードの実行時間は2354msでした。 ? しかし、定数倍が遅かったり、JAVAなどのやや実行速度の遅い言 語だと通らない。
考察2 ? 完全な全列挙ではなく、後ろから考えて工夫して全探索できる のではないか？ ? ?Queueを使おう！ ? Queueについては、 ? http://www.cc.kyoto-su.ac.jp/~yamada/ap/queue.html ? を参照してください。
満点解法2 ? まず、最初に2つの引数を持つQueueを用意し、第1引数を現時点 での数、第2引数を「何個目のクエリまで終わったか」とします。 ? そして、Queueに(0,q)を入れます。その後、以下のループをQueue の大きさが0になるまで続けます。 ? Queueの先頭の第1引数をc1,第2引数をc2とします。 ? c2=0となった時点で「全ての処理が終わっている」ので、ループか ら抜けます。 ? そのあと、Queueをポップします。
満点解法2 ? 割ってc1になる場合 ? c1*a[c2]がqを超えない場合、可能です。(その場合、Queueに (c1*a[c2],c1-1)をプッシュします。 ? c1*a[c2]は当然a[c2]で割り切れるので、前から考えると …→a[c2]*c1→c1→…となります。 ? 割らずにc1になる場合 ? ｃ1がa[c2]で割り切れるとc1→c1/a[c2]に自動的になってしまうので、不 可能です。それ以外の場合、Queueに(c1,c2-1 )をプッシュします。
満点解法2 ? 例えば、a={3,4,6},n=20,q=3のとき、Queueは次のように変化します。 ? {(1,3)}? ? {(6,2),(1,2)}? ? {(24,1),(6,1),(4,1),(1,1)}? ? {(18,0),(6,0),(12,0),(4,0),(3,0),(1,0)}となります。 ? よって、最終的に残っているのは5通りとなります。枝刈りをしているので、数の 重なりはないです。?答えはループから抜けたときのQueueのサイズとなります。 ? グレーの部分は枝刈りされたものを示しています。
満点解法2 ? 状態数は最大で2^(q+1)通り、各状態につきO(1)かかるので、 計算量は最大でO(2^(q+1))となります。 ? q=24のとき、最大約3000万回の計算が必要ですが、満点解法 1よりは明らかに速いです。 ? 私が書いたコードだと、35msで通りました。 ? JOIでいう難易度5(満点解法2は6)くらいだと思います。
結果 ? FirstAcceptance:sigma425(8分06秒) ? 得点分布
おしまい
C問題 何通りの分割方法がある？
問題概要 ? 整数nが与えられる。 ? nを文字列に変換したものをSとする。 ? Sをいくつかの部分に分割する。 ? それを全て数字に変換するとき、和がD以内でなければならな い。ただし、各数字は0から始まってもよい。 ? 何通りの分割方法があるか、求めてください。
問題概要 ? 小課題1(10点) ? 通り数は1通り以下である。 ? 小課題2(30点) ? n≦10,000,000,000を満たす。 ? 小課題3(60点) ? N≦10^100を満たす。
例 ? 例えば、n=1355,D=50のとき、 ? {1,3,5,5}:1+3+5+5=13 ? {13,5,5}:13+5+5=23 ? {1,35,5}:1+35+5=41 ? の3通りの分け方が存在する。 ? 答えは、1,000,000,007で割った余りで求めなければならない。
注意事項 ? 小課題3では、n≦10^100と非常に大きいので、C++などでは 整数nを文字列として受け取らなければならない。 ? JAVAやC#などでも、BigIntegerという巨大な整数を用いる型を 利用しなければならない。 ? 64ビット型整数に収まる整数は最大约9*10镑18である。
小課題1(10点) ? 小課題1では、通り数は0か1しかありません。 ? 「通り数が1の場合」は、どれか1つの方法が存在するということです。 ? 一番和が少なくてできる方法は、1桁ごとに分割するという方法です。 ? なぜなら、最初すべて1桁ごとで、ある2つの隣り合った数字を合成 すると、10の位がa,1の位をbとすると、10a-a=9aだけ和が増えてしま います。
小課題1(10点) ? ?よって、「各位の数字の和」が考えられる各数字の総和として最 小となります。 ? 答えは0か1なので、「各位の数字の和」がD以下ならば「1」、Dを超 えていたら「0」となります。 ? 各位の数字の和を求める方法は、整数をまず文字列に変換し、最 初の文字から順番に見ていきます。 ? I文字目が「1」であれば1,「 2」であれば2…をsumに加算します。最 終的なsumの値が各位の数字の和となります。
小課題2(40点) ? 小課題1の方法では、答えが2通り以上の場合には対応できま せん。なぜなら、1桁ずつ分割する方法でできる場合、少し2桁 以上の数字を入れても条件を満たす場合があるからです。 ? 小課題2(30点)はn≦10^10までです。 ? ?これを利用できないか? ? できます。
小課題2(40点) ? nはせいぜい10桁です。 ? 切る場所(=桁と桁の間で分けるか)はTrueかFalseの2通りなので、 2^|n|でできます。 ? 実際桁と桁の間は|n|-1個しかないので、2^|n|-1通りを調べ上げる 必要があります。 ? 例えば、n=1355,場所={1,0,1}(1=True,0=False)のとき、1番上の位を 0桁目とするとき、0桁目と1桁目で分け、2桁目と3桁目で分けること になります。?{1,35,5}の3数に分割されます。
小課題2(40点) ? i=0から2^(|n|-1)まで以下のような操作を繰り返しますが、i桁 目とi+1桁目の間を分けるかどうかを表す変数をb[j]とします。 ? b[j]={i/(2^j)}%2(0≦j≦|n|-2)となります。 ? 配列bの数値が分かれば、どのようにnが分割されているかもわ かります。 ? それが分かれば、分割されている各数字の総和を求めてそれ がD以下であれば答えに1を加算します。
小課題2(40点) ? 例えば、D=50,n=1355で{1,35,5}と分割された場合その総和は41だから答えに1 を加算します。 ? 計算量は調べ上げる通り数が2^((nの桁数)-1)通り、1つの分割状態につき ? O(nの桁数)かかるので、計算量はO((nの桁数)*2^((nの桁数)-1))となります。 ? ここまででは、AOJ1237:Shredding Companyという問題によく似ています。 ? n=9,999,999,999のとき、計算量は約5000回となります。 ? しかし、n=10^100のとき、計算量は約10^32回となり、明らかにTLEします。
考察1 ? D≦100,000であることを利用できないか? ? 1桁目から順に通り数を見ていきDPで解けないか? ? どこまで見終わったか、今までの和、通り数と3つの要素が分 かればできるのではないか? ??DP(動的計画法)
満点解法 ? 考察でも示しましたが、「どこまで見たか」「今までの和」「通り数」の3つの 要素が必要です。 ? １つ目は|n|以下、2つ目はD以下、3つ目は10億7以下なのでdp[どこまで 見たか][今までの和]として通り数mod 1,000,000,007を格納するのが最適 です。 ? メモリはint型10,000,000個だから足ります。 ? まず、dp[0][0]=1とします。 ? そして、次のページの操作をrep(i,1 ～n),rep(j,0 ～D)として繰り返します。
満点解法 ? dp[i][j]の値を更新するとき、(最初にsum=0に初期化します。) ? まず、t=0とします。ループのたびにtに1を足します。 ? 10^t*(i-t桁目の値)をsumに足します。 ? sumがDを超えるかi-tが0未満になるとループから抜けます。 ? dp[i][j]にdp[i-t][i-sum]を足します。これは、i-t桁目までを分割した時 の和がi-sumで、そのあと、t桁分分割せずに数字を「今までの総和」 に足し、そこで(i-1桁目とi桁目の間で)分割するを意味します。
満点解法 ? そこで、１点注意事項があります。 ? 0がいくつか続いた後に1がくると、一度に10^20とかいう巨大な数 が足されてしまう可能性があるので、i-t桁目が1以上でかつt≧7の ときループから抜けるようにする必要があります。(オーバーフロー には注意すること。) ? 結果は、Σdp[n][i](0≦i≦D)となります。 ? n-1桁目(最後の桁)まで見終わるということは「全ての桁を見終わっ た」=「それ以上足されない」ことを意味します。
満点解法 ? 最後に1,000,000,007で割るのを忘れないようにしましょう。 ? 計算量は、ループにO((nの桁数)D),一度にO(Dの桁数)くらいかかるので、計算 量はO((nの桁数)*D*(Dの桁数))と見積もれますが、0が続くケースの場合、 ? 最大でO((nの桁数)^2*D)となります。定数が1/2くらいつくので制限時間5secな ら間に合います。 ? 工夫してdp[i][j]が1以上のときdp[i+t][j+sum]に足す方法でやれば、0が続く場合 でも対処できます。 ? この場合、sumはi桁目からi+t桁目までの数字列を1つの数字として表したときの 値となります。
満点解法 ? 想定解は約500msです。 ? 工夫してdp[i+t][j+sum]の形でやった場合です。 ? ちなみに、小課題1は難易度2,小課題2は難易度5,小課題3は 難易度6～7くらいだと思います。 ? コンテストお疲れさまでした。
結果 ? First Acceptance:piroz95(24分43秒) ? 得点分布
おしまい
D問題 2016
問題概要 ? 整数nが与えられます。 ? n以下の数字の中で約数の個数がが最大となる数の約数の個 数と、この約数の個数を持つ数の中で最小の整数を求めなさ い。 ? ただし、最初にクエリの数Qが与えられて、Q回だけ整数nが質 問されることになります。
問題概要 ? 1≦q≦10,000を満たす。 ? 小課題1(8点)…1≦n≦10,000を満たす。 ? 小課題2(34点)…1≦n≦1,000,000,000を満たす。 ? 小課題3(58点)…1≦n≦10^17を満たす。 ? 小課題3では特に、オーバーフローに注意すること。
例 ? 例えば、n=100の場合、 ? 最大の約数は12個あります。 ? 約数が12個の、100以下の整数は、60,72,84,90, 96があります が、60の方が小さいので60の方を出力します。 ? 答えは、12と60を空白区切りで出力することになります。(この 場合)
例 ? ちなみに、 約数が最大となる整数は、 以下のように続きます。(高度合成数) 整数 約数個数 整数 約数個数 整数 約数個数 1 1 48 10 840 32 2 2 60 12 1260 36 4 3 120 16 1680 40 6 4 180 18 2520 48 12 6 240 20 5040 60 24 8 360 24 7560 64 36 9 720 30 10080 72
小課題1(8点) ? 自明な探索解で解けます。 ? n≦10,000と非常に少ないため、クエリごとに処理する必要はありま せん。 ? 最初にn=1,2,3,4…10000のとき約数が何個になるのかを記録した配 列をaとすると、 ? a[i]=max(a[i-1],a[i])とします。 ? そうすると、nが与えられたとき答えはO(1)で求めることができます。 答えはa[n]です。
小課題1(8点) ? 1つの数字の約数の個数を求めるのにO(n)、かつn個の数字に対してこ れを求める必要があるので、計算量はO(n^2)となります。 ? 小課題1でのnの最大は10,000なので、計算量は約1億回です。?時間 制限3secであれば間に合います。 ? ちなみに、aは下表のようになります。 整数n 1 2 3 4 5 6 7 8 9 10 11 12 13 もとのa[i] 1 2 1 3 2 4 2 4 3 4 2 6 2 答えのa[i] 1 2 2 3 3 4 4 4 4 4 4 6 6
考察1 ? n≦1,000,000,000であれば、小課題1の解法であれば明らかに TLEしてしまいます。 ? また、配列をを1,000,000,000個も置くと、MLEしてしまうので、ク エリごとに処理する必要があります。 ? Q≦1,000なので、1クエリにつき可能な計算量は最大で約 300,000回です。
考察1 ? ?約数を全て調べるひまがありません。 ? ?問題は「約数を最大化しろ」なのでDFSでできるのでは？ ? 素数を列挙し、掛けていきnを超えるまでつづけるのがいいの では？ ? 図は次のページを参照してください。
考察1 素因数の 個数を {2,3,5,7} で表した ものです 。(n=30のとき) {0,0,0,0}=1? {1,0,0,0}=2 ? {2,0,0,0}=4? {3,0,0,0}=8 ? {4,0,0,0}=16? (これ以降は矢 印は省略) {5,0,0,0}=32 {4,0,0,0}=16 {4,1,0,0}=48 {4,0,0,0}=16 {4,0,1,0}=80 {4,0,0,0}=16 {4,0,0,1}=112 {4,0,0,0}=16 {3,0,0,0}=8 {3,1,0,0}=24 {3,2,0,0}=72 {3,1,0,0}=24 {3,1,1,0}=120 {3,1,0,0}=24 {3,1,0,1}=168 {3,1,0,0}=24 {3,0,0,0}=8 {3,0,1,0}=40 {3,0,0,0}=8 {3,0,0,1}=56 {3,0,0,0}=8 {2,0,0,0}=4 {2,1,0,0}=12 {2,2,0,0}=36 のように 続きます。
小課題1(8点)解法2 ? このようにDFSでも解けます。 ? 方法としては、 ? 素数を{2,3,5,7,11,13…sqrt(n)}くらいまで列挙し、 ? nを超えるまで掛け続ける。 ? nを超えたら1手前に戻る。 ? それでもすべての場合でダメな場合さらに1手前に戻る。 ? 約数が最大のときの整数をmin,maxなどを使い求められる。 ? 1ページ前を参考にすること。
小課題1(8点)解法2 ? その場合、計算量的にはn≦10,000では間に合います。 ? それに少し工夫を加えれば、小課題2が通ります。 ? ※注意事項 ? DFSは、スタックや再帰を使えば実装できます。
考察2 ? 全探索する必要ないのでは? ? そもそも素因数3が0で5が1よりも3を1にした方が数が小さくなり かつ約数の個数も変わらないのでこちらの方が得なのでは? ? ?一度素因数0の場所が現れたらそれ以降は0なのでは? ? ×{3,0,1,0,1…},〇{3,1,1,0,0…}
小課題2(42点) ? 考察2より、次のように全探索することができます。 ? 素数を{2,3,5,7,11,13…47}まで列挙します。 ? ただし、2*3*5*7*11*13*…*47≒6.14*10^17だから、47までしか 必要がないです。 ? 考察1のようにDFSをしますが、個数0からではなく1から探索す るようにします。
小課題2(42点) ? 状態遷移は下のようになります。 状態遷移 {2,3,5}= (数,約数) ?は省略 します。 n=30 {0,0,0}=(1,1) {1,0,0}=(2,2) {2,0,0}=(4,3) {3,0,0}=(8,4) {4,0,0}=(16,5) {5,0,0}=(32,6) {4,0,0}=(16,6) {4,1,0}=(48,10) {4,0,0}=(16,6) {3,0,0}=(8,4) {3,1,0}=(24,8) {3,2,0}=(72,12) {3,1,0}=(24,8) {3,1,1}=(120,16) {3,1,0}=(24,8) {3,0,0}=(8,4) {2,0,0}=(4,3) {2,1,0}=(12,6) {2,2,0}=(36,9) {2,1,0}=(12,6) {2,1,1}=(60,12) {2,1,0}=(12,6) {2,0,0}=(4,3) {1,0,0}=(2,2) {1,1,0}=(6,4) {1,2,0}=(18,6) {1,3,0}=(54,8) {1,2,0}=(18,6) {1,2,1}=(90,12) {1,2,0}=(18,6) {1,1,0}=(6,4) {1,1,1}=(30,8) {1,1,2}=(150,12) {1,1,1}=(30,8) {1,1,0}=(6,4) {1,0,0}=(2,2)
小課題2(42点) ? 計算量的にはそれで小課題2には通ります。 ? しかし、小課題3では現実的な時間にはなりますが、TLEをして しまいます。 ? そこで、さらに考察をする必要があります。
考察3 ? 小課題3では、今までの方法だとTLEします。 ? 想定時間は約11secくらいです。 ? よく見てみると、{2,3,5}={1,2,0}のようになっている場合があります。 ? これを{2,1,0}にスライドした方が数は少なくなり、約数は同じなので こちらの方が効率的 ? ?{2,3,5,…}を昇順にソートさせたとき一番効率的
考察3 ? つまり、a(2)≧a(3)≧a(5)≧a(7)≧…となるようにプログラムを組 めばよいと考えられます。 ? ちなみに、a(n)とは、素数nで何回割れるかということです。 ? このようにすれば、さらに时间が短くなります。
満点解法 ? 考察3を利用します。 ? 再帰またはDFSの、「何回掛けるか」の範囲を ? 1から「前の掛けた回数(1つ前の素数を何回掛けたか)」までにします。 ? また、1回nを超えてしまったら、その次の素因数以降探索せずにもう1回 戻るという方法も使えます。(つまり合計2回もどるということ) ? 例えば、n=30のとき、次ページのようになります。 ? {2,3,5}=(整数,約数)の形で表します。
満点解法 ? 以下のようになります。 {0,0,0}=(1,1) {1,0,0}=(2,2) {2,0,0}=(4,3) {3,0,0}=(8,4) {4,0,0}=(16,5) {5,0,0}=(32,6) {4,0,0}=(16,5) {3,0,0}=(8,4) {3,1,0}=(24,8) {3,2,0}=(72,12) {3,1,0}=(24,8) {3,0,0}=(8,4) {2,0,0}=(4,3) {2,1,0}=(12,6) {2,2,0}=(36,9) {2,1,0}=(12,6) {2,0,0}=(4,3) {1,0,0}=(2,2) {1,1,0}=(6,4) {1,1,1}=(30,8) {1,1,0}=(6,4) {1,0,0}=(2,2) {0,0,0}=(1,1) これだけです。 緑字は2回戻り の途中を表し ます。
満点解法 ? このように、工夫をして計算量を減らすことができます。 ? この場合、問題で問われているのは「約数の最大化」なので、 全てを調べ上げる必要はありません。 ? このようなアルゴリズムを「ヒューリスティック探索」ともいいます。 ? 想定解は約400msです。
参考問題 ? JOI 2009-10予選6 「方向音痴のトナカイ」 ? AOJ 0190 「11パズル」 ? AOJ ALDS1_13_C 「15パズル」 ? AOJ 1128 「square carpets」
結果 ? First Acceptance:nuip(14分47秒) ? 得点分布
おしまい
E問題 部分文字列 / Substrings 解説
問題概要 ? 文字列 S が与えられる。 S の部分文字列の合計の文字数を求めなさい。 ただし, 重複するものは 1 通りだけをカウントする。 ? 制約 ? 1 ≦ |S| ≦ 100,000
問題概要 ? S = "abc" のとき ? "a", "b", "c", "ab", "bc", "abc" の 6 個がある。合計は 10文字であ る。 よって, 答えは 10となる。 ? S = "aaqqz" のとき ? "a", "q", "z", "aa", "aq", "qq", "qz", "aaq", "aqq", "qqz", "aaqq", "aqqz", "aaqqz" の 13個があり, 合計で32文字である。
部分点解法 (15点) ? 部分文字列を全部探索し, 重複しているものを 1 回しかカウントしない。 ? 部分文字列は合計で O(|S|^3) 文字あるので, これをソートすると全体の 計算量は O(|S|^3 log |S|) かかる。 ? こんなに簡単に 12点が取れます。
部分点解法 (50点) ? 部分文字列は合計で O(|S|^2) 個しかないので, 文字列を数値に変換す ればソートに O(|S|^2 log|S|) しかかからない。 ? そのようなアルゴリズムをハッシュという。(確率的だが, 99.9%くらい正確と 思っといたほうがいい) ? 長さ k の文字列の場合, の v の値をハッシュ値とする。unsigned long long型で mod 2^64 を取るのが一 般的。 ? 全体の計算量は O(|S|^ 3)
部分点解法 (50点) ? Rolling-Hash という方法で S の部分文字列のうち長さ N のもののハッ シュ値を O(|S|) で求めることができる。 ? 分からない方は蟻本やインターネットのページを参考にしてください。 ? 全体の計算量は O(|S|^2 log |S|)
Suffix Array, LCPについて ? Suffix Arrayとは? ? Suffix Arrayとは, 文字列 S の接尾辞をソートしたものである。接尾辞配 列 A[i] は (Sの文字数) - (ソートした時の i 番目の接尾辞の文字数) で ある。 ? 詳しくは蟻本やインターネットを参照。 ? これは で求められる。
Suffix Array, LCPとは? ? たとえば, S = "E869120" のとき, ? 接尾辞配列は右のようになる。 ? それを使って, LCPというものを ? O(|S|) で求められるようになる。 ? LCPについては次ページで。 i Suffix A[i] 0 (空文字列) 7 1 0 6 2 120 4 3 20 5 4 69120 2 5 869120 1 6 9120 3 7 E869120 0
Suffix Array, LCPとは? ? Suffixをソートした時の i 番目の文字列をSuffix[i] とする。 ? LCP[i] = (Suffix[i-1] と Suffix[i] の最初の何文字が同じか) ? LCPについても蟻本やインターネットに載っているので参考にしてくださ い。
満点解法 ? S = "AAQQZ" のとき i Suffix LCP 重複している文字列 重複していない文字列 1 AAQQZ 0 0個 A,AA, AAQ, AAQQ, AAQQZ 2 AQQZ 1 1個 (A) AQ, AQQ, AQQZ 3 QQZ 0 0個 Q, QQ, QQZ 4 QZ 1 1個 (Q) QZ 5 Z 0 0個 Z
満点解法 ? S = "AAQQZ" のとき ? 同じになっている! i Suffix LCP 重複している文字列 重複していない文字列 1 AAQQZ 0 0個 A,AA, AAQ, AAQQ, AAQQZ 2 AQQZ 1 1個 (A) AQ, AQQ, AQQZ 3 QQZ 0 0個 Q, QQ, QQZ 4 QZ 1 1個 (Q) QZ 5 Z 0 0個 Z
満点解法 ? それを利用して通すことができる ? 計算量は O(| S| log^2 |S|) なので間に合う
結果 ? First Acceptance … climpet(6分51秒) ? 得点分布
Range Sum Queries 解説
問題概要 ? 長さ a の数列 が に初期化されて いる。 ? 次の操作を c 回行う。 ? とする。 ? 最終的な の値を mod 1,000,000,007 で求めなさい。
問題概要 ? 制約 ? 1 ≦ a ≦ 100,000 ? 1 ≦ b ≦ 1,000,000,000 ? 1 ≦ c ≦ 1,000,000,000
問題概要 ? の時 ? よって, 求める答えは58となります。 ? 58って, 素晴らしい数ですね。 (rng_58, sky58のようなプロも使っている) d[0] d[1] d[2] d[3] 最初 1 3 9 27 1回目終了後 1 4 13 40 2回目終了後 1 5 18 58
0点解法 ? 問題文の通りそのままやる ? 1回の操作につき かかる ? 全体の計算量は ? a, b,c が 1,000であることを考えるとTime Limit Exceededしてしまう。
部分点解法(12点) ? もっと高速化する方法はないか? ? 実は, d[i] を求める時にd[i-1] の値を利用できる ? (右辺は current ) ? ? ? 計算量は O(ac)なので小課題1には通る
部分点解法(12点) の補足 ? DP(Dynamic Programming ) でも解けます ? JOI2006-2007 予選 6問目 「通学経路」 のように DPしていくとできます ? 漸化式は dp[i][j] = dp[i-1][j]+dp[i][j-1] のような感じですね ? この方法でも12点は取れます。
考察1 ? でも, この問題には JOIの 「通学経路」 のように障害物はありません ? AtCoder Beginner Contest 034 C問題 「経路」 のような場合です ? 「経路」 という問題は, 組み合わせ (nCr) を用いた解法で101点取れます ? そこで, H×W の経路の総数について考えてみましょう
考察1 ? 縦に進む時をX, 横に進む時をYとする。 ? そのとき, XがH個, YがW個 あります。 ? 経路の総数は, H+W個のなかからH個を選ぶので 通りとなります。
考察1 ? 次に, を O(n) で求める方法を紹介します。 ? フェルマーの小定理を用いて ということが分 かります。その解を 「a の逆元 (mod inverse)」 といいます。 ? なので, n! を O(n) で求めて逆元をO(log n) で求めれば結 果として計算量は O(n) となります。
考察1 ? この問題にも nCr を使うことができます。 ? 9 という数字について考えると, 1×1の場合と同じ2通りの経路があり, 最終的な 答えに9×2=18 を足していることが分かります。 d[0] d[1] d[2] d[3] 最初 1 3 9 27 1回目終了後 1 4 13 40 2回目終了後 1 5 18 58
部分点解法(60点) ? 最初に説明した例の場合, 答えは であり, 58 となります。 ? しかし, そのままでは nCr を求めるのにO(n) かかってしまいます。 ? k! を 1 から n までメモ化することによってO(log n) で済みます。 ? よって, 全体的な計算量は mod p のとき 約 O(c + a log p) となります。 小課題2には通ります。
満点解法 ? n が大きい場合の nCr をどのように求めるか? ? を使えばO(r) で求められます ? では, どのようにして を求めるのか? ? 上の方法を利用すれば で求められる。 ? もっと高速化する方法はないか?
満点解法 ? であるから, その関係について 調べてみると,...
満点解法 ? それを順番に求めていくと, O(a log p) ですべて求められます。 ? よって, O(a log p) でこの問題を解くことができます。 ? この問題は少し数学的な知識が必要かもしれませんが, 蟻本に載ってい る程度なので解けなかった人はマスターしましょう。
nCr を利用する問題 ? 以下, 私がお勧めする nCr を用いる問題です。 ? ProjectEuler 015「Lattice Paths」 ? AtCoder Beginner Contest 034 C問題 「経路」 ? AtCoder Beginner Contest 022 D問題 「多重ループ」 ? AOJ 2335 「10歳の動的計画」 ? AOJ 2445「Minimum Cost Path」
結果 ? First Acceptance… snuke(25分10秒) ? 得点分布
G問題 道とN個のAtcoder社
問題概要 ? N個のAtcoder運送会社の工場が存在する。 ? その座標は(xi,yi)である。(入力される。) ? 工場と工場を結ぶ道をできるだけ建設したいが、工場以外で 道と道は交差してはならない。 ? 最大で何個の道を建設できるか求めなさい。
問題概要 ? 小課題1(14点)…1≦n≦4を満たす。 ? 小課題2(50点)…1≦n≦100を満たす。 ? 小課題3(36点)…1≦n≦2,000を満たす。 ? どの小課題でも、3工場は一直線上に並ばない。 ? また、0≦xi,yi≦1,000,000,000である。
例 ? n=4,座標={(0,0),(1,1),(0,1),(1,0)}のとき、 ? 最大で5本の道を建設できる。
小課題1(14点)解法1 ? 自明な探索解です。 ? n≦4のとき、線は最大で6本しか引くことができません。 ? よって、どことどこが結ばれているか、2^6通りを列挙する方法でで きます。 ? 結ばれている線に交差がない場合、 ? maxn=max(線の本数,maxn)とします。 ? 答えは、maxnの値になります。
小課題1(14点)解法2 ? 貪欲でも解けます。 ? まず、n=1のとき、道は0個建てられます。 ? 次に、n=2のとき、道は1個建てられます。 ? 次に、n=3のとき、3工場が三角形の形になるため、道は3個建てら れます。 ? 次に、n=4のとき、道が5個建てられる場合、6個建てられる場合の2 通りに分かれます。
小課題1(14点)解法2 ? ある3点を選んで、残りの1つの点が3つの点からできる三角形 に囲まれる場合、道は6個建てられます。 ? どのように3点を選んでも囲まれない場合、道は5個しか建てら れません。 ? 次のページの図を参照してください。
小課題1(14点)解法2 ? 道が6本のとき/道が5本のとき(実際は工場は点として考える)
考察1 ? 小課題2は、1≦n≦100です。 ? 小課題1と比べて、nが一気に大きくなるので、到底全探索だと間に 合いません。 ? 多項式時間で求めるとしても、O(n^4)程度またはそれ以下で求める 必要があります。 ? ?解法としてはGreedyが考えられます。 ? 辺の本数の最大を求めるのでDPではできにくいです。
考察1 ? 三角形を作ります。 ? 道をn*(n+1)/2通り列挙し、その時点で道が引けるならば道を 建て、引けないならば道を建てません。 ? 証明としては、三角形の辺をつながるところにどのように移動し たとしても、四角形を作ることはできないからです。 ? ?道の数は四角形をなくし、三角形だけにしたときに最大
考察1の図 ? 四角形がある図/三角形しかない図
考察1の図 ? 辺の移動?新しく四角形は現れない
小課題2(64点) ? 考察1のようにやればよい ? ?{a,b}を結ぶ道は条件を満たすか(交点がないか)を求めるクエリとする ? {a,b}=0のとき結べない、1のとき結べるとする ? ?{1,2},{1,3},{1,4},{1,5}…{1,n},{2,3},…{2,n},{3,4}…というように、全て の辺を順に調べる ? この段階で{a,b}=0のときこの道は結ばない、{a,b}=1のとき結ぶ ? このような方法でやると、無駄な四角形の部分がなくなる
小課題2(64点) ? {a,b}を求めるのに最大でO(n^2)かかります。 ? 実際は線分の数は大体nに比例し、平均で3nくらいになります。 ? そして、{a,b}はn^2回呼び出すので、最大でO(n^4)となります。 n=100の場合、定数が(?)*(?)=(?)くらいつくので、約2500万 回?間に合います。 ? しかし、n=2000のときはTLEしてしまいます。
考察2 ? どのような順序で調べてもよいが、線分の交差判定をしている時間 が無駄 ? ?何が使えるか? ? 方法としては、外から順番に道を引いていくが、印をつけた点を除 く点集合のConvex_Hullの周りは全て道で囲むことができる ? そして、Convex_Hullになった点は印をつける ? これを繰り返していけば、最終的にすべての点に印がつく
考察2 ? 以下のような図になる。(左?右)
考察2 ? 前の図で、2つのConvex_Hullで囲まれた凸多角形の間にも辺 が結べる ? それに対して全探索をする場合、前よりは計算量は落とせるが 小課題3は通らない ? 2つの凸多角形の間に何本の点が引けるのかを高速に求めた い
考察2 ? これは以下のようになる。 ? a頂点からなる凸多角形とb頂点からなる凸多角形の場合 ? ただし、前者の方が外側とする。 ? b=1のとき、a個の道が建てられる。 ? b≧2のとき、a個の道が建てられる。 ? 証明は、次のページを参照してください。
考察2の証明 ? まず、b=1のときb側の頂点からa側の頂点に1つずつ道が引けるの で、合計でa個道が引けます。 ? そして、b≧2(a≧b)のとき、交点ができないようにa側の点から1つず つ道を引くと、b個の四角形ができます。 ? ただし、n角形は四角形n-3個分とします。 ? 四角形1つにつき1本追加で道が引けるので、追加で道をb個建て ることができます。よって、合計でa+b個の道を建てられます。 ? a≦bのときもaとbを逆転すれば証明できます。
考察2の証明 ? b=1のとき/b≧2のときは以下の図のようになります。
満点解法 ? 考察2を利用して解けます。 ? 解法としては、Convex_Hullを求めて、その点集合に印をつけ ます。そのとき、sumに点集合の数を加算します。 ? そして、このConvex_Hullが2つ目以降の場合、1つ前の Convex_Hullの点集合と結べる道の数をsumに加算します。 ? sumの最終的な値が答えとなります。
満点解法 ? 考察2の証明の右のほうの図では、答えは4+3+7=14個となり ます。 ? 計算量は、Convex_Hullを求めるのに最大でO(n^2 logn)かかり、 sumに加算するのに最大でO(n)かかるため、計算量は最大で O(n^2 logn)となります。 ? n=2,000のとき、計算量は最大で約4,000万回?間に合います。 よって、合計100点が得られます。
満点解法 ? この問題は、H問題と同じくらい、このsquare869120Contest#2 で1,2を争うくらい難しい問題だと思います。 ? ちなみに、私は考えるのに2日間もかかってしまいました。 ? 想定解は66msです。 ? JOIの難易度表でいう難易度10くらいでしょう。
結果 ? First Acceptance:DEGwer(18分07秒) ? 得点分布
おしまい
H問題 Counting 1's 解説
はじめに ? square869120Contest #2 にご参加いただきありがとうございます。 ? 私は解法を考えるのに 2 日かかりましたが, G問題はもっとかかりました。 ? 問題を考えてから思ったんだけど, JAGAsia 2012 にも Counting 1's とい う問題があったが, 全然違う問題である。そもそもJAGの方のCounting 1'sは難易度が高すぎます。
はじめに ? E869120, square1001の2人で合計20-30問くらい (約 10-15問ずつ) の 問題の候補を出しましたが, 2人で話し合って合計8問 (4+4) を厳選しま した。そして, この8問を出すことにしました。 ? 解法を考え終ってからいざ実装すると約40行で書けてしまって 「えっ、こ れが H 問題なのか?」 と思いました。
問題概要 ? 長さ N のビット列 a[0], a[1], a[2],...a[N-1] があり, 0 で初期化されている。クエ リが Q 個与えられ, 次の 2 つの処理のどちらかを行う。 ? Query 1: 区間 [l, r) のビットをすべて反転させる ? Query 2: 区間 [l, r) のビットが 1 であるものの個数を数える ? 制約 ? 1≦N≦100,000 ? 1≦Q≦100,000
問題概要 ? N=8 , Q=4 のとき (入力例1) i 0 1 2 3 4 5 6 7 a[i] 0 0 0 0 0 0 0 0
問題概要 ? N=8 , Q=4 のとき (入力例1) ? Query 1: 区間 [3, 7) のビットを反転させる i 0 1 2 3 4 5 6 7 a[i] 0 0 0 1 1 1 1 0
問題概要 ? N=8 , Q=4 のとき (入力例1) ? Query 2: 区間 [2, 5) のビットが1のものの個数を求める ? 2 i 0 1 2 3 4 5 6 7 a[i] 0 0 0 1 1 1 1 0
問題概要 ? N=8 , Q=4 のとき (入力例1) ? Query 1: 区間 [2, 4) のビットを反転させる i 0 1 2 3 4 5 6 7 a[i] 0 0 1 0 1 1 1 0
問題概要 ? N=8 , Q=4 のとき (入力例1) ? Query 2: 区間 [1, 6) のビットが1のものの個数を求める ?3 1 0 1 2 3 4 5 6 7 a[i] 0 0 1 0 1 1 1 0
部分点解法(8点) ? 何も工夫をしないでやります。 ? 1つのクエリに対して O(N) で処理します。 ? 全体の計算量は O(NQ) ? ?これだけで 8 点もらえる !
部分点解法 (16点) ? 制約 ? 1≦N≦100,000 ? 1≦Q≦100,000 ? Query 2 は 1,000 個以内 ? そのままでは Query 1 にO(N), Query2 にO(N) かかっているので間に 合わない ? Query1 の実行速度を速くするためにはどのような方法を使えばよいか?
部分点解法 (16点) ? 次のようなクエリに置き換えることもできる ? Query 1: 区間 [l, r) に 1 加算する ? Query 2: 区間 [l, r) の中で 2 で割ると 1 余るようなものの数を求める ? 「いもす法」 という方法を使うと Query1 が O(1) でできる
部分点解法 (16点) ? 「いもす法」 とは? ? Query 1: 区間 [l, r) に対してa[i] += x とする ? Query 2: a[0], a[1], ... a[n-1 ] の値を求める ? Query 1 を O(1 ) で, Query2 を O(n) ですることができる。
部分点解法 (16点) ? Query 1: s[l] += x, s[r] -= x とする ? Query 2: a[i] = a[i-1] + s[i] である ? そのように, 累積和を応用するだけでそのようなクエリ処理ができる。 ? ?Query 1 に O(1),Query 2 に O(N) かかる ? ?小課題 2 には通る
部分点解法 (52点) ? 52 点をとれる解法が思いつかなかったので, 52点解法につての解説は しません。 ? 100 点解法はもちろんわかってますよ !
満点解法 ? ここではまず, 「平方分割」 という方法について説明する。 ? 例として, 次のようなクエリを処理する問題を考えてみよう。 ? 数列が 0で初期化されている ? Query 1: a[i] = x とする ? Query 2: 区間 [l, r) の最大値を求める ? 平方分割という方法を使えば, Query 1, Query2 ともに で求められ る
満点解法 ? N = 9 のとき 0 0 0 0 0 0 0 0 0 0 0 0 0
満点解法 ? Query 1: a[4] = 3 とする 3 0 0 0 0 3 0 3 0 0 0 0 0
満点解法 ? Query 1: a[2] = 5とする ? ? 5, 3, 0 の最大値は 5 ? ? ? ? 0, 0, 5 の最大値は 5 ? ? ? ? a[2] = 5 とする 5 5 0 0 5 3 0 3 0 0 0 0 0
満点解法 ? Query 2: 区間 [2, 8) の最大値を求める ? ? 赤い部分の最小値を求めればよい 5 5 0 0 5 3 0 3 0 0 0 0 0
満点解法 ? そのようにすれば, Query1 を で終わらせることができる ! ? 実際には, Query 1 には O(1) しかかかっていない
満点解法 ? 各ノードに 「ノードが示す区間に 1 が何個含まれているか」 を記録する ことができればよい ? 区間 [l, r) のビット列を反転させると, 1 の個数は (r–l) - 「区間 [l, r) の 1 の個数」 となる ? では, 実際にやってみよう ! ? まず, 最初は1つのノードが示す値について調べてみます。
満点解法 ? Query 1: 区間 [2, 3) のビット列を反転させる 1 1 0 0 1 0 0 0 0 0 0 0 0
満点解法 ? Query 1: 区間 [3, 6) のビット列を反転させる 4 1 0 0 1 3 0 0 0 0 0 0 0
満点解法 ? Query 1: 区間 [0, 3) のビット列を反転させる 5 2 0 0 1 3 0 0 0 0 0 0 0
満点解法 ? Query 1: 区間 [3, 4) のビット列を反転させる 4 2 0 0 1 2 1 0 0 0 0 0 0
満点解法 ? Query 1: 区間 [4, 5) のビット列を反転させる ? ?青い部分が O(1) では 1, 3 のどちらになるのか分からない 4 2 0 0 1 2 1 1 0 0 0 0 0
満点解法 ? 各ノードに 「ノードが示す区間の 1 の個数」 だけを配列に保存すると高 速に動作しない ? そこで方法を考えてみよう。 ? ノードAを反転させるとき, ノード A の子の 「ノードが示す区間の 1 の個 数」 は 「反転」 する。 ? このことを利用するべきではないか?
満点解法 ? 各ノードに 2 つの値を記録すればよい ? 区間に含まれる 1 の個数 (完全ではない) ? 各ノードが何回反転されたか ? では, 実際にやってみよう !
満点解法 ? Query 1: 区間 [2, 3) のビット列を反転させる [1, 0] [1, 0] [0, 0] [0, 0] [1, 1] [0, 0] [0, 0] [0, 0] [0, 0] [0, 0] [0, 0] [0, 0] [0, 0]
満点解法 ? Query 1: 区間 [3, 6) のビット列を反転させる [4, 0] [1, 0] [0, 0] [0, 0] [1, 1] [3, 1] [0, 0] [0, 0] [0, 0] [0, 0] [0, 0] [0, 0] [0, 0]
満点解法 ? Query 1: 区間 [3, 4) のビット列を反転させる [3, 0] [1, 0] [0, 0] [0, 0] [1, 1] [2, 1] [1, 1] [0, 0] [0, 0] [0, 0] [0, 0] [0, 0] [0, 0]
満点解法 ? 今 [2, 1] となっているノードに注目しよう。そのノードの子である [1, 1] と なっているノードは, 0 から 1 になっている (1 加算されている) が, その ノードは 1 減算されている。なぜなら, そのノードは 1 回反転されている ため 「1 から 0 になった」 とみなしているからである。
満点解法 ? Query 1 は, 各ノードに対して O(1) で処理できることが分かった。 ? 次に, Query 2 についてやってみよう。
満点解法 ? Query 2: 区間 [3, 6) の 1 の数を求める ? ?上のノードで全く反転されていないので, 2 である。 [3, 0] [1, 0] [0, 0] [0, 0] [1, 1] [2, 1] [1, 1] [0, 0] [0, 0] [0, 0] [0, 0] [0, 0] [0, 0]
満点解法 ? Query 2: 区間 [4, 5) の 1 の数を求める ? ?青い部分が反転されていることを考えると, 求めるノードも反転されているの で, 1-0=1 個である。 [3, 0] [1, 0] [0, 0] [0, 0] [1, 1] [2, 1] [1, 1] [0, 0] [0, 0] [0, 0] [0, 0] [0, 0] [0, 0]
満点解法 ? 区間は, 程度のノードの集合としてあらわされる。 ? N=9 で, 区間 [2, 7) を表すとき, [2, 3), [3, 6), [6, 7) に処理をしていけ ばよい ? Query 2 の場合は, その合計を求めればよい ? 全体の計算量は
満点解法 ? SegmentTreeを使って同様の処理をすることもできる ? 平方分割は, 3段になっていて, 1つのノードの子が √(n) 個ある。 ? Segment Tree は, logn 段になっていて, 1つのノードの子が logn 個ある。 ? 同じような方法で, Query1, Query2 を処理できる。
満点解法 ? Segment Tree を使うと, ? Query 1 … ? Query 2 … ? n が大きくなると, SegmentTree の方が実行速度は速い。 ? n = 100,000程度の時は, Segment Treeと平方分割がだいたい同じ速度 になる。
満点解法 ? ちなみに, 私が最初に思い付いた解法がSegment Treeによる解法で, 実 装は本当に簡単でした。 ? 平方分割による解法はコンテスト 5 日前に思い付きました。
結果 ? First Acceptance … yosupo(5分13秒) ? 得点分布

More Related Content

Square869120 contest #2