DDCC予選通過したはずだけどまだメール来てないです

シェアする

  • このエントリーをはてなブックマークに追加

こんばんは。お久しぶりです。

お久しぶりじゃダメだろ! という話ですが、なかなか時間が取れないもので。

まどマギ一挙とか、えとたま一挙とか……

この前のニコ生一挙放送で初めてまどマギ見たんですが、素晴らしいですね。

さやかちゃんが好きです。切ない。

さて、この前の土曜日にDDCC2016というプログラミングコンテストの予選がありました。

DISCOという半導体関係のメーカー?とディスカバリーチャンネルが主催のコンテストで、採用にもかかわるそうです。

私はDISCOに就職するつもりは無いのですが、予選通過したら就活のアピールポイントになるだろうと思って参加しました。

結果、4問中3問正解で66位となりました。

就活生枠(2018年3月卒業の大学・大学院生が対象)は80人分用意されていて、私はその対象者なので、予選は通過ということになります。まだメール来てないですが。

ということで、簡単に感想を書いていきたいと思います。

A,B問題

A問題は書くまでもないですね。(double)C*B/Aを表示して終わり。

B問題はとにかく問題が理解しづらいです。

要は、i番目のラインとi-M番目のラインの長い方(=中心に近い方)の長さを全部足せばいいわけです。

i番目のラインの長さは幾何学的に計算できますね。三平方の定理です。

このとき、iが中心より上か下かで計算式が変わるのに注意ですね。

あとは、中心に近い方の選んで足せばいいだけ。

分かってしまえば簡単ですね。

C問題

この問題が予選通過できるかできないかを分けたような気がします(就活生枠だと2完の早い人まで通過? 社会人枠だと3完でも早い方しか通過できない?)。

2数の積がKの倍数になるような組の個数を求める問題です。

自然数を素因数分解で考える癖がついていると、GCD(最大公約数)を使う発想はすぐに出てきます。

整数を素因数分解したときの、各素因数の指数を、素因数の小さい順に並べた無限次元ベクトルで整数を表すことができるという考え方があります(厳密には、線形空間の公理を満たさないのでベクトルとは言えません。無限次元空間の第一象限にある格子点でしょうか)。

たとえば、50=2^1*3^0*5^2*7^0*……なので、50=(1,0,2,0,0,...)と表現できます。

このとき、整数x,yの積は、この"素因数ベクトル"の和になります。指数法則ですね。

また、整数nがKの倍数であることは、素因数ベクトルの全成分についてnの成分の方がKの成分よりも大きいことと同値になります。当たり前ですが。

したがって、2数X,Yの積がKの倍数になるには、Xの素因数ベクトルの成分の中でKの成分より小さいものをYが完全に埋め合わせるという関係が必要になります。

つまり、そもそもXの素因数ベクトルのある成分がKの成分を超えている場合は、「Kの成分と同じ値である」と考えてもよいのです。

例えば、X=(1,5,2,1,0,...), K=(0,3,1,3,0,...) の場合は、X=(0,3,1,1,0,...) だと考えてもよいのです(結局必要なのは第4成分が2以上という条件だけ)。

これを言い換えると、「X*YがKの倍数ということは、GCD(X,K)*GCD(Y,K)がKの倍数ということと同じだ」ということになります。

すなわち、数列A[i]の入力を受け取る時点で、A[i]=GCD(入力値,K) としてよいのです。

この前提がすぐ思い浮かんだのが幸いでした。

そうすると、20万個の数字が入力されても、そのほとんどが被ってしまいます。

そこで、連装配列(C++のmap, C#のDictionary)を利用して、「KとのGCDが2になるのは7個」みたいな情報を記録しておきます。この場合はKeyが2でValueが7。

そうすると、連装配列の要素数は最大でもKの約数の個数になります。

さて、この時点で総当たりで積がKの倍数になるかを調べていくと、計算量はO((Kの約数の個数)^2)になります。これは大丈夫でしょうか。

実は、少し前にAtCoder社長のchokudaiさんが気まぐれで「Chokudai Contest 002」というマラソンマッチ形式のコンテストを開催しており、「10億以下の自然数のなかで約数の個数が最多のものは1400個以下の約数を持つ」ということがその中で示されました。

したがって、この総当たりの方針ではO(1400^2)ぐらいの計算量になり、「通るかも? 通りそう?」ぐらいの計算量になります。

実際、これで通ります。

連装配列をKeyの昇順にソートしておき、同じ組み合わせを見ないように2重ループを作ります。

ここで、「20と20の積は40の倍数だ」などを見るときに、組合せの個数を「map[20]*map[20]」などとしないように注意です。

同じカードは組み合わせられないので、map[20]*(map[20]-1)などにする必要があります。

コード貼るのは面倒なので、ACした提出コードへのリンクを貼っておきます。

http://ddcc2016-qual.contest.atcoder.jp/submissions/968304

それでは、また。

スポンサーリンク
レクタングル(大)
レクタングル(大)

シェアする

  • このエントリーをはてなブックマークに追加

フォローする