なんとな～くしあわせ？の日記

「そしてそれゆえ、知識そのものが力である」 (Nam et ipsa scientia potestas est.) 〜 フランシス・ベーコン

SoundHound Inc. Programming Contest 2018 - (Ordinary Beauty) 再考

AtCoder アルゴリズム 競技プログラミング

問題は単純なのだが、解法が全然思いつかず。

問題

C - Ordinary Beauty

  • N, M, D が与えられるとき
  • 1 ～ N までの種類の整数を使って
  • サイズMの数列を作ったとき
  • それぞれの隣り合う要素の差がDになるものの合計値を数列の美しさとして定義する

各要素が 1 以上N以下の整数である長さMの数列は全部でN^M通り存在します。 このN^M通りの数列すべてに対して美しさを求めて、それらの平均を出力してください。

n, m, d = 2, 3, 1 のとき、並べ替えのパターンと数列の美しさは

111 = 0 
112 = 1 
121 = 2 
122 = 1 
211 = 1 
212 = 2 
221 = 1 
222 = 0

考えたこと

  • 数列 [ 1, 2, 3 ... n ] から重複を許して m 個選んで並び替えたときの要素m-1個すべて差分を数え上げれば答えが出るな！（死）
  • 上記は考えたのだけど、問題の制約からnもmも10^9まで行くので間違いなく制限時間に間に合わない→解法が思いつかず寝る

方針

以下、解説のリーディング

期待値の線形性を利用して数列の美しさの算出を分解する

隣り合う 2 項は m − 1 通り存在します。

わかる（自明）。サイズmの数列を作るので、間に入るそれぞれの要素の差分はm-1個になるはず。

期待値の線形性から、m − 1 通りそれぞれについて差の絶対値が d である確率を求めて、足し上げれば答えが求まります。

は？なんで（半ギレ）要は数列考える際に、m 個選んで並び替えするということは必要なく隣り合う２つの要素の差を考えてm-1個足し上げると答えになるようです。めちゃくちゃ不思議。期待値の線形性については　和の期待値は期待値の和 | 高校数学の美しい物語　が参考になりました。

リンク先の「期待値の線形性の応用例2」が、そのまま今回の問題に適用できるので解説の画像を作りました。

例

f:id:panzer-jagdironscrap1:20180709114308p:plain

問題

f:id:panzer-jagdironscrap1:20180709115138p:plain

d = 0の場合と d != 0の場合で場合分けする

確率を求める処理を、d = 0の場合と d != 0の場合で場合分けします。これは単にその２通りで計算が変わるからでしょう。

1 から n までの整数のペア (a, b) の差の絶対値が d である確率を求めます。
d = 0 であるとき、条件を満たすペアは (1, 1), . . . ,(n, n) の n 個です。よって、確率は n / n^2 = 1 / n です。

与えられた数1~nまでを使用して同じものを並べるだけなのでn通りあるはず。全体はn^2通りあるので、d = 0の場合の確率は 1 / n。

d != 0 であるとき、条件を満たすペアは
(1, d + 1), . . . ,(n − d, n) と
(d + 1, 1), . . . ,(n, n − d) の
2(n − d) 個です。よって、確率は 2(n−d) / n^2 です。

これも考えてみれば簡単で、1~2のカードを重複を許して２枚並べてその差分が１になるのは(1,2)のときと(2,1)のとき。これを一般化したものとわかる。

解答コード

コード自体は短く、小数点以下の桁数を0埋めしていると正解になった。

lines = $stdin.read
array = lines.split("\n")
N,M,D = array[0].split(" ").map(&:to_i)

ans = if D.zero?
        1.quo(N)
      else
        (2*(N - D)).quo(N**2)
      end

puts "%.10f" % ((M-1)*ans).to_f

Submission #2816342 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-

AWS GlueでSparkのDataframeを使う

PySpark AWS Python

AWS GlueでSparkのDataframeを使う

Glue上のクラス構造

docs.aws.amazon.com

  • 引用

Apache Spark の主要な抽象化の 1 つは SparkSQL DataFrame で、これは R と Pandas にある DataFrame 構造に似ています。DataFrame はテーブルと似ており、機能スタイル (マップ/リデュース/フィルタ/その他) 操作と SQL 操作 (選択、プロジェクト、集計) をサポートしています。
これらの制限に対応するために、AWS Glue により DynamicFrame が導入されました。DynamicFrame は、DataFrame と似ていますが、各レコードが自己記述できるため、最初はスキーマは必要ありません。代わりに、AWS Glue は必要に応じてオンザフライでスキーマを計算し、選択 (または共用) タイプを使用してスキーマの不一致を明示的にエンコードします。これらの不整合を解決して、固定スキーマを必要とするデータストアとデータセットを互換性のあるものにできます。

こう書かれてはいるが、DynamicFrameは少し自由度が低いように感じられる（S3やRDSへの接続が可能なのはいいんだけど）。とは言えDynamicFrameからDataFrameへの変換、そしてその逆が可能であるので、やりたいことは実現できた。

DynamicFrameからDataFrameへの変換

toDF
toDF(options)

# DynamicFrame -> Spark DataFrame
src_s3_df = DynamicFrame.toDF(<元のDynamicFrame>)
  • DynamicRecords を DataFrame フィールドに変換することにより、DynamicFrame を Apache Spark DataFrame に変換します。新しい DataFrame を返します。

DataFrameからDynamicFrameへの変換

fromDF
fromDF(dataframe, glue_ctx, name)

# Spark DataFrame -> DynamicFrame
result_s3 = DynamicFrame.fromDF(<加工したDataFrame>, glueContext, 'result_s3')
  • DataFrame フィールドを DynamicRecord に変換することにより、DataFrame を DynamicFrame に変換します。新しい DynamicFrame を返します。

ここまでをまとめると以下のような感じ

f:id:panzer-jagdironscrap1:20180621180055p:plain

DataFrameを使った処理など

連番作成

最初はrow_number()を使おうとしたのだけど、うまくいかなかったので zipWithIndex を使った。DataFrameに生えているrddを使えばOK。中のデータをいじるときはrddを更新したほうがよさそう。

rdd_indexed = dataframe.rdd.zipWithIndex().map(lambda x: (x[0][0],x[0][1],x[1]+1))
df = rdd_indexed.toDF(['id','score','rowNum'])
df.show()

カラムの追加、リネーム

withColumn, withColumnRenamedというものがDataFrameに生えているのでそれを使う。表形式のデータを変更したい場合はDataFrameに生えているメソッドでだいたい解決しそう。

.withColumn(lit('固定値'))
.withColumnRenamed('from', 'to')

あとはこの調子でデータを変形してDynamicFrameに戻せばまた連携できる

AtCoder - AtCoder Beginner Contest 066 (11) を解いてみた

AtCoder アルゴリズム 競技プログラミング

ABC 040 D問題に使われるアルゴリズム要素は組み合わせ、繰り返し２乗法、階乗のmod逆元、（＋累積和的な処理？）です。組み合わせ(nCr)については、以前動的計画法によるアルゴリズムを紹介しましたが

nantonaku-shiawase.hatenablog.com

AtCoderではこれでもまだ処理が遅くACが取れませんでした。

組み合わせ

繰り返し２乗法や階乗のmod逆元については、他でもいろいろ解説があるので言及しません。しかし、組み合わせの処理にてなぜそれらを使わなければいけないか書いておきます。

組み合わせを階乗の式で表す

Rubyとかだと配列クラス(Array)に#combinationメソッドが用意されておりすぐに求められるのですが、競技プログラミングの場合これでは遅すぎます。いったん組み合わせ(Combination)がどのような式で構成されていたか確認してみましょう。

組み合わせの式

以下のようなものになります、nの階乗をrの階乗と(n-r)の階乗で割ったものでした
{}_n \mathrm{C}_r = \frac{n!}{r!(n-r)!}

この、階乗の数値が巨大なものになってもすばやく計算する方法が繰り返し２乗法で、巨大な階乗の逆数を求める方法が階乗のmod逆元と呼ばれているようです。

英語で調べると、これらはFast modular exponentiation*1とかmodular inversesという名前で紹介されている感じです。

これらを覚えると、AtCoder Beginner Contest 021 (D - 多重ループ) も解けます、これは嬉しい。

ABC 066 (11) 、解説の解説

AtCoder Beginner Contest 066 (D - 11)

問題の考察ヒント

問題文から

数の種類が n 種で、項が n + 1 項あるので、必ず同じ数の項が複数存在します。
また、すべての数が 1 度以上現れるという制約から、同じ数である項はちょうど 1 組であることが分かります。

これがヒントになるようだ

考察

簡単な例
  • 入力値（1 だけ重複している）
3
1 2 1 3
  • 部分列を作ったときの状況

部分列の要素数n 状況 重複を見つける
1 4つのカードから1つを選ぶ組み合わせ(= 4C1 = 4)だったら簡単なのだが、１個重複があるので3通り {1}の要素は明らかに２回数えられている(=選び方が一意ではない)
2 4つのカードから2つを選ぶ組み合わせ(= 4C2 = 6)だったら簡単なのだが、１個重複があるので5通り {1, 3}の要素は明らかに２回数えられている(=選び方が一意ではない)
3 4つのカードから3つを選ぶ組み合わせ(= 4C3 = 4)だったら簡単なのだが、重複はないので 4通り N/A
4 4つのカードから4つを選ぶ組み合わせ(= 4C4 = 1)だったら簡単なのだが、重複はないので 1通り N/A

上記から、n+1 C r から重複分を除けば答えになりそうだとわかる（※問題出されたときにわかるかと言われると、う〜ん…）

重複を取り除くパターン

数列 a_n が以下のように与えられるとする、赤字が重複

index 0 1 2 3 4 5 6
1 2 3 4 5 3 6

ここから要素を１つだけ取得して並べるやり方は明らかすぎるので考えない、要素を２つ取得して並べる方法を樹形図にしてみた

f:id:panzer-jagdironscrap1:20180610122107p:plain

  • この図から、重複したものを選び出す場合の数は
    • {}_3 C _1 となることがわかる（※重複した要素の外にある３つの値{1,2,6}から1つを選び出す場合の数。3を選ぶことは確定しているので1つを選び出す場合の数となる。）
  • ここから一般化すると、組み合わせの式は
    • "重複した要素の外にある要素数" から "並べる部分列の要素数 - 1"
    • とりあえず考察要素に関してはこれで終わりで、後は考察した組み合わせの式をより早いオーダーで実行しなければいけません。

*1:modular exponentiation = 冪剰余