ISUCON7予選参加記(初心者)

一昨日行われたISUCON7予選にICPC国内予選に出た時と同じ、dGFpc2VpeXVtYQというチームで出ました。

ISUCONには初参加でミドルウェアの知識はほとんどなかったのですが、ISUCON夏期講習に参加して面白そうだったのでチームメイトを誘って参加。ただ、チームメンアーの内2人はコドフェスの予選通過していたため、多分ISUCON予選通過しても本戦参加しないので気楽に参加してました。

言語は雰囲気でpythonを使いました。

結果は惨敗。ち〜ん。

その参加記をここに残します。

当日の流れ

深夜〜朝

KMCの部室で作業できるかと思っていたら、他のチームとの兼ね合いで厳しそうだったので、チームメイトの家で参加することになる。

9時過ぎ

チームメイトの家に集合する。他人の家に行くのは久方ぶりだったのでテンションが少し上がる。

9時半ごろ

どうやらコンテストが遅延するらしいとの情報が入ったので、ゼルダの伝説BoWを眺めたり、マリオカート8を3人でプレイするなどしてわいわいした。この辺のdiscordのリアクションの治安が悪くて面白かった。

11時半過ぎ

ご飯を食べに出かける。雨が降ってきてて悲しかった。

12時過ぎ

再びマリオカート8。13時にコンテストが始まるっぽいので、レギュレーションを読みながら備える。レギュレーションに複数サーバの存在を示唆する記述があり戦慄する。

13時13分〜

実は13時13分に始まらずに中途半端な時間に始まり、驚きながら開始。sshをしていたら、突然fail2banに拒否されるなどして辛かったが、テザリングなどで回避した。

前半

複数サーバ何もわからないのでappサーバ1台とDBサーバ1台でやって行くことにした。

とりあえず、alp等のツールを入れるなどしたりした後、なんやかんやでDBに画像バイナリが入っていてやばいことに気づき、app.pyを雑に編集してファイルに書き出す。その後DBに雑にインデックスを張るなどしたり、僕が知らない編集がなされるなどして、スコアが2倍ぐらいになった。

後半

椅子に座っただけ。

iconsがやばいのをなんとかしようと、nginxの設定を眺めた。nginxの経験が我々のチームにはほぼなかったこともあり、キャッシュの設定がうまくいかなかった。

何もわからなくなってきて雑に修正してベンチをかけまくっていた。

最終的に特に有効打を打てずにガチャを数回回して終了。

まとめ・結果

f:id:basemusi:20171023112054p:plain

最終スコアは19610だったはず。highestは2万点台。

惨敗という感じです。やっている最中はISUCONの雰囲気があり楽しかったですが、あまり成果が出せなかったので辛い……。

来年以降はとりあえずレギュレーションとか当日マニュアルとか熟読するようにしたい。

ただ、ためになった気がするし楽しかったので、来年以降も参加してみたいです。

ICPC2017国内予選参加記

1週間前に行われたICPC国内予選にdGFpc2VpeXVtYQ*1というチームで出ました。

Pietは今回は使わず、C++を用いました。 その参加記をここに残します。

コンテスト中の流れ

16:30

コンテスト開始。A問題を読み、全探索するだけなのでチームのエースに問題内容を伝えて実装してもらう。4分ほどでAC。

16:35~16:50

B問題を読んで、やるだけ問題なので一人後ろについてもらいながら適当に私が実装し、エンバグデバッグを少ししつつもAC。

16:50~17:00

エースがC問題を通す様子を、チーム全員で指摘しながら見守り、AC。

17:00~17:40

D問題は入力に応じて2つの解法に分ければよいという雰囲気だったので、エースに実装してもらう。ただ実行があまりにも遅かったので標準出力をファイルに流さず眺めていたら、なんとか数分で終わったのでそれを回答ファイルにコピーして提出した。ここでWAをもらい動揺するが、どうやらコピーしたときに最後に改行を入れたことが問題だったらしく*2実行に時間を掛けつつAC。DのACまでは開始から70分程しかたっていなかったのでここまでは順調。

17:40~

次にとりかかる問題を全員で考える。Gは右手法で行けそうな気がしたが、Gにしては簡単すぎて怪しいので他のチームが通したのを見てからとりかかるという話になった(今思うとGに取り掛かってもよかった気がする)。その後、僕がFの嘘解法をチームメイトに話し、少し実装した後にダメなことに気づいてFの実装を中断(このFの考察、あと少しで正解だったのでもう少し時間をかけて冷静に考察すべきだった。悔しい。)。

その後~

EがDPで解けそうとの話になったので、入力文字列を評価する部分を二人で実装しつつ、エースに解法を検証してもらう。その後、エースに最短文字列をdpで探索する部分を実装してもらう。このE問題の実装がかなり重く、デバッグを3人がかりでやったが結構時間をロスしてしまった。そして提出するもWA。この時点ではまだ数十分残っていた。そのあとバグをいくつかつぶしたが、残り十分で解法に不備があることに気づく。具体的には( ( a ^ b ) * ( c ^ d ) )みたいな二つと二つを演算するパターンが抜けていた。もう大きく修正する時間がなかったので、気合いでごまかそうとするが通せず終了。

結果

全体順位28位、学内順位4位で予選落ちです。大学を変えれば通過できる順位なので趣を感じますが、東大はもっとひどいので我慢です。

振り返ってみても5完、6完するチャンスは十分あったので悔しいです。来年はなんとか予選通過したい。

↓は順位表の一部です。(青色のチームが予選通過、左の数字が順位です。) f:id:basemusi:20170720091728j:plain

*1:チーム名の由来は極秘なので察してください

*2:大きく事故るチャンスなので皆さん気を付けましょう

PietでABC061に出てみた

Pietと呼ばれる難解プログラミング言語を用いてAtCoder Beginner Contest 061 - AtCoder Beginner Contest 061 | AtCoderに出てみたので、その記録を残しておきます。

Pietについて

 Pietを知らない人はこの辺を見ましょう。Pietが分かりやすく説明されている最高の資料なのでまだ見ていない人はみましょう。

 簡単に言うと、ドット絵ソースコードプログラミング言語です。例えば、下のような二つの数の最大公約数をもとめるプログラムが描けます。f:id:basemusi:20170513235017j:plain

 しかし、なぜかPietのソースコードを直接Atcoderに提出することはできないので、Pietのソースコードを書いたら適当にc++とかに変換します。その辺の話はkmc.hatenablog.jpで書きました。この記事ではABCのD問題とかも解いているので、今回の結果もまずまずのものが得られるだろうと思っていました。

 

結果

1完でした……つらい。。。

コンテスト中の流れ

21:00

コンテスト開始。A問題を読み、解けそうなので早速取り掛かる。

21:22~21:27

Pietからc++への変換が久しぶりだったので、変換ツールの使い方を思い出しながらA問題を提出。 WA。 入力の順番を勘違いしていたことに気づき、それを修正してAC。 Atcoderに提出したプログラム

Piet版↓

f:id:basemusi:20170514000404p:plain

21:30

B問題を読む。解法のアルゴリズムは難しくないが、二重ループが必要そうで書きたくないので飛ばす。 C問題を読む。いろいろとめんどくさそうだが、ループは一重でよさそうなのでこれにとりかかる。

22:20

使用する配列の初期化・基数ソート・答えを求めるループの3つのループを描き上げる。 しかし、ここで他の言語では変数の参照にあたる処理がPietでは計算量がO(1)でないことを思い出して、今書いているプログラムがTLE解であることに気づき絶望する。案の定サンプルを入れたら、実行に数十分かかった。実行中の中断が自由にできないPietのIDEを用いていたので、そのままコンテスト終了。

コンテスト終了後

少しのデバッグとともにC問題を提出しなおし、TLE以外はそこそこ合ってそうなことを確認して満足したので終了。 Atcoderに提出したプログラム

Piet版↓

f:id:basemusi:20170514001448p:plain

まとめ

Pietでプログラミングは難しい(575)

いい感じのメドレーを自動生成したい

この記事はkmc-id : base64による KMC Advent Calendar 2016 22日目の記事です.

www.adventar.org

前回の記事はwass80さんによる「部室に温度センサーとかつけて監視する」でした.

www.wass80.xyz

いい感じのグラフで部室を監視できて良いですね.

QOL*1を上げたい

 皆さんは何か作業するときに曲を聴きますか?私はよく聞いています.私のお気に入りの作業用BGMはニコニコ動画【打ち込み】駆け抜けるアニソンメドレー by M.Iz(元M.I.) 音楽/動画 - ニコニコ動画です.この曲はアニソンがいい感じに繋げられていて聞いていて気持ちいいです.

 この曲を聞いていて,こんな感じのメドレーを自動生成できたらQOLが爆上がりして人生勝ち組になれるのでは⁉︎と思ったため,いい感じのメドレーを自動生成するプログラムを作ってみました.(進捗力が足りなかったので,精度はあまり良くないかも……)

 (QOLは大事です)

本題

 ここから,いい感じのメドレーを生成する大まかな方針を簡単に説明していきます.

 ソースコードを見たいという方や,実際に試してみたいという方はgithubで公開しているのでそちらを参照してください*2github.com

 いい感じのメドレーを作りたいと言っても,どうすると「いい感じ」なのかをちゃんと定義しないと先に進めないので,「いい感じなメドレー」をここでは下のように定義します.

  • 中途半端なタイミングで曲が切り替わるのではなく,小節や拍単位で一つの曲から抜き出されている.
  • 似ている音を持つところで曲が繋げられている.

曲をいい感じのタイミングで切り取る

 この部分のアイデアこの参考文献を参考にしています.

 まず曲を短時間フーリエ変換し,各時間における周波数ごとの音の大きさを求めて,これの単位時間当たりの変化が大きい時刻を音が変化したタイミングとして列挙します.

 音が変化したタイミングは拍のタイミングと一致することが多いことから,音が変化するタイミング同士の時間間隔を調べて,そこから拍と拍の間隔を推測します.

 そして,得られた拍の間隔を基にして,音の変化の度合いが大きい箇所を調べて,それを小節の開始点ということにしています*3

 以上の手順を得て,曲の小節(拍)のタイミングと思われるタイミングで曲を切り取っています.

似た音で曲を繋げる

 あらかじめ曲をいい感じのタイミングで切り取ってたくさんのパーツに分けます.このパーツの始まりと終わった直後の部分の音の周波数成分で大きいものをフーリエ変換で調べてます.これで得られた周波数の音でそのパーツが始まり,そしてその音が鳴る直前にパーツが終わるということにします*4

 あとは適当な曲のパーツから始めて,そのパーツの直後の周波数と近い周波数で始まるパーツをつなげて,つなげたパーツの直後の周波数と近い……(以下略)とすることで似た高さの音で曲を繋げています.

成果物

 僕のPCに入っている曲を使って手元で生成したメドレーをあげたかったんですが,思いっきり著作権的にまずい*5ので,jackerさんのKMCフリー素材*6の音楽を使わせてもらって作ったいい感じのメドレーをKMC内で公開します(jackerさんに感謝!).

 (こうしてKMCのDTM勢の曲を聴くとすごいなぁといつも思います)

 KMCに入っていない人は手元でプログラムを動かすか入部しましょう!

 それなりにいい感じのメドレーが(少なくとも僕のitunesの曲に対して)自動生成できたので満足してますが,いろいろな部分を雑に実装していて精度も良くないので,今後改良していくかも.

次回のKMC Advent Calendar

 明日のKMC Advent Calendar 2016の記事はtetsutalow先生による「1223は素数だしかし20161223は素数ではない」です.楽しみですね.

KMCM(宣伝)

京大マイコンクラブではQOLを上げたい部員を募集しています.年齢や所属、国籍や宗教その他諸々に関する制約はありません。詳しくは入部案内を見て下さい。 www.kmc.gr.jp

*1:Quality of Lifeの略

*2:gitとかpythonには慣れていないので,温かい目で見てください

*3:この部分の精度がかなり悪く,自分のitunesに入っている4分の4拍子の曲で40%弱ほどで正しく小節の先頭を検出できる.多くの場合他の拍のタイミングを誤検出する

*4:フーリエ変換でただ単純に調べただけだと色々な音が混じる曲では精度が良くないという話もあっていい感じにしたい

*5:代わりに著作権が切れた有名な音楽とか使えばいいのかなと思っていたら,著作隣接権などがあって厳しそうだった

*6:KMCの活動の範囲内で自由に使える素材

ブログはじめる

こころいき

こんにちはこんにちは,basemusiとかbase64*1と言います.

なぜ今ブログを開設したのかと言うと,

レポートを書かないといけないのにやる気が全く出ないので,別のことに時間を使ってレポートを書かない言い訳をしたいから

今後書こうと思うことが幾つかあるので,「せっかくだから自分のブログを作るか」と思い立ったからです.

放置するかもしれないけど雑に適当にいい感じによしなにやっていきます.

*1:base64と言うのはエンコード方式の名前と一緒なんですが,なぜか僕はそれについて詳しくはないです.あまりつっこまないでください.