Aizu Competitive Programming Camp 2017に参加しました
チームperyaudo（@mt_caret、@raven_38_、@54k3y）に混ぜてもらってACPCに参加しました。オンラインです。
詳しいことはcaretくんが書いてくれました。わざわざ記事を立てることもなかったんですが、記念に立てたかった。
mt_caret.log - Aizu Competitive Programming Camp 2017参加記https://t.co/083i3x82K1
— IN THE 熱湯 (@mt_caret) 2017年9月20日
書きました。
ということなので個人的な話をします。
僕は1日目のC、2日目のE、3日目のBを解きました。見返すとどれもやるだけという感じだし、時間の割に解いた問題が少なくて悲しい。とはいえ他の問題も読んで口を出したり解法を思いついて書いてもらったりしてチーム競技っぽくて楽しかったですね。
3日目BはWAを出しまくって最終的にPython3で書いたら普通に通ったので悲しい気持ちになりました。やはりPythonは正義。
解法がわからないのは精進するしかないとして、反省点としては実装力の無さを改めて感じました。みんな書くのが早い。あとC++をよく知っている。
それと、DPだなとかフローだなとか思ってもちゃんとコードに落とせなかったり、2日目のL問題はsegment木を書くのに手こずって結局時間切れになってしまったりしたので、典型問題はもう少し解き慣れておくべきだなと思いました。
もうちょっと解けるようになると競プロは楽しくなりそうです。あと関係ないですがみんなインターンとか頑張っていたので頑張らないとという気持ちになりました。
TensorflowのBatch Normalizationについてのメモ
TensorflowのBatch Normalizationでハマったのでメモしておきます。
あるモデルで訓練時はうまく学習されているのにテスト時にはひどい出力を出されれるということがありました。重み共有とかいろいろとしていたので原因を探すのに時間がかかったのですが、問題はBatch Normalizationでした。
TensorflowでBatch Normalizationを使用する方法は複数ありますが、もっとも簡単な方法はtf.layers.batch_normalizationを使う方法らしいです。
https://www.tensorflow.org/api_docs/python/tf/layers/batch_normalization
is_trainingフラグによって訓練時（Trueのとき）には平均と分散の計算を行うのに対して、テスト時（Falseのとき）には学習された値を使うという制御を行っています。これがFalseになっているときに正しく動いていなかったようです。
原因は単純で、Batch Normalizationの変数が学習されていなかったようです。上のページに書いてある通り、Batch Normalizationの更新は明示的に指定しないといけないことになっています。面倒です。
Note: when training, the moving_mean and moving_variance need to be updated. By default the update ops are placed in tf.GraphKeys.UPDATE_OPS, so they need to be added as a dependency to the train_op. For example:
update_ops = tf.get_collection(tf.GraphKeys.UPDATE_OPS)
with tf.control_dependencies(update_ops):
train_op = optimizer.minimize(loss)
僕はここに書いてある方法をそのまま書いていたのですが、なぜか学習されていませんでした。今も原因は分かっていません・・・
結局いろいろと調べている中で下の記事にある通りupdates_collections=Noneとしたら正しく動きました。このように指定すると上のような書き方をしなくてもその場で更新されるようになるらしいです。学習が遅くなると書いてある記事がありましたが、とりあえず僕のモデルは動いたので良いことにします。
結局原因は分かっていないのですが、Batch Normalizationは良く使うのでメモとして残しておきます。
GTX1070入りパソコンを作ってもらいました
ずっと深層学習ができるパソコンが欲しかったのですが、ついに9月6日に購入しました。
かわいいですね。
そろそろパソコン欲しいなという話をしたら↓の人ともう一人の友達が僕の知らない間にパーツを買って僕の家に来て30分くらいで組み立てて帰って行きました。僕は詳しくないのでありがたかったんですが、今後は軽率にパソコンが欲しいとかいう発言はしないようにします。
構成は以下のようになっているらしいです。良く分からないですがGTX1070が力を発揮できて予算は15万くらいという相談をしていたので、そういう構成になっているだろうと思います。
| OS | Ubuntu 16.04 LTS |
| CPU | Core i7 7700 |
| GPU | ZOTAC GeForce GTX 1070 Mini 8GB |
| MB | H110M-HDV |
| メモリ | W4U2400CM-8G |
| SSD | Crucial MX300 275GB |
| 電源 | NE550C |
| ケース | Fractal Design Core 1500 |
GPUの性能比較の流儀は知らないですが、とりあえずTensorflowのmnist_deep.pyで時間を計測してみました。
時間がかかりそうだったので1000epochで学習しています。変数の初期化から学習終了まで（with tf.Session() as sess:で囲まれている部分）を計測しました。比較対象はMacBook Air（4GB、13-inch、Early 2015）です。
ざっくりとした測定ですが、およそ50倍の速度が出ているようです。すごい。
| 機種 | 時間 |
|---|---|
| MBA | 311s |
| GTX1070 | 6.04s |
楽しい深層学習ライフが送れそうです。
ベルマンフォード法の負閉路検出について
常識だと思いますが、メモしておきます。
ベルマンフォード法は単一始点最短路問題をO(VE)（V：頂点の数、E：辺の数）で解くことが出来る手法です。ダイクストラ法と比較して、負の辺が含まれていても正しい解が求められることが特徴です。
ただし、始点から到達できる負閉路（含まれる辺のコストの和が負になる閉路）が存在する場合はいくらでもコストを小さくすることができるので、解を求めることはできません。そのため、負閉路を検出する必要があります。
以下のように（蟻本に書いてあるように）グラフを構成してベルマンフォード法を書いたとします。
#include<iostream> using namespace std; #define REP(i, n) for(int i=0; i<n; i++) #define ll long long struct edge{ int from, to; ll cost; }; ll INF = 10e17; edge es[2000]; ll d[1000]; int V, E; void shortest_path(int s){ REP(i, V) d[i] = INF; d[s] = 0; REP(i, V){ REP(j, E){ edge e = es[j]; if(d[e.from]!=INF && d[e.to]>d[e.from] + e.cost){ d[e.to] = d[e.from] + e.cost; } } } }
閉路を求める方法として、蟻本では以下のような方法が紹介されていますが、これを使うときは注意が必要です。
蟻本に明記されている通り、このコードは始点から到達可能か否かにかかわらずグラフ内に負閉路が存在すると真が返されます。問題において単一始点からの距離を求めたいだけであれば、到達できない負閉路を検出する必要はありません。
// type A bool find_negative_loop(){ REP(i, V) d[i] = 0; REP(i, V){ REP(j, E){ edge e = es[j]; if(d[e.to]>d[e.from] + e.cost){ d[e.to] = d[e.from] + e.cost; if(i == V-1) return true; } } } return false; }
到達出来る閉路のみを求めたい場合はどうすれば良いでしょうか。
到達可能な負閉路が存在しない場合の最短路は最大でもV-1個の辺から成るのでV-1回の更新によって到達可能な頂点への最短距離が求められることがわかります。しかし、到達可能な負閉路が存在する場合は何回でも更新が起こるので、V回目の更新が発生します。よって、上記のベルマンフォード法の関数でV回目の更新が起こったら真の値を返すようにしておけば閉路を検出することができます。
// type B bool shortest_path(int s){ REP(i, V) d[i] = INF; d[s] = 0; REP(i, V){ REP(j, E){ edge e = es[j]; if(d[e.from]!=INF && d[e.to]>d[e.from] + e.cost){ d[e.to] = d[e.from] + e.cost; if(i == V-1) return true; } } } return false; }
これで解決といいたいところですが、まだ注意すべき場合があります。それは、目的地が決まっている場合です。
ベルマンフォード法は到達可能な負閉路が存在しなければ単一始点から任意の点への最短距離を求めることができますが、ある点への最短距離が知りたいだけであれば到達可能な負閉路が存在していても距離を求めたい点が負閉路に含まれていない場合は正しく最短距離を求められます。
ある点が負閉路に含まれる場合は、高々V-1回の更新によって到達可能な全ての点への最短距離が求められたのちに、高々V回の更新によって再度その点の最短距離が更新されることになります。よって、V回目から2V回目の更新で目的地の最短距離が更新されなければ目的地を含む負閉路は存在しないことが分かります。よって、この場合には以下のコードによって負閉路を検出することができます。
// type C bool shortest_path(int s, int t){ // t: destination REP(i, V) d[i] = INF; d[s] = 0; REP(i, 2*V){ REP(j, E){ edge e = es[j]; if(d[e.from]!=INF && d[e.to]>d[e.from] + e.cost){ d[e.to] = d[e.from] + e.cost; if(i>=V-1 && e.to==t) return true; } } } return false; }
実際のグラフに対しては以下のように判定されます。いずれも始点が1、目的地が7です。
- typeA：負閉路あり
- typeB：負閉路なし
- typeC：負閉路なし
- typeA：負閉路あり
- typeB：負閉路あり
- typeC：負閉路なし
考えてみると当たり前ですが、問題を解くときに間違えないようにしたいですね。僕はさっき間違えました。
AOJ-ICPCカテゴリー分け
AOJ-ICPCの問題で僕が解くときに使った解法（アルゴリズムなど）をまとめておきます。
僕が使った（または調べたら出てきた）というだけで、最適なのかは分からないのでご了承ください。 解けるとは思います。 空欄は特に典型的な手法を使ったつもりがないものです。 僕が知らないだけで何か名前があるかもしれません。
項目名を押すとソートできます。 「Search:」に入力するとフィルターできます。
| 難易度 | 問題 | 種類 | 補足 |
|---|---|---|---|
| 250 | Pollock's conjecture | DP | |
| 250 | Square Route | ||
| 250 | Fastest Route | DP | bit DP |
| 250 | Differential Pulse Code Modulation | DP | |
| 250 | The Secret Number | DP | |
| 250 | Cubist Artwork | ||
| 250 | Minimal Backgammon | DP | |
| 250 | Expected Allowance | DP | |
| 250 | Koto Distance | 累積和 | |
| 250 | Manhattan | ||
| 250 | Squeeze the Cylinders | DP | 幾何 |
| 300 | Cut the Cake | ||
| 300 | Gather the Maps! | ||
| 300 | Princess in Danger | Warshall–Floyd法 | Dijkstra法 |
| 300 | Building a Space Station | Union-Find木 | 幾何 |
| 300 | Building a Space Station | 幅優先探索 | |
| 300 | Mirror Cave | 幅優先探索 | |
| 300 | Vampire | 幾何 | |
| 300 | Balloon Collecting | DP | |
| 300 | Line Gimmick | ||
| 350 | Curling 2.0 | 幅優先探索 | |
| 350 | Identically Colored Panels Connection | 幅優先探索 | |
| 350 | Twirling Robot | Dijkstra法 | |
| 350 | Biased Dice | ||
| 350 | And Then. How Many Are There? | bit DP | |
| 350 | Starting Line | ||
| 350 | Sleeping Time | 二分探索 | |
| 350 | For the Peace | ||
| 400 | Cards | 二部マッチング | |
| 400 | Brave Princess Revisited | Dijkstra法 | |
| 400 | Restrictive Filesystem | ||
| 400 | Milky Way | 幾何 | Warshall–Floyd法 |
| 400 | Encryption System | ||
| 450 | Circle and Points | 幾何 | |
| 450 | FizzBuzz | 二分探索 |
使ったもの
競技プログラミング サイト集
競技プログラミングに関するサイトのメモです。
問題のジャンル分け
主にICPCの問題のジャンル分けをしてくれているサイト。解く問題を選ぶときに参考にしている。
AOJ ジャンル分けメモ - ひよっこプログラマのプログラミング
幾何問題
ライブラリ
幾何ライブラリ
カンニング
データ構造などをカンニングする。
アルゴリズム コード集
Spaghetti Source - 各種アルゴリズムの C++ による実装
Union Find木・パケット法・平方分割・セグメント木
Dijkstra法
コンテスト
AtCoder Virtual Contest
AtCoderの過去問を仮想コンテストで解けるというサイト。 僕は1問解くのに平気で3時間とか掛けてしまうので、スピードをあげる練習には良さそう。
競技プログラミングを始めた
前からほんの少しやってすぐに飽きていたんですが、今回はKPCCというサークルでみんなでやろうという感じなので少し頑張ってみたいと思います。 解いた問題とかのメモをします。
AOJ-ICPC一日一AC、毎週AtCoder参加がノルマです。
8月3日
8月4日
8月5日
8月6日
8月7日
僕が解法に悩んでいた問題がだいたいDPということを神野さんに教えてもらった。 DPは知っているんですが、未だに使いこなせない。 適当に簡単な問題を解いてみた。
あと、下のDPの問題を解いてみようと思ったらTLEになったので、仕方なく他の方が解いた回答を見たらほぼ同じだったのでPythonのせいで通ってないみたいですね・・・。 ここまで慣れているPythonで書いていたのですが、そろそろ限界みたいです。
8月8日
やっと今日はC++で書きました。無限に時間がかかりました。
今日得た知見としては、小さすぎる値で「2.82327e-09」とか出力されるとWA扱いになるみたいですね。iostreamで出力する場合は下のような感じでやるみたいです。少し面倒ですね。もう少しいい方法があると良いのですが。
cout << fixed << setprecision(6) << dp[T][N] << endl;
【Proton.jp】 C++：マニピュレータを用いた数値の整形
KCPPのLT会で使ったスライドです。
8月9日
解法はすぐに思いつくような問題ですが、string型の数字を比較する方法など、C++の書き方で丸一日悩んでしまいました。結局string型の数字を比較するのは以下のように関数を作ることにしました。compareの挙動も分かりづらいです。
bool former_is_bigger(string a, string b){ if(a.size() > b.size() || (a.size() == b.size() && a.compare(b) >= 1)){ return true; } else { return false; } }
8月10日
簡単な問題ですが、C++でpair、sort、vectorを初めて使った。慣れない。
8月11日
DPで解くらしいが、制約が緩いので愚直に書いたら通ってしまった。勉強にならなかった。
8月12日
幅優先探索するだけなので1時間で解いてDijkstra法の勉強をするつもりだったが、無限にバグらせて時間がなくなった。 はじめてMLEが出た。 正直メモリをどれくらい使うのか意識していなかったが、地図ごとキューに入れるみたいな頭の悪いことをすると出てしまうみたい。
構造体やtypedefを初めて使った。 関数が配列を返せないのはとても不便。
D問題が解けなかった。 難しくはなかったが、僕の手が遅い。 あとは木の扱いに慣れてなさすぎるので、頑張りたい。
8月13日
簡単な問題を解いてDijkstra法をやるつもりだったが、やる気がなくなった。
8月14日
今日こそはDijkstra法をやる。
8月15日
Dijkstra法の問題が解けなかったので、とりあえず1問解いておいた。 最近、なかなか問題が解けない。 つらい。
今日もLT会がありました
8月16日
BitDP。やり方が分からず、かなり答えを見てしまった。 しかしだいぶビット演算の扱いが分かったので良かった。
O(n2)程度が限界。
普通のDP。
今日は実装が軽い問題を3個解いた。 練習としては良かった。 しかしDPは割とできるようになったので、最短路やグラフの問題を練習したい。
普通にユークリッド距離が1のときにマンハッタン距離が2になるということが数日分からなかった（頭が悪い）
8月17日
Segment木を初めて使った。 僕は無限に時間を使って書いたんだけれど、想定解は累積和というものを使うらしく、無限に頭が良かった。
AOJ 2600: Koto Distance - 宇宙ツイッタラーXの憂鬱
DP。 特定のテストケースだけWAが出るので原因が分からずにいたが、最初と最後の壁の処理で間違えていた。
愚直に解けばO(N)で間に合う。 調べたところ方針は現地点の左右の>と<の個数を数えるということで合っているみたいだが、 書き方が雑だったのでパネル数のカウントがややこしくなってしまった。
AOJ-ICPCの問題の横にある☆マークは良問であることを表しているらしく、この問題は星が7個もついているので解いてみたが、とても簡単だった。
幾何。簡単。
ICPCで解ける問題が減ってきたので、最短経路問題やフロー問題の典型題を解いていきたい。
8月18日
二分探索。 愚直にやるとO(230)でつらい。 いろいろ試そうと思ったけど、軽く枝刈りしたら通った（良くない）。
8月19日
幾何問題。 簡単だと思ったら、二つの円の交点を求めるところでつまずいた。 普通に調べてしまったけど、割と面倒だったのでこういうのをライブラリとして用意しておくんだろうか。 これくらいは導出しろという感じなんですかね。 分からない。
Dijkstra法。 簡単だけど、自分で書いたコードと人のブログに書いてあったコードがほぼ同じだったので嬉しい。
Warshall–Floyd法の練習。 Warshall–Floyd法そのままの問題。
最大フロー問題の練習として、二部マッチング問題を解いた。 ほぼ蟻本写経になってしまったし、最大フローを空で書けるようになるのは遠そう。
8月20日
とても簡単な問題だったがなぜか通らず、スタックを毎回クリアするのを忘れていた。 これに一時間くらい気付かず、辛い気持ちになった。
C++のstring型の扱いがわからず、B問題で時間を使ってしまった。 そのせいでD問題は方針はあっていたのに時間切れになった。
8月21日
二分探索。 問題自体は簡単だったが、C++の言語仕様が分からなくてpowをバグらせてしまった。 longの範囲でpowを扱いたいときには入力をlongにしないといけない。 考えてみればそうなのかもしれないが、このミスで時間を溶かした。
少し面白い最短路問題。 冷凍施設のない街を取り除き、時間がMより長くかかる道を取り除けば普通にDijkstra法になる。 しかも、計算量に余裕があるのでWarshall–Floyd法で良い。 取り除くところもO(N3)使えれば楽なので、そこも含めての優しさなのかな。
Dijkstra法。 Highway Express Bus | Aizu Online Judgeとほぼ同じ問題。
8月22日
考えることが色々とあるが、O(NL)で良いので丁寧に条件に合わせて書くだけ。 それでも無限にバグらせるので反省したい。
一応幾何問題でしょうか。 貪欲法でもあるしUnion-Find木問題でもある。 O(N3)で余裕があるので面倒臭がってUnion-Find木を使わずに解いたが、 結局そこの処理をバグらせてしまったので使った方がよかった。
8月23日
条件が色々とあるが、ただのDP。
それは良いのだが、dpの初期化で範囲を間違えて一つ外側まで指定していたのに手元ではエラーがでず、AOJでもエラーではなくWA扱いになってしまっていたのでハマってしまった。
頭が悪いので幅優先探索を4個書いた。
まだC++は分からないことが多い。 配列渡しを初めて使った。
8月24日
Dijkstra法。 これは面白い問題だったと思う。
高々24枚だからメモ化して全探索した。 こういうと聞こえは良いが、最初は普通に探索しきれるだろうと適当にやったら同じ状態をなんども踏んでTLEにすらならずREを出された。 結局状態をbitでメモしたので、bitDPの方が明らかに良かった。
8月25日
頑張って書いたら通った。 おそらく調べてみた感じでも頑張って書くしかない。
8月26日
幾何問題。 幾何ライブラリが活躍する問題だったので、幾何ライブラリを作った。 写経しただけだけれども。 幾何ライブラリがあれば、あとはひたすら距離を測るだけ。 問題としては面白くはない。
ルールに則ってひたすら頑張る。 空間・時間ともに計算量に余裕がありそうなので、多めに候補をとって最後に暗号化して一致するか判定した。 復号化よりも暗号化の方が楽なので、結果的には良い方針だったかもしれない。
無念の1完。あとで解説をみたらBとCは方針が惜しかったので、次回は3完を目指したい。
8月27日
もはや競プロの問題ではない。解いていた問題が解けなかったので消化。
しばらくABCを埋めていきたいと思う。一応時間を計って行う。A、B、C問題はすぐに終わったが、D問題で悩んで結局1時間ほど使ってしまった。
D問題、アプローチは正しかったがパスを求めるのにDijkstra法を使ったらTLEになってしまった。実装があっていれば通る気がするのでどこかで無駄な事をしているかもしれない。木であれば単純に探索をすれば良いということに気づかずにDijkstra法などを使うというミスを何回かしているので気をつけたい。
C問題でTLEを出した。文字列結合は時間がかかるということを学んだ。
肝心のD問題をまた通すことができなかった。方針はわかったが、二項係数の余りの出し方がわからなかった。意外とD問題を通すことができない。つらい。
8月28日
今日もABCをやりたかったので消化問題。
久々に時間内にABC全完できた。1時間29分くらい。たかがABCでも嬉しい。
しかしB問題でなぜか1回で行ける場合を飛ばしてWAを出して時間を食ってしまった。こういうケアレスミスが多いのをなんとかしたい。
簡単な回だった。 C問題で例をちゃんと見ていなかったので色が8種類しかないと勘違いしてWAを出して結局45分かかってしまった。
8月29日
完全に頭が悪いので二分探索という発想に至らずD問題が解けなかった。
8月30日
探索するだけ。
8月31日
最初の面を決定する効率の良い方法があるのか少し考えたが、結局全て列挙した。他の人もそのようにやっている人がいたので良い方法はないのかもしれない。
D問題、最小値をlogNで求めたいから・・・segment木か。という頭の悪い発想のせいで時間内に実装できなかった。普通にヒープで良いじゃん・・・。
9月1日
ベルマンフォード法を使うだけの問題だが、ベルマンフォード法は意外と使わないので初めて書いた。そのため、負閉路判定でバグらせて悲しい気持ちになった。
A、Bを1時間ほど掛けて解いたが、Cが解けなかった。
9月2日
またD問題が解けなかった。想定解ではないものの方針は正しいと思うが、REとWAが二個ずつでてしまった。想定解は頭が良いですね。
またD問題が解けなかった・・・。必勝法を見つける問題はとても苦手。
参加。69位。ABC久々に全完できたので嬉しいけど、簡単な問題だった。D問題でtypoに気づかずにWAを出してしまったのが悔やまれる。
9月3日
いい加減、AB問題を解くのが面倒なのでARCを解くことにしたが、D問題すら解けなくて辛い気持ちになった。
D問題は部分点解しか得られなかった。方針としては惜しかったが、コードに落としこめなかった。計算量を減らす方法が複数あり、問題としては面白かった。
9月4日
C、D問題は解けた。簡単な回だったが、Dの実装が悪くてかなり時間をかけてしまった。
9月5日
C、Dは簡単だが、E問題は解けなかった。解説を見ても自分で解ける気があまりしなかった。E問題を解けるようになるにはもう少しかかりそう。
簡単な回だったようで、E問題もDPだろうとは思ったが解けなかった。DPはだいたい解けると思っていたので悲しくなったのでtypical DPコンテストでもとこうと思う。
9月6日
9月9日
Cしか解けなかった。Dは解説によると途中からは典型らしい。
一応全完できたが、単純ミスで2WA2REを出してしまった。問題としては簡単な回だったので反省したい。特にD問題は制約が8だからbit DPだろうという短絡的な発想をしてしまったが普通に全探索できた。bit DPをバグらせて2REを出しているので、簡単な方針を立てられるように心がけたい。
あとやっと緑コーダーになった。とりあえず早くシアンになりたいですね。
9月10日
E問題が解けそうで解けなかった。先に集合を作ろうという発想はあったが、座標の45度回転をしていなかったので順序集合で重複なく集合を作る方法が思いつかなかった。そのあとの二分探索もおそらく思いつかないだろう。実装としても僕からすると大変そう。やはりE問題はもう少し鍛錬が必要みたい。
9月11日
D問題が解けなかった。ゲームの勝敗問題は苦手。しかしE問題が簡単だったので解けた。簡単だったのでなんとも言えないが、E問題は初めて解けたので嬉しい。
9月12日
E問題も簡単だが、実装が悪くて間に合わなかった。
9月13日
久しぶりにAOJ。この問題はなかなか難しい。
9月14日
前は難しいかと思っていたが簡単だった。しかしbit演算をバグらせて時間がかかってしまった。
桁DP。
9月16日
E問題は方針が思いついたのが終了10分前くらいだったので解けなかった。 C、D、Eともに考察に時間を掛けすぎなのでなんとかしたい。
レート1117になった。次回シアンにいけるといいです。
9月18日
Raven38さんとcaretくんと出ました。僕はCを解きました。
9月19日
チームとしてはたくさん解けていたので楽しかったが、思い返すと僕はEしか解いていない・・・。
9月20日
Bを書いたら何故か無限にWAを出されて、2時間くらい悩んだ末にcaretくんからの提案でpython3で書いたら通った。c++とは分かり合えない。
9月23日
Dが解けなかった。想定解、頭良いですね・・・。マンハッタン距離問題は多いのでこういう考え方に慣れたいです。
あと水色コーダーになりました。わーい。