ARC080 E: Young Maids

競技プログラミング 競技プログラミング/AtCoder データ構造/セグメント木

arc080.contest.atcoder.jp

解き方

  • 辞書順なので、先頭から埋める
    • 最初の数列で、奇数番目が解答の先頭に、偶数番目が解答の2番目にくる
      • 奇数番目の最小の数字が先頭に、それより後ろで最小の偶数番目が2番目にくる
    • 3つの領域に分割されるので、それらについて同じように考える
  • ある領域の中で最小の数字を見つけるのはセグメント木（RMQ）
  • いくつかの領域のなかで奇数番目が最小の領域を見つけるには、priority_queueを使う

ハマったところ

  • 最小の領域を見つけるのに、priority_queueを使わずmin_elementを使用
    • いい加減O(n)のSTLを使ってTLEはやめたい
  • セグメント木の実装をコンテスト中にバグらせずにやるのは時間が足りない
  • 不要なところを埋めるmaxに10^5を使っていた。
    • 1e7とか書くと浮動小数点になるから嫌だなぁと思っていたけど、わかりやすさのためには使った方が良い気がする

github.com

ARC080 C: 4-adjacent

競技プログラミング 競技プログラミング/AtCoder

arc080.contest.atcoder.jp

解き方

  • すべての数字を4で割った余りに変えても同じ
  • 2は全部連続させて良い（分けることでうまく行くパターンが増えることはない）
  • 2の連続、1のとなりには0が来ないといけない（2...2, 0, 1, 0, 1, ...., 1, 0, 1など）ので、それぞれの個数を調べて判別
    • 2, 2, ....., 2の場合は例外として、0がなくてもYesなので注意が必要

ハマったことろ

  • 一番一般的な場合の判定式をミスって実装した
    • 例題の内容くらいは手を動かして確認したほうが良い？
  • 場合分け忘れと実装ミス多数
    • サンプルにないコーナーケースを見つけたら横着せずにサンプル追加したほうが良さそう

github.com

活動記録(2017/7/31-2017/8/6)

活動記録

競技プログラミング

ARC80

結果: 613rd, 1480->1449 (Perf:1225)

前回が良すぎたのでレート落ちは想定内。前回と合わせて800点問題に手が出るようになってきたように感じられるのもモチベーション向上にはつながった。 ただ、CとDで4回とか実装ミスWA・REさせたのはもう駄目。ことによるとCのような場合分けをちゃんとして答えを出すやつは苦手かもしれない。

Eについては、競技時間中に0からセグメント木を実装するのは色々と無理があったように思うので、utils拡充も必要。

マイクロマウス

PiCo 3が来て、はんだ付けの道具がないことに気づき、注文した

実装・実験

DeepCoder

評価をとりあえず行って収束させた。実験速度向上のためにはマルチGPUから逃れられそうにないし、複数GPU積んでるマシンは高いし、p2.xlargeのクラスタを夢見てChainerMNを試してみることにした。

その他

デスクトップをArchLinuxとWindowsデュアルブートにした。Wake on LANの設定が整えば、i7, 64GB, GTX 960の開発鯖が出来上がる（はず）

ARC079 F: Namori Grundy

データ構造/グラフ アルゴリズム/深さ優先探索 競技プログラミング/AtCoder 競技プログラミング

arc079.contest.atcoder.jp

解き方

  • 1つ閉路があり、残りはその閉路にぶらさがっているようなグラフ
  • 閉路とそれ以外にまず分ける
  • 閉路以外の部分は、根を0、その上を…としていくと一意に定まる
  • 閉路については、適当に1頂点にxを割り当てて、うまくいくか計算する。xは、0以上、その頂点の次元数+1 以下なので、そのパターンだけ試す。

ハマったところ

  • コンテスト中はここまで考察できていなかった
  • 閉路を見つける部分は、スタックを使いまわすような形式じゃないと辛い（stackにパスをpushしていくと多分O(n^2)。関数スタックをシミュレートするような実装のほうがこの場合効率が良い）
  • std::findはO(n)なのでループの中では厳禁。メモリに余裕のあるケースのほうが多いので一度unordered_setに変換するべき

github.com

DeepCoder 追実装まとめ

DeepCoder 実装 機械学習

概略

[(Input, Output)] => Map[関数, 出現確率]の関数をディープラーニングで学習し，それを利用してプログラム空間を探索・プログラム合成をする． 詳しくは論文．

実装

レポジトリ

chainerに慣れていないため、諸々非効率的と思うが、実装自体はそこまで難しいところはなかった。 細かい反省点としては、データセットをJSONで保存するのは馬鹿らしかったなどなどがある。ただ、とりあえずやってみることを重要視した以上、実装での汚い点、反省点があるのは当然とは思っている。

学習

最終的に学習に用いたデータセットは800万件ほど。g3.4xlargeを利用して24時間強学習した。lossは下のような感じ。環境変数で与える学習パラメータは、ALPHA=0.0001、EPOCH=1000、BATCH_SIZE=1000で行った（詳しい実装はレポジトリを参照）。今考えると学習率上げてもよかったかもしれない。

f:id:mhiroaki0000:20170802184110p:plain:w300

当初はp2.xlargeを利用していたのだが、CPU側メモリが足りなくてabortするという事態が発生したので、急遽インスタンスタイプを変更した。 データセットを生成後S3に上げるというワークフロー、メモリに展開するべきではない制約を鑑みるとSQLiteが妥当だったと考えている。

また、プロトタイピングという目的からは、学習に1日かかるというのは問題。方法は以下の3つほど考えられる。

  1. 小さいデータセット、単純な問題で実装を進め、最後に規模を大きくする
  2. 複数のGPUを積んだEC2インスタンスを利用する
  3. いくつかのp2.xlargeあたりのインスタンスでクラスタを組む

1は単純なアプローチだけど、結局規模を大きくしたときのデバッグで苦しむ気がする。2は一番素直だけど、値段が跳ね上がる（余っていないらしくスポットインスタンスによる費用抑制ができない）という問題がある。 3は、上手くスポットインスタンスを組むことができれば、一番潰しが効く気がするけど、実現難易度は高い。

評価

ランダムに100個プログラムと入出力サンプルを生成して、プログラム合成をさせた。各サンプルに対し、以下の3パターンを試している。最後のやつの詳細は論文参照。

  1. DFS (DNNなし)
  2. DFS (DNN利用)
  3. “Sort and Add” Enumeration (DNN利用)

ただし、1800秒たっても合成できない場合はタイムアウトさせて終了させている。

結果

経過時間平均と標準偏差 (秒)

DNNなし DFS with DNN “Sort and Add” Enumeration
434.55 (695.86) 1075.42 (794.41) 464.11 (718.14)

見ての通り、DNNを利用したときの方が遅くなっている。一応DNNの推論分の時間がDNN使用の時には追加されているが、それを考慮してもやはり遅くなっているはず。

経過時間平均と分散（高階関数抜き） 実行過程を眺めたところ、高階関数で時間をとっているような気がしたので、高階関数を使っていない場合飲みを抽出して再度計算した。

DNNなし DFS with DNN “Sort and Add” Enumeration
580.51 (786.43) 639.75 (781.70) 369.43 (656.61)

自分の直感どおり、早くなってはいるが、母数が少ない（18件）し、分散は大きいし、よくわからない。

まとめ・所感

DeepCoderそのものについて

実装・学習

一点（整数のembed方法）を除いて元論文の通りに実装しているはず。ただし、データセットの生成手法・学習手法については元論文に詳細な記載がないので本当に同じかはわからない。多分違う。

評価

全体的には性能向上は見られなかった。一方、高階関数を使わない場合は学習が効果があったのかもしれない（ただしよくわからない）。 総じて、上手く学習できているのかはよくわからないという結論を出さざるを得ないと思う。

なお、評価方法については、以下の2つの懸念点がある。

  • timeコマンドを時間計測に利用
    • より正確なデータが必要なら真面目な計測をしないといけないが、面倒だった
  • 各サンプル1回しかテストをしていない
    • 他に最低限のプロセスしか動いていないEC2インスタンス上でテストしたので、実行時間の分散は比較的小さいと思う

学習を続ければまだlossが下がりそうなので、もう少し学習時間を取ると予測精度が上がって速度向上につながるかもしれない。ただ、それをやっても自分として得られるものが少ない気がするのでここで追実装としては終わりの予定（暇だったりなんかのついでにできたらやるかも）

機械学習とかプログラム合成について

機械学習

  • 比較的簡単なネットワークであっても、1 GPUの学習には限界がある
    • 複数のGPUを使える環境は優先的に整えたほうが良い
  • データセットは一次記憶に展開しなくて済むよう、最初から実装するべき
    • それなりの時間を無駄にしかねない

プログラム合成について

  • 結局全探索なので、探索方法の工夫での高速化の余地は大きい
    • 今回で言えば、反復深化法のほうがDFSよりはあっていたという予感がある。
  • 実行速度にダイレクトに関わるのはプログラムの長さ
    • 長さ4, 5のプログラムが一瞬で生成できるわけではない。
    • 元論文でも、平気で合成に数千secとかかけている。

作業記録

mhiroaki.hatenablog.com mhiroaki.hatenablog.com mhiroaki.hatenablog.com mhiroaki.hatenablog.com

DeepCoder追実装記録 (4)

DeepCoder 機械学習 実装

前回まで

mhiroaki.hatenablog.com mhiroaki.hatenablog.com mhiroaki.hatenablog.com

学習

思い立って800万件で学習する。学習の様子は以下のような感じ。

f:id:mhiroaki0000:20170802184110p:plain:w300

この時、p2.xlargeのCPUメモリが足りなくなって強制終了されていた。 今回はg3.4xlargeを使って対処したが、実際は、SQLiteなどを使ってメモリを節約する必要がありそう。

評価

ランダムに100件プログラムとInput-Outputサンプルを生成し、評価してみた。 詳しくは後でまとめるが、DNNの推論部分を含めると平均実行時間は増加してしまっているように見える。