0x19f (Shinya Kato) の日報

主にプログラミング関連の話をします

8/8 束の間の夏休み

8/3で無事に春学期の期末試験を全て終えて夏休みに突入した. しばらくは休養がてらアニメ見たりして過ごしてた. 昨日から大学の夏期集中講座でまた学校に来ている. なんだかオープンキャンパスで高校生がいっぱいいたり, 何かのイベントで小学生がいっぱいいたりして普段とはかなり違う雰囲気.

 

AtCoder

  • B: Colorful Creatures - AtCoder Grand Contest 011 | AtCoder [解答]
    スライムがN個あってそれぞれの大きさA[i]が与えられている. スライムは自分の大きさの2倍以下の大きさのスラムを吸収してその分大きくなることができる. こうしてスライムが吸収を繰り返して最後に残るスライムが1個になる時, 最後に残るスライムは何通り考えられるかという問題.
    とりあえず, 大きさの昇順にソートして考えてみる. 昇順に並んでいれば, i番目のスライムは1からi - 1番目までのスライムを吸収することができる. i番目のスライムがそれら全てを吸収すると大きさは, A[1]からA[i]までの和sumとなる. この時A[i + 1] <= sum * 2であればi番目のスライムがi + 1番目のスライムを吸収することができる. A[i + 1] > sum * 2であれば, どう足掻いてもi番目のスライムは全てのスライムを吸収することはできない. よって, A[i + 1] > sum * 2となる最大のiを探せば, 答えはN - iとなる. そのようなiが存在しない場合は答えはNとなる.
    実際の実装では降順にソートして, A[i] > sum(A, A + i - 1)となったところでループを抜けるって感じにしてます.

  • B: Mysterious Light - AtCoder Grand Contest 001 | AtCoder [解答]
    光が2個めの反射点に辿りついた直後, 残っている正三角形の領域は平行四辺形になっていることに注目すると考えやすい. このあと何度か光が反射すると再び平行四辺形ができる. この時, 何回光が反射すると次の平行四辺形になるかは二つの辺の長さから計算できる. また, 次の平行四辺形の辺の長さも同様に計算できる. 具体的には辺の長い方をa, 短い方をbとするとa = b, b = a % bになる. これを見てわかる通り, 辺の長さはlogで減っていく. イメージとしてはユークリッドの互除法みたいな感じ. これをbが0になるまで繰り返す.

7/30 ISUCONの練習始めました

今年こそISUCONに出たい

前々からISUCONにチャレンジしてみたいなぁーと思っていたのもあって, 今年こそはちゃんと練習しようと思っています. 夏休みに入って時間も取れるようになってきたので.

とりあえず, Vagrant使って過去問を触ってみる. ISUCON過去問とほぼ同じサーバー環境をVagrantで構築するためのVagrantファイルを公開してくださっている方がいるので, それを使う. 圧倒的感謝.

d.hatena.ne.jp

github.com

環境構築の手順

リポジトリをgit cloneして立ち上げたい問題のディレクトリに移動, vagrant upするとサーバーが起動する. ちなみに, 起動には結構時間がかかるので注意. あと, なぜかISUCON6のqualifyはうまく立ち上げられなかった. というわけで, isucon5-qualifyを立ち上げてとりあえずベンチを取ってみるところまでメモしておきます.

1. Virtualbox, Vagrantのインストール
brew cask install virtualbox
brew cask install vagrant

すでにインストールしている場合は, バージョンが古いとエラーが出ることがあるようなので再インストールしておくといいと思います.

brew cask reinstall virtualbox
brew cask reinstall vagrant
2. Vagrantfileが入っているリポジトリをcloneしてくる.
git clone https://github.com/matsuu/vagrant-isucon.git
3. 立ち上げたい問題のディレクトリに移動してvagrant up
cd vagrant-isucon/isucon5-qualifier/
vagrant up

これが結構時間かかります. 気長に待ちます. 諸々の準備が終わるとimageというサーバーとbenchというサーバーが起動しているはずです. きちんと把握してないですが, imageは問題を解く用, benchは負荷走行用かなと思っています. おそらく, 予選本番ではimageの方だけが参加者には与えられていて, benchサーバーにはベンチマーク取ってくださいってリクエストをするだけなのかと.

もしかしたらstandaloneは両方立ち上げないのかも. そうだとしたらそっちの方が早く起動できる(？).

4. imageサーバーにsshで接続する
vagrant ssh image
5. ユーザーを切り替える

ログインするとvagrantユーザーになっていると思うので, isuconというユーザーに切り替えます.

sudo su - isucon

そこでlsしてもらうといろいろファイルがあるのがわかると思います. 基本的にはアプリケーションなどの中身は/home/isucon以下に置かれてます.

6. とりあえずベンチを取ってみる

/home/isucon以下にbench.shというスクリプトがあるのでそれを実行します.

./bench.sh

しばらく待っているとベンチが終わって, 以下のような結果が標準出力に出てきます. これがスコアになるようです.

...
Isucon5Checker
done
success
114.1
{"success"=>206, "redirect"=>81, "failure"=>1, "error"=>0, "exception"=>0}
アプリケーションが 3000 ミリ秒以内に応答しませんでした

ここからやること

基本的にはNginxとMySQLのログを見ながらボトルネックになっている箇所を探していくことになるかなぁと考えています. MySLQはベンチ取った時のログをざっと見る限りでは結構N+1クエリがありそう. 他にもいくつか時間かかっているクエリもあったのでそのあたりを中心に見ていくことになりそう. あと, 実際にブラウザからアクセスもしてみるとどういうお題なのかわかりやすくていいかなぁと.

チームメンバーに競プロerがいるので, C++でゴリゴリ書き直すみたいな戦略も面白いかなぁって思っている. ちなみに, 昨年はC++で予選を突破したチームが1つだけいた模様. と思って調べてみたらまさかのこのチームで爆笑してしまった.

ISUCON6予選をC++で参加して予選通過した話 - いもす研 (imos laboratory)

さすがに自前でC++のWebサーバーを作るのは険しすぎるのでC++でCGIとか作ってみるのはどうかなぁなんて考えているところ. どれぐらい速度出るか全くわからないけれど.

7/29 ARC079

AtCoder Regular Contest 079

C, Dを解いて2完. Eはにぶたんとかいろいろ試したけれどダメだった. Fは問題さらっとしか読んでないです.

  • C: Cat Snuke and a Voyage - AtCoder Regular Contest 079 | AtCoder [解答]

    島1から繋がっている島すべてに対して, Nと繋がっているかどうかを調べる.

  • D: Decrease (Contestant ver.) - AtCoder Regular Contest 079 | AtCoder [解答]
    K回操作を行った後に0, 1, 2, 3, ..., N - 1という長さNの数列になるような数列を作る. 1回操作を行ってこの数列が得られるような列の中にはN, 0, 1, 2, ..., N - 2という列がある. 同様に, 2回操作を行ってこの数列が得られるような列の中にはN - 1, N, 0, 1, ..., N - 3というものがある. これを一般化すると, A[i] = K / N + (N - i - 1) + (i < K % N)とすれば良い. Nはとりあえず50にしておいた.

  • E: Decrease (Judge ver.) - AtCoder Regular Contest 079 | AtCoder [解答]
    最大になるものを選んでとあるが, 実は操作する順番を変えても答えは一緒になる. なので, A[i]がN未満になるまで減らして他の要素には+1をするというのを全要素がN未満になるまで繰り返せば良い.
    コンテスト中は二分探索をしようと思ったのだけれどどうやら, 解の付近で単調性が崩れるらしくて正しく答えが求められなかった. ちなみに, 解の範囲をある程度絞った後で範囲のしたから解を探すってことをしたら通った(提出コード).
    周辺まで見る二分探索をしているレッドコーダーの方もいたみたいで, その正当性をTwitterで話していたけれど正直よくわからなかった.

7/27 久々に.vimrcを整理したい

今までずっと補完というものを使わずにプログラムを書いてきた. なのだけれど, 英単語のスペルミスがあまりにも多かったり, 特定の単語を特定の間違い方することが多いので補完を使ってみることにした. とりあえず, vimの標準の補完機能(ctrl + p)を使ってみたけれど, 普通に慣れていないと押すのを忘れそう. というわけで, NeoCompleteというプラグインを入れてみた.

github.com

 

設定を.vimrcに書いておけば, プログラム書いてると勝手に補完窓が出てくるのでひたすらTabを押せばOK. これなら慣れてなくても使えそう. あとは言語ごとに辞書ファイルとか追加しておくと便利そう.

ちなみに, このプラグインはluaを使っているらしく, 自分の使っているvimにはluaを入れていなかったため, brewでインストールし直した. brew install vim --with-luaでlua付きでコンパイルされる. 途中pyenvと何かがコンフリクトしたっぽく, インストールするときだけ.bash_profileからpyenvのパスを通している部分をコメントアウトした.

 

他に最近ほしいなと思った機能が, vimでcsvファイルを開いた時にコンマで整列させるスクリプトとか. これないとさすがにデータの中身を覗くのがしんどいので. 今は普通にExcelでファイルを開いているけれど, csvの中身を見るためだけにいちいちExcel起動させるの面倒だし.

その他でvimrcをきちんと整理したいと思っているのが, quickrunの設定. 何かの言語を実行する時に非同期実行だと結果がうまく得られなくてオフにしているのだけれど, やっぱりほしいなと.

7/24 AGC018とか

AtCoder Grand Contest 018

安定の1完(). A問題が難しくて普通にお葬式になるところだった. Bは言われれば貪欲だなぁ〜って感じ.

 

ABC/ARC D問題埋め

  • D: No Need - AtCoder Regular Contest 070 | AtCoder [解答]
    部分点解法は, ある1枚のカードを抜いて部分和を列挙する. 和がK未満の部分集合に抜いたカードを入れて和がK以上になれば, そのカードは不要ではない. 抜くカードの選び方がN, 部分和の列挙がO(NK)なので, 全体で計算量はO(N^2 * K).
    満点解法は, しばらく考えたのだけれどわからなくて解説を見てしまった. 実はカードを書かれている数字の昇順でソートすると, カードiが不要ならカード(i - 1)も不要となる. なので, 必要なカードと不要なカードの境界を二分探索する. もちろん, 二分探索の判定部分では部分和のDPをする. 全体としての計算量はO(logN * NK)になる.

7/23 OS自作をしていたらWindowsが起動しなくなっていた

ここ最近結構時間を費やしてOS自作入門を読んでHaribote OSを写経したりしていたのだけれど, せっかくだから実機でも動かしてみたいなと思ってUSBにディスクイメージを書き込んで起動させようとしたら, Windowsが起動しなくなっていたことに気づいた.

 

代わりになぜかHaribote OSが起動する()

 

ほとんどはMac上でエミュレータを使って挙動を試していたのだけれど, その環境を構築する前に一瞬だけVAIOで2, 3日分ぐらい試していたので, その時に間違ってHDDにイメージを書き込んだのかなぁと. だとしたらmake installみたいなので書き込まれたんですかねぇ. 自分の性格的に特に意味もなくコマンド実行してたりする可能性は全然あるんだよなぁ. まぁ, その辺中身が何をしているのかあんまり理解してないのでアレですが.

 

運のいいことに, このVAIO自体にはほとんど大切なデータとか入れてなくて, Windowsも10への無償アップグレードをし損ねたWindows 7で, ほとんど壊れても問題ないマシンとして扱っていたのでそこまで痛手ではないのだけれど...

 

さらにいろいろ試していたら, デュアルブートさせていたUbuntuの方は起動できたのだけれど, なぜかキーボードから特定の文字だけが入力できない. そのためパスワードが入力できなくてログインできない.

 

それにしても, ブート関連の場所ってほんのちょっと書き換えただけでもOS起動しなくなるものなんですねぇ......

7/22 ソフトウェア工学と言語処理系の期末おわり

ソフトウェア工学は微妙, 言語処理系はぼちぼち(？).

ソフトウェア工学は正直ただの暗記ゲーで内容的にもそんなに面白いものではないので退屈だった.

言語処理系はちゃんと勉強してみると面白かったのだけれど, もう少しちゃんとしたレジュメ配って欲しいっす.

あと, 試験問題はバリエーションがなくてめちゃくちゃ退屈.

 

ABC/ARC D問題埋め

  • D: Alice&Brown - AtCoder Regular Contest 072 | AtCoder [解答]
    MiniMaxで全探索するプログラムを書いて0 <= X, Y <= 20ぐらいの答えを全部試してみたら, |X - Y| <= 1の時はBrownが, それ以外の時はAliceが勝ったのでそこから答えを推測.
    たまには試してみるのも大事ですね.

  • D: 井井井 / ### - AtCoder Regular Contest 071 | AtCoder [解答]
    あるi, jについてx = X[i], x = X[i+1], y = Y[j], y = Y[j + 1]で囲まれる長方形が何回足されることになるかを考える.
    これはこの長方形を含むような長方形がいくつあるかと同じなので, (i + 1) * (N - i - 1) * (j + 1) * (M - j - 1)と等しくなる.
    よって, 求める値は\sum_{i = 0}^{N - 1} \sum_{j = 0}^{M - 1} (i + 1) * (N - i - 1) * (j + 1) * (M - j - 1) * (X[i + 1] - X[i]) * (Y[i + 1] - Y[i]).
    この式をよく見るてiとjをそれぞれ総和と関係ないところから外すと, (\sum_{i = 0}^{N - 1} (i + 1) * (N - i - 1) * (X[i + 1] - X[i])) * (\sum_{j = 0}^{M - 1}  (j + 1) * (M - j - 1) * (Y[i + 1] - Y[i]))となる.
    あとは, X/Y方向の総和をそれぞれ求めて最後に掛け合わせれば, O(N + M)で求められる.

  • D: Maximum Average Sets - AtCoder Beginner Contest 057 | AtCoder [解答]
    平均の方は価値の降順にソートして, 先頭からA個の平均を求める.
    組み合わせの数は, 基本的にはコンビネーションを求めて足し上げるだけ.
    ソート列のA番目の値がN個の中にいくつ含まれるか(=d)と先頭からA個までの中にいくつ含まれるか(=c)を数える.
    平均を求めるときに, 2種類以上の価値のものを使っていれば答えはcombination(d, c).
    そうでない場合は, 全て同じ値を使う組み合わせをA個からB個まで足しあげれば良い.