CS Academy Round#73 参加日記
夜、布団に入ってTwitterを弄っていたら、「CS Academy オンラインコンテストが後10分で始まる」というツイートが見えました。
このサイトは初めて聞いたのですが、このツイートを見たことに運命を感じてしまったので、
速攻アカウント作って、参加することにしました。割とマジで、考えるより手が先に動きました。
という訳で今日は、CS Academyのオンラインコンテスト参加日記です。
CS Academyとは？
CS Academyとは、次世代のコンピュータサイエンス教育のプラットフォームです。 オンライン上でアルゴリズムの勉強等できるみたいですね。
その教育の一環として、定期的にオンラインコンテストが開催されているみたいで、今日はその73回目コンテストでした。
問題がいくつか与えられ、それを解くようなプログラムを制限時間内にいくつ作れるかを競います。
ただし、プログラムの実行時間に制約が設けられており、 たとえ正しく正解を出せるプログラムを作っていたとしても、その制約をオーバーすると正解判定は出ません。 なので、しっかりと効率的に実行できるアルゴリズムを考えつつ実装する必要があります。
世界中の人とリアルタイムで勝負ができるので、とてもワクワクします。 結構楽しいですよ。
どんな感じ？
コンテストが始まると、以下のように左側に問題文、右側にエディタが出てきてます。 エディタ部分にプログラムを書き、「Submit」ボタンを押下するとコードが提出されて正誤判定が出ます。
因みに、「Run input」を押下すると、提出前にコードのテストができたりします。
因みに、プログラミング言語はいくつかの中から選択できます。
僕は今回Pythonで解きました。(なぜか、Pythonで参加してた人は、僕ともう一人だけだった...)
自分のパソコンで環境を作らなくてもオンライン実行できるのは画期的ですね。 普通に使いやすかったです。
結果
今回は制限時間2時間、問題数は5問が与えられていて、僕はそのうち2問解きました。 順位は1117人中382位でした。
正直言うと、あと1問解きたかったです。 正しい答えは出るけど、実行時間オーバーでとても苦しみました。
Binary Isomorphism
Binary Isomorphismは、今回解けなかった3問目のタイトルです。
詳しい説明はすると長くなってしまうので省略します。 簡単に言うと、木の同型判定の問題で、想定解は根付き木ハッシュというものを使うらしいです。
プロの方の記事に根付き木ハッシュの説明が書いてあります。
これを読んで、なるほどなぁと思うと同時に、計算量的にはコンテストの時に自分で考えていたものとほぼ変わらない気がしました。
もしかしたら、Python自体がインタプリタ言語で実行速度が遅いが故に、タイムアウトになった説が浮上してきました。
(Python使ってる人少な過ぎるし)
最後に
CS Academyというサイトのオンラインコンテストに参加しました。 他の人と競い合うのも、パズルチックな問題を考えるのも、それをコードに落とし込むのも、全てが楽しいです。
他にもやりたい事は沢山ありますが、偶にはこういうやつをやってみるのはイイ息抜き(?)になると思います。
あとは、今回Pythonは競プロで使うには良くない説が浮上したので、次回は違う言語で挑戦してみたいと思いました。
