ICPC Asia Jakarta Regional Contest 2018 参加記

はじめに

11/10〜12に行われたICPCジャカルタ予選にearlybirdというチームで出ました。

せっかく海外に行ったので、参加記を書きます。

チームメイトはjoisinoとyumaです。

役割分担は

  • 実装: joisino
  • 考察: yuma・base64

で臨みました

11/9 移動日

  • 朝目が覚めて、携帯を確認するとyumaから「パスポートが見当たらない」というメッセージが届く
  • は?
  • とりあえずyumaを日本に置き去りにして韓国経由でジャカルタへ移動
  • なんとかyumaがプラクティスの日は間に合わないが本番の日には間に合いそうになる
  • 大会の運営にyumaがプラクティスに間に合わないことを伝える
  • 運営からyumaが遅れた理由の詳細を求められる
  • パスポートを無くしたと正直に答える
  • 運営からの返信がないままホテルで就寝(0時過ぎにチェックインで朝7時起床で辛かった)

11/10 プラクティス日

  • ホテルから大学へタクシーで移動(数百円しかかからなくてすごい)
  • 大会への参加を許してもらう(めでたい!)
  • チームメイトが一人欠けた写真撮影をする
  • 謎のパフォーマンスを鑑賞したり企業の人の講演を聞いたりルール説明を聞いたりチーム紹介があったり
  • ラクティスで、SCCとRMQを練習でjoisinoが書いてたらバグらせてて不穏
  • 夜はホテル近くのショッピングモールに食べに行った
  • インドネシア語の漫画を発見するなどした
    • 神のみの漫画を買った

11/11 本番

  • 朝、yumaとの感動の再開
  • 大学での受付がスムーズに終わってホッとする

    コンテスト

    I問題

    順位表を眺めるとI問題が解かれているので、yumaが読んでjoisinoが実装してAC(0:11)

    D問題

    僕がD問題を読んで、簡単に解けそうだったのでjoisinoに伝えて実装してもらう。AC(0:23)。FA

    L問題

    全く知らないうちにAC(0:36)

    A問題

    この辺でyumaと読んだ問題の内容を共有する。順位表を見るとAが解かれてるのでyumaと一緒にAを考える。いい感じになったのでjoisinoに伝えてAC(1:05)

    F問題

    結構バグりそうな雰囲気もあったが一発AC(1:21)。FA

    J問題

    このあたりで全員で問題の共有をして次に解く問題を決めた。 JはDPのJ。yumaが考えたDPをjoisinoに伝えてAC(2:20)

    H問題

    HはセグツリのH。最初に考えた方法がだいぶやばかったが、少し改善して軽めの方法で1WA後AC(2:55)

    C問題

    yumaが天才的に思いついて実験をいくつかした上で凡ミスの1WA後AC(3:53)。

    K問題

    橋を切らないようにすれば行けそうな気持ちになったところでyumaがいい感じdfsを思いつく。結構バグりそうな見た目をしていたがこれもjoisinoが一発AC(4:12)。 この辺でテンションが上がってくる。

    G問題

    かなり序盤に二分探索で行けそうな気持ちになるが、計算量が怪しいので却下される(実はこの解法を高速化するのが想定解だったっぽい)。結構悩んで、間に合うか分からない方法をjoisinoが投げる。ACしてやばい。神。(4:42)

    B・E問題

    Bはリンクカットツリーで解けるという話になるが、リンクカットのライブラリを持ってきていないことが判明する(そもそも時間がないが)。 Eの重い解法をjoisinoが思いついたが時間が足りないので、その解法を英語で書いてコメントアウトしただけの謎ソースコードを投げようとするが数秒間に合わず終了。

結果

よく分からないが World Final 通過チャンスっぽい?

結果はよかったがこう振り返ってみると、僕があまり活躍*1してなくて精進〜〜という気持ちになった。

11/12 excursion

  • 朝8時集合を勘違いして6時半集合だと思って辛い起床
  • 午前は謎のベンチャーゲーム会社の見学
    • LoLを(業務中に?)やってる人がいた
    • MOBAのゲームを作ってたりしてて開発中のMOBAを体験したりした
    • 3Dデザイナーとかプログラマーとかが実際に業務してるところが見れて面白かった
    • 他にもVRゲームとかARゲームとかを体験して満足
  • 午後はジャカルタ水族館に行った
    • 全体的に普通の水族館だと思っていいたが、最後に人魚が出てきて謎のショーが始まって面白かった

  • お土産をいくつか購入した後空港に行って帰国の途に着く

    11/13 帰国

  • 帰国する
  • 疲れた

*1:joisinoがWAで詰まらなかったのでデバッグの仕事が少なかった説はある

Atcoder Beginners Selectionを難解言語Pietで解いてみた

いきさつ

最近、Atcoder Beginners Selection をなんらかのプログラミング言語で解いてブログに上げる行為が流行っているようなので、Pietで流行に乗っていくことにした。

Pietとは

難解プログラミング言語の一つで、ソースコードがドット絵であることが特徴。慣れてくればソースコードフローチャートに見えてくるのでその点においては画期的(だと信じてる)。詳しいことは「Piet」で検索してください。

AtcoderではPietのソースコードを提出できないので、手元でPietのc++インタプリタに画像データを埋め込んで提出している。

A はじめてのあっとこーだー

実際に提出したc++コード

f:id:basemusi:20180321184452p:plainf:id:basemusi:20180321184512p:plain
AのPietコードと説明付きコード

A問題からループを使っていく必要がある。文字列の入力は1文字ずつ入力を受け取って、その文字が改行かチェックしながら行う。Pietはプログラミングが何も分からなくても、ぐるぐるしてそうな場所が分かるよい言語。

B Product

実際に提出したc++コード

f:id:basemusi:20180321185501p:plainf:id:basemusi:20180321185506p:plain
BのPietコードと説明付きコード

左上の部分で掛け算をして、右上と右下に分岐してそれぞれ出力する。分岐が実際に分岐している。

C Placing Marbles

実際に提出したc++コード

f:id:basemusi:20180321185812p:plainf:id:basemusi:20180321185818p:plain
CのPietコードと説明付きコード

1の数を数えてmod演算を使う。ソースコードの図形的には簡単。

D Shift only

実際に提出したc++コード

f:id:basemusi:20180321190116p:plainf:id:basemusi:20180321190123p:plain
DのPietコードと説明付きコード

最初に暫定解をINFにしておく。N個の数それぞれについて、最大何回2で割れるかを右上のループで求めて、その数と暫定解のminを暫定解にする。ループしてる感じがコードからにじみ出てる。

E Coins

実際に提出したc++コード

f:id:basemusi:20180321190711p:plainf:id:basemusi:20180321190715p:plain
EのPietコードと説明付きコード

11問中最も難しい。高等テクニックである三重ループを要求されるが、気合いを出すと実装できる。実装したときの美しさは他の言語を圧倒する。

F Some Sums

実際に提出したc++コード

f:id:basemusi:20180321191042p:plainf:id:basemusi:20180321191049p:plain
FのPietコードと説明付きコード

ループと分岐を実装していくと描ける。この辺のプログラムは見た目がフローチャートっぽい。

G Card Game for Two

実際に提出したc++コード

f:id:basemusi:20180321191713p:plainf:id:basemusi:20180321191719p:plain
GのPietソースコードと説明コード

上半分でバブルソートをして、下半分で貪欲に大きい数が書かれたカードをとっていく。ソートの実装は重いが、Pietはソースコードの再利用も可能なので、既に描いてあるソートプログラムをコピーすると簡単。

H Kagami Mochi

実際に提出したc++コード

f:id:basemusi:20180321192228p:plain
f:id:basemusi:20180321192234p:plain
HのPietコードと説明付きコード

長さ100超の配列を用意して(左のループ)、各d_iについて配列のd_i要素目をインクリメントし(中央のループ)、配列の中の1以上の数がいくつあるかを数える(右のループ)。1以上の判定にはnot演算を使うとよい。greater演算を使うよりもスリムに書ける。

I Otoshidama

実際に提出したc++コード

f:id:basemusi:20180321192931p:plainf:id:basemusi:20180321192941p:plain
IのPietコードと説明付きコード

1万円札A枚、5000円札B枚、1000円札C枚とすると、C=N-A-Bとなるので、AとBのループだけでよい。しかし残念なことに、自分のPietインタプリタが定数倍遅すぎてこの回答だとTLEしてしまった。悲しい。最高のPietインタプリタコンパイラでもいいよ)求む!!!

※3/21 20:53追記

よく考えると5000円のループは8枚以下しか回さなくてよいという情報が降ってきたのでO(N)で書き直してACした。

f:id:basemusi:20180321205055p:plainf:id:basemusi:20180321205104p:plain
IのPietコードと説明付きコード修正版

J 白昼夢 / Daydream

実際に提出したc++コード

f:id:basemusi:20180321193410p:plainf:id:basemusi:20180321193417p:plain
JのPietコードと説明付きコード

この問題では文字列を後ろから見ていった方が実装が簡単だが、Pietはメモリがスタックしかないので、何も考えなくても後ろから処理したくなる。しかし、Pietでは大きな定数を打ち込む気にあまりならないので(不可能ではないが不格好になる)文字のeなどをプログラムで使うたびに10*10+1=101='e'というようなパズルをすることになって実装がしんどい。

Pietでは分岐処理の間に黒い線を入れて分岐している感じを際立たせたりも可能。

K Traveling

実際に提出したc++コード

f:id:basemusi:20180321194033p:plainf:id:basemusi:20180321194040p:plain
KのPietコードと説明付きコード

時間差dt, x座標の差dx, y座標の差dyについてdt >= dx + dy && (dt - dx - dy) % 2 == 0が成り立つことを確認すればよい。

dxとdyの絶対値をとる部分は関数化して、まったく同じ絵柄を用いている。関数化すると便利。

まとめ

11問全問をPietで解くことができた。したがって、Pietでプログラミングコンテストに出てもよいというお墨付きが得られた(と思う)。みなさんも難解言語でプログラミングコンテストに参加していってください(僕はしません)。

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