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と言うのはエンコード方式の名前と一緒なんですが,なぜか僕はそれについて詳しくはないです.あまりつっこまないでください.