Hewlaの競プロ記

競プロ記です。

SoundHound Inc. Programming Contest 2018 -Masters Tournament- 予選 C, D - 解説

今回は30歳以上の方の枠が広いプロコンでした。かつて競プロですごく強かったみたいな人がでていらっしゃっていてかっこよかったです。憧れる〜

コンテストサイトです。
SoundHound Inc. Programming Contest 2018 -Masters Tournament- - AtCoder

C - Ordinary Beauty

n^mとか出てきて一瞬ドン引きします。1000000000^{1000000000}なんかC++では扱えません。でも平均というからには分母にn^mがくるはずです。なんとなく分子にn^{(something)}がくるときれいに割り切れてくれて幸せになれそうです。

真面目な考察

真面目に考えていきます。
手元で計算をします。分子には全ての数列の美しさの総和をつっこんでやらねばなりません。これを考えます。

k項と第k+1項によってつくられる美しさの和を全てのkについて足せば、全ての数列の美しさの総和を考えることができます。

k項と第k+1項の差がdとなるような「第k項と第k+1項の数の組」は、

  • d>0のとき 2(n-d)
  • d=0のとき n

組あります。

次に、第k項と第k+1項が美しいような数列の数を求めます。
k項と第k+1項の差がdとなるとき、他のm-2項はなんでもいいので、これを満たすような数列の数は

  • d>0のとき 2(n-d)n^{m-2}
  • d=0のとき n\times n^{m-2} = n^{m-1}

です。
これは、第k項と第k+1項によってつくられる美しさの総和と等しいといった言い方もできそうです。

長さmの数列で隣り合う2数はm-1組あるので、美しさの総和は

  • d>0のとき 2(n-d)(m-1)n^{m-2}
  • d=0のとき (m-1)n^{m-1}

となります。

あとはこれをn^mで割ります。答えは

  • d>0のとき \frac {2(n-d)(m-1)n^{m-2}}{n^m} = \frac {2(n-d)(m-1)}{n^2}
  • d=0のとき \frac {(m-1)n^{m-1}}{n^m} = \frac {m-1}{n}

です。

ビジュアライズ的な

この画像を見ればわかる場合とわからない場合があるぞい

f:id:hewla:20180710142141j:plain
①×②×③が美しさの総和となります

D - Saving Snuck

変わった通貨が出てきました。問題文読解がちょっとややこしくて戸惑いました。日本語が苦手。

0年目はどこで両替してもいいのでパターンがたくさんありそうで大変です。しかし、n-1年目は両替を都市nで行う必要があります。この年においては、

  • sからnまで円で移動
  • nからtまでスヌークで移動

ということになります。sからnに使う円とnからtに使うスヌークの最適解はダイクストラ法を用いると求められます。

n-2年目はn-1年目に比べて、都市n-1の両替所も使えるようになります。そうすると、先ほどの場合に加えて、都市n-1の両替所を経由して移動するパターンを考えて、この2パターンのうち答えの良い方を選んで答えとすればいいです。

同様に、n-3年目には都市n-2の、n-4年目には都市n-3の、...、1年目には都市2の、0年目には都市1の両替所が新しく使えるようになります。
都市sから都市iまで移動するのにかかる円の最小値をyen_i、都市iから都市tまで移動するのにかかるスヌークの最小値をsnuuk_iとします。
i年目の答えans_iは新しく使えるようになった両替所を経由する答えと1年後の答えの良い方なので、
ans_i = max(ans_{i+1},  10^{15} - (yen_{i+1} + snuuk_{i+1}))
となります。この漸化式を、n-1年後から順に埋めていけば良いです。

yen_iはsを始点としたダイクストラ法1回で全てのiについて求めることができます。
また、鉄道はどこも双方向に走っているので、snuuk_iはtからiまでにかかるスヌークの最小値に等しいです。したがって、tを始点としたダイクストラ法で求められます。

ダイクストラ法を実装したのはJOI以来です。というより実装を真面目にやったのがすごく久しぶりな気がします。思い通りに動いた時はやっぱり楽しいです。

Rating 2000以下はratedでした。青になりたい人向けコンテストみたいな感じです。またやってほs
全完して爆上げのつもりでしたがEが解けませんでした。A〜Dの4完でレートはなんとか上がってくれました。
f:id:hewla:20180708120101p:plain
perf:1896で、1483 → 1532 (+49)です。次回で青もあり得る!!!(しかしAGC)

AGC023 A, B

AtCoder Grand Contest 023です。僕の考えたことをゆっくり書いてます。

A - Zero-Sum Ranges

数列から二つ数字を選んだときにその間に並んでいる数字の和が0になる選び方はいくつありますかって感じの問題です。僕の解法を書いていきます。

愚直に実装すると、

  • 始点のループ
    • 終点のループ
      • 始点から終点までの和を計算するループ

となります。 O(N^3)ですかね。わからない。まあとりあえず間に合わなさそうです。

こういう感じのやつって、何となく累積和を取りたい気持ちになります。整数の配列sumを用意したとき、sum[i]はa_iまでの和を表す、みたいな感じのが累積和です。問題文はa_0がないので、sum[0]は0としておきます。

じゃあこの累積和を使って何ができるでしょうか。
a_iからa_jまでの和はsum[j] - sum[i-1]であることから、a_iからa_jまでの和が0のとき、sum[i-1] == sum[j]です。
つぎに、これを満たすようなi, jの和を数えればよいです。
累積和をとった時にこのように部分列の和が計算できるのはよく使う気がします。

例えば入力例1では、sumの中身は

  a:    1  3 -4  2  2 -2
sum: 0  1  4  0  2  4  2

という感じになります。
sumには3組同じ数字のペアができていて、この数は答えと一致しています。

しかし、いくつペアがあるかを

int ans = 0;
for(int i = 0; i <= n-1; i++){
    for(int j = i+1; j <= n; j++){
        if(sum[i] == sum[j]){
            ans++;
        }
    }
}

という感じでループして調べようとすると、これは O(N^2)となって間に合いません。

同じ数字のペアがいくつあるかを調べたいので、同じ数を集めてやることができれば数えやすくて幸せになれそうです。ソートをします。
mapとかを使ってやるのも手です。
入力例1では、

sum: 0  0  1  2  2  4  4

となります。これだと、連続する2数を調べて等しければans++とすればいいような気になりますが、それは正しくありません。たとえば3つの数が連続している時、組み合わせの数は3つあります。
同じ数字がm個連続しているとき、そのm個からできうるペアの数は
 _m C _2 = \frac{1}{2}m(m-1)
となります。連続している数からこれを計算し、答えとする変数にたしてゆけばよいです。

以下僕の汚いコードです。
入力を0-indexedで受け取ったので些かややこしいです。
和はintの範囲を超える可能性があるので気をつけました。

B - Find Symmetries

日本語が難しかったです。結構誤読しました。
正方形のマス目にアルファベットが書いてあります。
f:id:hewla:20180428234640p:plain
この図はそのマス目を表しています。マス目のうち1つを選んで、それが点(0, 0)に来るように平行移動します。その結果できたアルファベットの並び方が上図の赤い線を軸として対称になるようなマス目の選び方は何通りあるかという問題です。

愚直に実装した場合どうなるでしょうか。平行移動をする基準の点を探すのにO(N^2)、平行移動したときにそれが対称になっているかどうかを確かめるのにO(N^2)ですので、合わせてO(N^4)です。300^4 = 81\times10^8なので間に合わなさそうです。

ここで一つ閃きですが、(a, b)の移動がよい盤面を作るのならば、(a+x, b+x)の移動もよい盤面をつくるという事実があります。
ちょっと説明をします。
今、うまく対称になっている盤面があるとします。
マス目(1, 1)を選んで(0, 0)に移動させたとき、これも対称になります。それぞれのアルファベットの軸に対する位置関係は変わらず、軸に対して平行に移動するからです。
そうすると、(0, 3)が適しているならば、(1, 4)も適しているはずで、以降同様に緑色の線の上のN個のマス目は全て適しているということができます。
f:id:hewla:20180429000128p:plain

それなら、(0, 0)から(0, n-1)まで一番上の列について調べ、適しているならば答えにNを足せばよさそうです。
点の選び方がO(N^2)からO(N)に変わったので、あわせてO(N^3)、これで間に合います。

以下コードです。割と綺麗に書けたつもりです。関数に飛ばすの好き

感想

なんだか今日はうまくいきました。
perf:2129, レート+97で1515, Highestです!幸せ
f:id:hewla:20180429000743p:plain
ちなみにC問題はわかる気がしなかったので撤退しました。

説明下手くそで恐縮ですがやってればそのうちだんだん上手になると思います。思いたいだけです。
コンテストのたびに書いたり書かなかったりしますが、よろしくお願いします。

ARC095/ABC094 C, D

AtCoder Regular Contest 095, AtCoder Beginner Contest 094のC問題, D問題です。

C: Many Medians

まあまずこういうのってとりあえず数列をソートしますよね。ソートしたあとの数列とする前の数列を両方取っておきます。

まず頭に浮かぶこととして、
「1つぐらい数字を消しても、中央値の位置って大きくてもせいぜい1しかずれないよね」
ということがあります。
元の数列の長さは偶数なので、ソートした数列で真ん中の2つが中央値候補です。その候補たちの左側が消された場合は右側の候補が、逆に右側が消されたら左側の候補が答えになります。これは大小比較したらよいです。

あとは、中央値候補本人が消えた場合のことをちょっと考えてから実装してやります。
僕はここでなんか迷ってしまいました。ここでさっとクリアに見通せるようになりたい。

以下僕の汚いコードです。med1, med2が候補になってます。

D: Binomial Coefficients

nCrのお話ですね。高校の数学Aでおなじみのやつ。結構時間を溶かしてしまいました。考えたことを事細かに書いていこうと思います。

はじめ、なんとなくcomb(n, r)のnは大きければ大きいほどいいんじゃないかなって考えました。実はこれは正しかったのですが、このときの僕は何を考えたのか
「いやいやcomb(12, 1)と(11, 5)なら(11, 5)のほうがでかいやんか」
とか考え始めました。今思えばこれが大失敗の元でした。
そのあとは迷走して、パスカルの三角形とか色々考えてましたが、ようやく気づきました。

「さっきcomb(12, 1)と(11, 5)で考えたけど、(11, 5)に5が使えるなら(12, 5)もつくれるやん

そして、comb(n, r)とcomb(n+1, r)ならcomb(n+1, r)の方が大きいことを確かめました。rが同じ数ならnは大きい数の方がいいということになります。階乗で表現した式を考えれば簡単です。じゃあ、nは最大の数を使って良さそうです。

じゃあ、rは何がいいのでしょうか。ここでパスカルの三角形の出番です。

    1        
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

こういうやつです。nCrとの関係はご存知である前提で話を進めます。知らない人は調べてね。これを見ると、真ん中のほうの数字が大きいのがわかると思います。ここから、

rはn/2に近い方がよい

ことがわかります。じゃああとは簡単です。一番大きい数字を選んできて、あとはそれより小さい中でn/2に一番近いものを選んだら良いです。

実は僕はここでバグを産みました。ここで比べるべきは、rの候補とn/2との差ではなく、(rの候補)*2とnとを比べるべきだったのです。どういうことかというと、
例えばnが9で、rの候補に5と3があるとしましょう。9/2は4.5なので、このうちだと5の方が近いです。しかし、9/2は整数どうしの演算なのでコンピュータの内部では答えが4となり、実装によっては3も選ばれてしまう可能性がでてきてしまいます。
普段なら気をつけるのですが、なんだかややこしくって完全に忘れていました。恥ずかしい〜

ということで1WAでACです。

感想とか

f:id:hewla:20180414232812p:plain
レートが下がりました!w
D問題でウジウジしてしまったのが原因ですね。E問題解けると良かったんですが、なかなかきつかったです。
まあ楽しかったので良しとします。次回はhighest出したいですね。

GCJ ROUND 1A 2018

お疲れ様でした。2問目、3問目ほとんどわからなかったので撤退しました。

BとかCとかで上位勢が抜けたところを狙っていきたいと思います。

 

Waffle Choppers

縦にR行、横にC列並んだ正方形のセルからなる巨大な長方形のワッフルがあります。このセルにはチョコチップが1つ入ってたり、また入ってなかったりします。

このワッフルを横向きにH回、縦向きにV回切ることで(H+1)×(V+1)個の長方形に分けます。このとき各ピースの大きさは異なっていても構いませんが(いいのかよ)、どのピースにも同じ数のチョコチップが入っていないといけません。

R, C, H, Vと、チョコチップのある位置に関する情報が与えられるので、この条件を満たすように切り分けることは可能かどうか出力しなさい、という問題です。問題文を適当に抜粋したため条件に抜けがあるかもしれませんので、 詳細は問題文を参照してください。

考察 - Hidden-

これ、最初から何ピースに分けるのかがすぐにわかります。(H+1)×(V+1)です。 チョコチップの個数の和をS、ピース数をP = (H+1)×(V+1)とすると1ピースにはS/Pこのチョコチップが入ります。SがPで割り切れなければIMPOSSIBLEです。

ここから少し考察しました。横にH回切るとH+1個の帯ができます。この帯それぞれをV回縦に切るとき、そのすべてに同じ数のチョコチップがないといけないわけですから、すべての帯に含まれるチョコチップの数も同じ数にならないといけません。帯をH+1個作ることと、チョコチップがS個あることから、各帯にはS/(H+1)個ずつチョコチップが入るように切り分ける必要があります。これをもとにうまいこと(全ての帯にS/(H+1)個のチョコチップが

入るような切り方を探す)処理すると、「どこで横に切るといいか」ということがわかります。ここの実装で迷ってしまったなんて言えない(精進不足)

同じことが縦に切り分けるときのことについても言えるので、どこで切り分けるといいかが縦横全てについてわかることになります。この分け方以外に条件を満たす切り分け方がある可能性がないってことになります。あとは、その情報に基づいて「各ピースにしっかりS/P個のチョコチップが入っているか」を確かめます。

 

感想

なかなか実装がしんどかったです。てか僕の実装がクソ実装だったんでしょうね。それだけにACしたときはびっくりしました。絶対落ちると思ってた

次回、Round1Bもがんばります

 

2018/07/07 追記

そういえばこの後1Bと1Cも落ちました

開設してみました

ひゅーらです。ブログを開設してしまいました。

 

お前そんな実力で競プロ系のブログとか作ってどないするねんという声が聞こえてきそうですが、まあ思いついたので始めちゃいました。思いついたならしょうがない

 

自己紹介

ひゅーらといいます。

AtCoder ID: Hewla     Hewla - AtCoder

Twitter: @hewla

です。よろしくお願いします。

AtCoderのレートはこんな感じです。

f:id:hewla:20180409223350p:plain

今年は受験生なので精進をしていません。

実力が単調減少しています。

だいたい毎週末のAtCoderには出たいなと思っています。

 

ここではいったいなにを書くの

プログラミングコンテストが終わってからとかに、自分が解けた問題とかについて

僕がその解法に至るまでにどんな間違いを経由したか、

どういう気持ちで考察したのか

どうやってこれを思いついたのか

みたいなことをゆっくり書いていきたいです。

 

対外的には、競プロをはじめてそんなに日の経っていない人が

「こういう風に考察する人もいるんだ」ぐらいに

参考にできるようなブログを目指していこうとおもいます。

 

そんな感じです

コンテストが終わってからってなかなか寝る気にならないんですよね。

Twitterは楽しいし。

この時間をつかって適当に書いていこうと思います。

受験勉強には支障はでないはず、、、

気がむく限りは続けます。よろしくお願いします。