0x19fの日報

なるべく毎日書きます

8/11 AtCoder Regular Contest 080

この前うっかり寝過ごしてで損ねたARC080を解いた.

  • C: 4-adjacent - AtCoder Regular Contest 080 | AtCoder [解答]

    数列の要素を自由に並び替えて隣り合う要素の積が4の倍数になるようにできるか判定する問題. Aiが奇数, (4の倍数でない)偶数, 4の倍数で隣に置かなければならない数の条件が変わることに注目する. Aiが奇数なら, 隣には必ず4の倍数をおく必要がある. Aiが偶数なら, 隣には偶数をおく必要がある. Aiが4の倍数なら, 隣におく数はなんでも良い. ここから考えると, { 奇数, 4の倍数, 奇数, 4の倍数, ..., 4の倍数, 偶数, 偶数, ... }みたいな並びが作れるかを判定すれば良いことになる.
  • D: Grid Coloring - AtCoder Regular Contest 080 | AtCoder [解答]
    1, 1, 1, 2, 2, 3, 3, 3, 3, ...., N, N, Nと左上から順に要素数H * Wのマス目を埋めていき, 奇数番目の行だけreverseして表示すればOK.

  • E: Young Maids - AtCoder Regular Contest 080 | AtCoder [解答]
    辞書順で最小のものを構成するのは後ろから考えるとやりづらいので, 先頭から小さい数字を順に決めていくことを考える. 最初の状態からqの先頭2つの要素を決めるのには, 偶数番目の要素でもっとも小さい値とその要素以降で奇数番目の要素を取るのが最良. この二つの要素がpのi, j番目だとすると, pは[0, i), [i + 1, j), [j + 1, N)の3つの要素に分断される. qの次の2要素はこの3つの領域の偶数番目の値から最小のものを選ぶことになる. これを繰り返していけばO(N^2)でqを求めることができる.
    ここから計算量を落とすためには, 偶数番目/奇数番目の要素から最小を求めるのにセグメントツリー, 分割された領域からどれを選ぶかはpriority_queueを用いればよい. 具体的な手順としては,
    1. { [0, N), min_odd }をpriority_queueに入れる
    2. priority_queueから最小のものを取り出す
    3. 3つの領域に分割して, それぞれをpriority_queueに入れる
    4. priority_queueが空ならループ終了, そうでないなら2に戻る
    という感じ. 結構実装がしんどかった...

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-lualua付きでコンパイルされる. 途中pyenvと何かがコンフリクトしたっぽく, インストールするときだけ.bash_profileからpyenvのパスを通している部分をコメントアウトした.

 

他に最近ほしいなと思った機能が, vimcsvファイルを開いた時にコンマで整列させるスクリプトとか. これないとさすがにデータの中身を覗くのがしんどいので. 今は普通に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起動しなくなるものなんですねぇ......