読者です 読者をやめる 読者になる 読者になる

Python3.5 Windowsにsklearn(+scipy,numpy)を入れる

なんか面倒くさかったので,困っている人のためにメモ

そもそもWindowsはscipyのインストールが面倒くさい.↓を参考にしてお手軽にインストールした.

Windows で VirtualEnv の Python2.7 に pip と wheel を使って コンパイルエラーが発生するパッケージ(例 scipy)をWindows用バイナリ提供サイトから入手してインストールする - グロブ

それでもまだ, ImportError: DLL load failed: The specified module could not be found. が出る.困った.どうやら,numpyをインストールするときも普通のnumpyではだめらしく,numpy-MKLをインストールしないといけないらしい(この辺は詳しくない). 上の記事と同様 numpy-mklをwheel形式でインストール (Python Extension Packages for Windows - Christoph Gohlke)

stackoverflow.com

そしたら動いた.

Python3+bs4で AtCoderのスクレイピング入門(初級者向け)

正直後から思ったんですが、urllib使うよりrequestsのほうが使いやすいと思うので、requestsを使うことをおすすめします (2016/07/17)

※ python2のurllibの情報が欲しい人はurllibの仕様が2系と違うのでこの記事を参考にしても意味ないです

Python3とbs4(beautifulsoup4)でAtCoderの便利スクリプトを作る.

対象読者はWebスクレイピングしたいけど,ブラウザ以外からのログインさえできる気がしないって人です.Pythonよくしらない人向けに書いたつもりでしたが,僕もPython初心者で教え方が全くわからないのでちょっと厳しいかも.

かなり手を抜いているのでコメントか直接何かしらの手段で質問してくれたら答えたいと思います.すみません.

bs4 をインストールしよう

bs4は何をしてくれるやつかっていうと,htmlとかxmlのタグをパースしてくれるというか,必要な情報抜き出してくれるやつです. 正規表現とかガリガリ駆使しながらタグ抜き出す作業するのは楽しいけどめんどいいので,そういった面倒臭さから僕達を遠ざけてくれます. 嬉しい!

pip install beautifulsoup4

でOK.pipがない人はインストールしといてください.

AtCoderPythonからログインしよう

AtCoderPythonからログインします.

ログインするためにはどういう手順を踏めばいい?

自分のアカウントでログインしたクッキーを維持しながらサイト内をWebスクレイピング(ウェブサイトから情報を抽出すること)しないといけません.

これはPython3に標準搭載されているurllibというインターネット上のリソースを取得するためのパッケージを使うと簡単に実現できます.

ログインはどのように行われるかというと,AtCoder(を含むいろいろなサイト)はPOSTリクエストという形式でログインに必要な入力データを持ってあるURLにリクエストすると,ログイン処理を行ってくれるように出来ています.

AtCoderのログインフォーム(https://arc001.contest.atcoder.jp/login) を見ると,以下のようになっています.

  • ユーザー名の部分
<input type="text" id="name" class="input-xlarge" name="name" value="" autocomplete="off">
  • パスワードの部分
<input type="password" id="name" class="input-xlarge" name="password" value="">

name部分が重要に注目してください."name"と"password"になっていますね. これに関するデータをPOST形式で渡すときの要素名になります.

実際にログインしてみる

さっそくAtCoderにログインしてみましょう.

ディクショナリをPOSTデータの実質の形式(password=パスワード&name=ユーザー名)にしてくれる関数urllib.parse.urlencode()があるので,それを使います.

username,password = 'ユーザー名','パスワード'
postdata = {
    'name': username,
    'password': password
}
encoded_postdata = urllib.parse.urlencode(postdata).encode('utf-8')
req = opener.open("https://arc001.contest.atcoder.jp/login",encoded_postdata)

print(req.read().decode('utf-8')) # req.read()だけだとバイナリで表示されてよくわからないのでutf8の文字列に変換

ログインに成功するとトップページに飛ぶので, 表示されたソースに「パスワードを忘れた方はこちら」とかが無ければログインに成功しています. おめでとうございます.

参考にさせて頂いたサイト様: http://stackoverflow.com/questions/5010915/how-do-i-clear-the-cookies-in-urllib-request-python3

AtCoderから情報を取得してこよう

問題番号とそれに対応するリストを取得してみる

ひとたび/loginにアクセスしてログインに成功したら,openerにクッキーの情報が紐付いてくれているので,あとは好き放題リクエストしまくりです.

では,問題番号とそれに対応するURLのリストを取得してみましょう. 課題ページ(http://arc001.contest.atcoder.jp/assignments )のソースを見て,問題へのリンクがあるところを抜き出すと,以下のようになっています.

<td class="center"><a class="linkwrapper" href="/tasks/arc001_1">A</a></td>
<td><a class="linkwrapper" href="/tasks/arc001_1">センター採点</a></td>

どうやら運の良いことに問題ページのURLにリンクされている⇔classがlinkwrapperであるタグで囲まれているということが分かりますね.

soupのオブジェクトを作って,select関数で.linkwrapperクラスのタグを全列挙してみましょう.

以下のコードにドットがついているのはcssのclassだからだと思います.

req = opener.open("http://arc001.contest.atcoder.jp/assignments")
soup = BeautifulSoup(req,"html.parser")
for tag in soup.select('.linkwrapper'):
  print(tag)

実行結果は以下のようになると思います. 実際にはtagは文字列型ではなくいろいろ操作ができるオブジェクトですが,あくまでprintした時の挙動はタグそのものを出力します.

<a class="linkwrapper" href="/tasks/arc001_1">A</a>
<a class="linkwrapper" href="/tasks/arc001_1">センター採点</a>
<a class="linkwrapper" href="/tasks/arc001_2">B</a>
<a class="linkwrapper" href="/tasks/arc001_2">リモコン</a>
<a class="linkwrapper" href="/tasks/arc001_3">C</a>
<a class="linkwrapper" href="/tasks/arc001_3">パズルのお手伝い</a>
<a class="linkwrapper" href="/tasks/arc001_4">D</a>
<a class="linkwrapper" href="/tasks/arc001_4">レースゲーム</a>

1つの問題につき2つリンクがあるので,これはお好みですが0,2,4,...番目だけ取り出せばいい感じになると思います.どうせこのへん賢くやっても仕様変更されたらおしまいなので,その時点で動いてればいいんじゃないでしょうか.

せっかくなので問題番号とそれに紐付いたURLというタプルのリストを作ってみましょう. PythonはすごいのでリストXに対してX[0::2]とすると2個飛ばしでリストを抜き出してくれます. こんなかんじになります.

X = []
for tag in soup.select('.linkwrapper')[0::2]:
    problemid = tag.text
    url = "http://arc001.contest.atcoder.jp"+tag.get("href")
    X.append((problemid,url))
print(X)

ここで,tagのメンバとかメソッドでtextとかget("href")とかありますが,これはそれぞれタグの囲まれている中身やタグの属性を取得してくれる便利なやつです.

出力結果は以下の通りです.

[('A', 'http://arc001.contest.atcoder.jp/tasks/arc001_1'), ('B', 'http://arc001.contest.atcoder.jp/tasks/arc001_2'), ('C', 'http://arc001.contest.atcoder.jp/tasks/arc001_3'), ('D', 'http://arc001.contest.atcoder.jp/tasks/arc001_4')]

ところで,リスト内包表記という記法を使ってタプルのリストを作るソースが以下のようになります. こういうワンライナーな使い方をすると可読性が低い気もしますが書きやすいです.

print([(tag.text,"http://arc001.contest.atcoder.jp"+tag.get("href")) for tag in soup.select('.linkwrapper')[0::2]])

問題文からサンプルを抜き出そう

あとはやることは同じです. ソースがどういう構造になってるか眺めながら,特徴になってきそうな部分を取り出してくるだけです. どうやら入出力の枠はpreタグで表現されているみたいです.これを全て取得すれば常勝では!?

しかし,気をつけることがあります.AtCoderの問題文は作る人によってhtmlのフォーマットが微妙に違うっぽいです. 具体的な例としては,preタグを入力形式・サンプル入出力以外にも使っている作問者がいるということが挙げられます.

ちなみにpreタグについている属性も人によってまちまちなので,あまりそこを情報として使うとよくないかも.

ただまあ,大体はお行儀の良い感じになっているはずなので,取得してみてバグったら修正を繰り返してればなんとかなるはずです.

ARC001で試してみる

ARC001のA問題(http://arc001.contest.atcoder.jp/tasks/arc001_1 )に対して,preタグでフィルタをかけてみましょう.

req = opener.open("http://arc001.contest.atcoder.jp/tasks/arc001_1")
soup = BeautifulSoup(req,"html.parser")
for tag in soup.select('pre'):
  print(tag)
<pre>
<var>N</var>
<var>c_1c_2c_3…c_N</var>
</pre>
<pre class="prettyprint linenums">
9
131142143
</pre>
<pre class="prettyprint linenums">
4 1
</pre>
<pre class="prettyprint linenums">
20
12341234123412341234
</pre>
<pre class="prettyprint linenums">
5 5
</pre>
<pre class="prettyprint linenums">
4
1111
</pre>
<pre class="prettyprint linenums">
4 0
</pre>

かなりいい感じに取れましたが,入力の項が混ざっています.これを取り除くために,一例として以下の方針が考えられます.

  1. prettyprintもしくはlinenumsクラスをselectに指定する

  2. 1つ目の取得結果を問答無用で取り除く

ARC001〜ARC004の範囲ならどちらの方針でも正しく動きそうです. 必要・十分条件とどれくらいのコンテストに対して成り立ちそうかみたいなのを強く意識すると正しい選択ができるかもしれませんが,これといった正解はないです.アドホックです.

まあとりあえずそのへんどう処理するかはおいおい考えるとして, とりあえず入力と出力を切り分けてみます.2.の方針のほうが多分多くのケースを網羅できるんですが,今回は1.の方針でやってみましょう.

opener = opener.open("http://arc001.contest.atcoder.jp/tasks/arc001_1")
soup = BeautifulSoup(req,"html.parser")
tags = soup.select('.prettyprint')
input_tags = tags[0::2]
output_tags = tags[1::2]
# len(input_tags) == len(output_tags) は勝手に仮定
for i in range(len(input_tags)):
  print("---- sample %d ----" % i) # こういう記法です
  print(input_tags[i].text.strip()) # strip()は前後の改行空白消してくれるやつです
  print("--")
  print(output_tags[i].text.strip())
  print()

出力結果は以下の通りになります.

---- sample 0 ----
9
131142143
--
4 1

---- sample 1 ----
20
12341234123412341234
--
5 5

---- sample 2 ----
4
1111
--
4 0

概ねこんな感じになりました. いい感じですね.あとはこのテキストをファイルに保存したりしたら自動ダウンローダーは完成です.おめでとうございます.

ところで,前後の改行空白を消すためにstrip()を使っていますが,不具合の元になる可能性はあります.が,そんな入力作るwriterいないと思いますし,サンプルに関してはミスって無駄に改行がある回とかがある可能性もあるのでstrip()する方針は間違ってなさそうです.

おわりに

いかがでしたでしょうか. 実はダウンローダーツールを作っていて,そのついでに並行でこの記事を書いてみました. 自分が扱ってるコードとここに書いたコードはいろいろ違うので,もしなんかこの部分動かないよ!ってのがあったらコメントください.

bs4についてもっと知りたい人は以下の記事が参考になると思います.僕もこれを見ました.ありがとうございます. http://qiita.com/itkr/items/513318a9b5b92bd56185

Python2 ニコニコ動画のコメント取得

コメント取得には,ニコニコ動画のIDではなく,固有のスレッドIDが必要らしい.

  1. http://flapi.nicovideo.jp/api/getflv/sm** でスレッドIDとニコニココメント取得APIをのアドレス取得(動画毎にapiの番号が違うから気をつけて).この操作にはニコニコ動画のログイン情報のクッキーが必要.
  2. 取得したAPIにgetリクエストすればコメントのxmlを得られる.リクエストの形式は「http://msg.nicovideo.jp/**/api/thread?version=20090904&thread=***&res_from=-***」という具合.res_from=-***を指定すると,直近***件のコメントを取得できる.
  3. コメントのパースを適当にする.

ソースコード

# -*- coding: utf-8 -*-
import urllib2, cookielib
from urlparse import parse_qs
import re

class NiconicoCommentGetter:
	def __init__(self,username,password):
		cj = cookielib.CookieJar()              # Cookieを格納するオブジェクト
		cjhdr = urllib2.HTTPCookieProcessor(cj) # Cookie管理を行うオブジェクト
		self.opener = urllib2.build_opener(cjhdr)    # OpenDirectorオブジェクトを返す
		self.opener.open("https://secure.nicovideo.jp/secure/login","mail=%s&password=%s" % (username,password) )
	
	def get(self,smID):
		# smIDからthreadIDの取得
		r = self.opener.open('http://flapi.nicovideo.jp/api/getflv/' + smID)
		html = r.read()
		res = parse_qs(urllib2.unquote(html))		
		
		# threadIDからコメントxmlの取得
		r = self.opener.open("%sthread?version=20090904&thread=%s&res_from=-1000" % (res['ms'][0],res['thread_id'][0]) )
		xml = r.read()
		
		# コメントのパース(無理やり,仕様変わってダメになるかも)
		comments = []
		rm = re.compile(">(.*)</chat")
		for line in xml.split('><') :
			g = rm.search(line)
			if( g != None ) : comments.append(g.group(1))
		return comments 

commentGetter = NiconicoCommentGetter("email", "pw")
for i in commentGetter.get("sm7"):
	print(i)

出力例

a
懐かしいな
最も古い動画?
こんなのあるんだ
sm7がなんで今更出現したの?
はえ^~
7コメ、記念カキコ
とうこうびなぞすぎ
6と8無いよ
なんでsm7が今更wwwwww
...(略)

参考資料

ニコニコ動画のコメント解析 – nanoway

urllib2でCookieを使う - ひきメモ

ICPC Tsukuba Regional 2015

コンテスト部分です.レポートがやばいので適当に書きます.

[00:00]コンテスト開始

  • 僕がA読んで解いて,xmodmapを設定するという方針.FAするぞー.
  • A読む.愚直にやるだけや~ん.
  • subsequenceだなあ,ただ例見る限り連続だしどっかに連続って書いてるでしょ.
  • non-negativeだから気をつけなきゃ...答えは1以上だな!!!
  • 書く.
  • サンプル1,サンプル2どっちも合った.出します!(間違い)

[00:05] A WA

  • 超慌てる.何事.
  • 問題文読むと"連続する"って英単語が無いことに気づく.うわこれ連続してない可能性あるやんどうしよう.
  • まーすにバトンタッチ

[00:11] B AC

  • Aに戻る.
  • 慌てている.うわーーーサンプル2ページ目にたくさんある!!
  • とりあえずどう考えても連続してない場合無理ゲーにしか見えないんだけど,WAしてるチームがいないから書いてみる.
  • サンプルが合わない.
  • よくよく考えるとnon-negativeは0以上だということに指摘されて気づく.
  • あわてて元のコードを1バイト修正
  • 提出
  • 全然ジャッジかえってこねえ.....
  • あまりにもかえってこないのでスタッフ呼んだりする.

[00:19] A AC

  • やらかしてもうた...冷静になるべきだった.
  • とりあえずDを読んで,解法をまーすさんに説明する.
  • 一次元に直すパートを頑張って紙の上で書く.
  • まーすさんがCを書いている.かなり実装きついと言っている.結構つらそう.
  • まーすさん曰く2~3完まみれになりそうとのこと.

[??:??] C WA

  • WAらしい.なんかいろいろ方針を変えて書きなおしている.
  • たしかここでDを書いたりしていた気もする.
  • 一次元に直すパートだけ書いて印刷して合ってるか確認みたいなことをしたりもする.
  • 後半の円環貪欲部分は典型だけれど,かなり苦手なので頭が混乱してくる.
  • 怪しいコードを書く.
  • ちょいちょいまーすに変わったりする.

[??:??] C WA

  • うーん...まーすさんが全く異なるシンプルな方針を思いついたと言っていて,そっち書く.

[01:57] C AC

  • さすが.
  • ただひどい順位表にかなり焦る.
  • とりあえずDを書き上げて,サンプル合ったのでクッッッッッッッッソ怪しいけど出してみることにする.

[??:??] D WA

  • WA.とりあえず印刷.ひどいコードを見たまーすさんにどんびきれる.
  • そもそもアルゴリズムが細かい部分でも間違っている上に円環の処理が全くできていない.
  • とりあえずustimawさんにEのコーディングをしてもらう.
  • その間にまーすさんにコードのだめな部分を指摘してもらう.
  • それを修正する.

[02:44] D AC

  • まーすさんがドン引きしている.「あれのアルゴリズム自体を間違えるのはちょっと・・・」ごめんいや僕も自分自身にドン引きしてます許してください.
  • とりあえずG読む.最短の長さ求めてから1つ1つ決めるとO(n^3)かかるからどうすっかなーと思っていたら,最短の長さだしちょっと巧みなメモ化再帰して復元すれば楽だなあと思う.
  • どうやら,Eのサンプルが合わないみたいな感じなので,交代してもらってコーディングする.
  • とりあえずGの最短dp書き上げてから,ustimawさんに交代する.
  • Eのサンプル合わない原因が分かったらしく,修正したらサンプルが合ったぽい.
  • Eを出してもらう.

[03:42] E AC ←時刻怪しい.+14分かも

  • ヨッシャ!
  • Gももうほとんど書き上がっているので,オーバーフロー対策とかをして出す.

[03:48] G AC ←時刻怪しい.+14分かも

  • よしよしよし一気に4完→6完.
  • ただ順位はね,ひどい.
  • まーすはFは方針経ったので通せそうって言っている.
  • Hは読まない.
  • I,Jの概要をustimawさんに説明してもらう.
  • Jはなんかmustというべきところをcanと認識してしまったせいで,少なくともdominator treeではないという結論になる.そもそもmustと認識してもどうdominator tree使うねんという部分で詰まっているはずだが.
  • どうやらIが独立集合求めるタイプのオーダー的に計算量落ちる探索なので「こういう問題を待ってた」「これはジャッジとの戦いやぞ」みたいな小言を言いながらやりてえなあと思う.時間余ったらやろうかなと思い,枝刈りの方法を考える.嘘っぽいのばかり思いつく.
  • dfsでやるのとdijkstraでやるのどっちがいいかなあと悩んだりする.
  • 順位表を見てIでTLEしてそうなチームがどれくらいいるか確認したいものの,ほとんどのチームが未着手でびっくりする(サンプル1つしかないからとりあえず嘘っぽいの書いて投げてるチームはいると思ってた).
  • Fが書き上がったらしいので提出してもらう.

[??:??] F,WA

  • デバグ開始
  • そもそもデッドロック,頭が混乱するので苦手で,説明されてもあんまり問題が頭に入ってこない.
  • 全然バグの原因わかんねえなあと数十分みんなで悩む.問題が頭に入ってこないせいでバグの原因もあんまし分からない.
  • さすがに明らかに通らなさそうなI書かせてとは言えないし,ウムム(実際紙の上で思いついた枝刈りでは通らないはず)

[05:00] ロスタイム

  • 実は途中でなんか特別にロスタイムを14分あげますと言われていたので,その時刻がやってくる.
  • 正直Aのジャッジが遅かったくらいで14分もロスタイムを頂くのはよくわからなかったけどまあいいや.
  • 静寂に包まれる.周りがみんなこちらに注目していて辛い.
  • なんかスタッフもたくさんやってくる.辛い.
  • とりあえずデバッグしてたらにぶたんの境界が怪しいという結論に至る.
  • 投げてもらう.

[05:04] F,AC

  • 7完.
  • 静寂の中声が響き渡る.周りの退屈そうな視線が辛い.
  • 何もしないのも申し訳ないのでとりあえずブツブツ言いながらIのコーディングをする.
  • 結局間に合わず終了Ω\ζ°)チーン.

ICPC Tsukuba Regional 2015(コンテスト以外)

2015年の11/28-11/30に行われたICPC2015の筑波アジア地区大会に行ってきました.

がんばって敬称略します.

出発日

  • @ustimaw,@mitaki28と一緒に8:30に集合
  • 新大阪出発
東京到着
  • 会津勢と会う.ウェーイ.
  • 秋葉で@__mathと合流
  • つくばエクスプレスに乗る.
  • convex hull trick実装してたら突然@yosupotに頭殴られる.
  • 雑談してたらうるさかったのか横に座ってた人が怪訝そうな顔で席を空けてくれる.申し訳ない.
つくば駅到着
  • AtCoder役員や他の参加者と大合流する.
  • 道を先導しようとしておもいっきり間違える.誰もついてきてなかったのでOK.
  • スタッフがJAGJAGしている.すごい.
コンテストサイトに入る
  • 公用語は英語
  • 雑談する
  • NCTUのコーチと会話する.模擬地区予選で調子が悪くウームム...と言われる.
  • mockコンテストでNTUの人ばかりKを解いていたので,NTUの人はmongeが得意なの?と聞いたところ,そんなに有名ってわけではないけどぶっちゃけノリでやりましたみたいなことを言われる.マジか.
practice
  • 日本語キーボードがカスすぎて戦慄する.
  • とりあえずキーボードがヤバイのには目を瞑って,スタック上限を確認.
  • フルに拡張されてるっぽいので無理やり拡張するまでもないっぽいなという結論.
  • ぜろくぎさんたちのチームが親切にもxmodmapのやり方を教えてくれる.本当にありがとう.
java challenge
  • ustimawさんとmitakiさんが頑張っている.どうやらジャッジが死んでいてこれもうわかんねえならしい.
  • 僕らはだらだらしている...
懇親会
  • 移動.いろいろ雑談する.SJTUの人にお久しぶりですと挨拶する(去年の台湾で雑談した).
  • チームスライド発表.よすぽのやつ結構すき.あとCXIVDXIVのスライドもすき.
  • hogloidがめっちゃSJTUの人と英会話している.聞き取るだけでも精一杯.聞き取れないけど.
  • 雑談に集中していたら置いてかれそうになる.危ない.
宿泊施設
  • 筑波研修センター.
  • 風呂に入ったり,部屋で雑談したり.
  • 鍵開けたままベッドでウトウトしてたらよすぽが勝手に侵入して僕の寝顔をとっていたり,さすがに自分のセキュリティ意識が低すぎる.
  • とりあえずconvex hull trickの問題を通してから寝ようと思い,2~3時くらいに寝る.
  • 早く寝ようと思ったんだけど,カチカチとラップ音が鳴っていて寝れないオイオイオイオイ.あまりにもうるさすぎる.
  • 暖房から出ている音っぽい?
  • とりあえず耳を塞いでがんばって寝た.

コンテスト当日朝

  • 07:30に起床.朝飯を食いに行く.
  • なんかみんな等しくあんまし寝れんかったぽい.
  • やべえな研修センター.
コンテスト会場に移動
  • なんか待機場所みたいなとこに連れてかれたけど状況が分からない.
  • と思っていたら会場がオープン
  • 本当に時間通りに開始するのかなあと思っていたらちゃんと時間通りに開始してハッピー.
コンテスト開始
  • あとで書きます.闇でした.
コンテスト終了
  • 精神的にキツいロスタイムを終え,コンテスト終了.大事故です.
  • ustimawさん「韓国大会参加しててよかったね...」
  • 問題解説やjavachallenge,セレモニーのために別会場へ行く.
  • 問題解説,ほとんどのチームが解けたA,Bに対して超丁寧に解説した後,以降の問題が全て雑に説明されていてショッキングだった.
  • java challengeはもうハチャメチャだった.
  • 結局sample AIを出したNTUが優勝していてめっちゃ面白い.
  • ただ,余興だしええやろという感じ.余興という域を少しでも超えたら許されないレベルではあったw
  • 結果発表,SJTU全完マジで何事だよ.
  • なんかクリスマスプレゼントいっぱいもらっている.
クロージングパーティー
  • いろいろ起業ブースがあってとても楽しい.
  • 「いい生活」名前が面白かったので企業説明を聞きに行ったらどんな会社か分かった.
  • ドワンゴクイズ,101を作りたいと強く願ったら解けて人形をもらえた.本は諸事情で遠慮した.
  • googleのブース回ったりlineのブース回ったりいろいろした.
  • なんか11位で「いい生活さんから企業賞ないんすかね~」とか冗談で言ってたら,本当にいい生活さんから11位に企業賞があってびっくりした.
  • googleのクイズ,謎解きとしてはtypicalで,最後の謎も割とtypicalっぽいんだけど,折ってもええことないやろ絶対...みたいな感じで話してたら,とりあえず折ってみろと言われ,折ったら感動した.
  • sigmaが僕のフードにいい生活シールをこっそりいたずらで貼っていたらしく,記念撮影のときに知った.偶然らしい.
  • その後はやんちゃな参加者や人事さんになんかアホみたいに衣服にシール貼られまくってた.広告料をよこせ(傲慢)
  • その後記念撮影して解散
2日目の宿泊施設
  • ぬわー疲れたもう.
  • なんか一階でだらだらしてたら,asiさんがピザ食うぞと言ってきて,食いたかったので食うことにした.
  • 目の前にドミノピザとコンビニがあって,意外に立地がリッチ.
  • 第一研修室に行くと,Yonsei Universityの人がおり,雑談する.
  • 話を聞くとそもそもコーチ相当の人は別の大学の人だし(よくみると名札がguestになってた),チームメンバーの一人であるxhaeさんは27歳らしい(兵役の都合で,M2かつ3年の兵役でそうなるぽい)
  • 彼らはCodeforces Div2の過去問にバーチャル参加したりして遊んでいた.
  • 韓国の人の英語,単語のチョイスとか発音がめっちゃ理解しやすい+聞き取りやすくて,今までに無いくらい意思疎通が出来た.
  • あと韓国のICPC事情について教えてもらった.僕らが2位になったことで背景ではかなり色々なことがあったらしい...ただそのことを知っていてもおそらくあの順位だったと思うので,申し訳ないとは思えど反省はしていません.
  • ついつい遅くまで楽しく談笑してしまいましたが,寝る前に素数を順番に言っていくゲームをKU勢と三重大学勢を含めた関西勢とやって就寝.
  • 寝る前に,アジア地区で着手できなくて心残りだったI問題を通して寝る.寝たの4時.

エクスカーション当日

  • 死ぬほど眠い.
  • 出発する.眠い.
最初の訪問先に到着
  • 1つ目のサイバーダイン・スタジオというロボットスーツのところに行く.眠い.
  • ビデオがいろいろな意味で面白かった.眠い.
  • 質疑応答フェーズで意識が飛ぶ.寝ていたらしい...
  • パワードスーツ実在すると思っていなかったし感動.
昼飯
  • 高エネルギー加速研究機構に移動して,昼飯食う.
2つ目の訪問先に到着
  • 高エネルギー加速研究機構を見学する.
  • 小学生向けの展示でテンションが上がる大学生たち.
  • いろいろおもしろいものがあった.
  • 基本的に寝まくってて本当に申し訳なかった.
解散

翌日

  • 情報解析Aの試験勉強を1mmもしていなかったため@a3636takoに助けてもらう.
  • あやうく死ぬところだった.
  • オシマイ.

codefestival 2015 コンテスト部分

遅くなりましたがcodefestival 2015のコンテスト部分参加記です.

[00:00]コンテスト開始

[00:41]A AC

  • FAらしい.やったー!
  • ダイスゲームを読む.3.5 * n 付近の整数を出力すればいいのかなと思う.
  • 実は複数ある場合は最小という制約を見逃していたせいで,複数ある場合はどれでもよいだと思っていたので切り捨てて出す.

[01:57]B WA

  • 2ケースだけWA.なんでだ.誤読に気づく.n=1だけ場合分けして再提出

[02:41]B AC

  • あーやっぱりn=1のケース2つはいってたのね.安心
  • 寿司タワーを読む.読むの辛い.
  • にぶたんで答え決め打ち+貪欲だと思ってしまう.

[10:20]C WA

  • またまた2ケースだけWA.うーん.
  • いろいろ変えるもWAを連発してしまう.
  • 仕方ないので計算量怪しいdpを書く.どうせこの辺にある問題やしテストケース作りこんでないやろし通るやろと思う.

[20:03]C AC (3WA)

  • 辛い...超慌てる.
  • D読む.うまくやれば解けるけどセグツリーが楽系にしか見えない.
  • とりあえずまあ,うまくやる方法を考え実装したが実は嘘であることに途中で気づき,セグツリーをペタ貼る.サンプル一致したので出す.

[31:01]D AC

  • うーん.やばいなあ.
  • Eを読む.パッと見解ける問題に見えない.
  • あんまり考えたくなかったので,ショートコーディングっつってるし高々数バイトになるのではwみたいな仮説を立てる.
  • 実際制約がそんなかんじになりそうっぽい.
  • 値の範囲も,元の関数f(x)と作った関数g(x)について,x=[-2,2]の範囲でf(x)=g(x)だったら関数としても一致してるでしょwみたいな気分になる.
  • 実装してサンプル一致したので出す.

[41:40]E AC

  • うーん...
  • 次に解けそうな問題何があるだろうなあ.Gかな.
  • Gの問題文を頑張って理解する.
  • とりあえず区間dpやってくださいみたいな問題なので区間dpを書く.
  • サンプル1が合わずバグる
  • 時間が無限に溶けまくっていく.
  • 気分転換に焼き肉を読む.区間ソートしてdpしていくタイプのやつっぽいが全然わからんし,3つ重なってるときどうしたらいいんかわからん.悩む.
  • 風船ツリーを読む.少しだけ考察.とりあえずあるパスを残すと決めたときに,どう切断するのが最適なのか考えていたけど,よくわからんうーんとなる(冷静に考えると根本でばっさり切るのが正解).
  • 焼き肉解けてないのに解けそうにないし捨てる.
  • 歩くピアニストを読む.グラフが輪っかになります.そこからわかりません終了.
  • Gに戻ってくる.
  • サンプル1が合うようにdpを書く.サンプル2が合わない.頭が混乱してくる.
  • これは括弧付けと同様だから,特殊ケースではカタラン数になってくれるはずなのでそういうケースを作る.
  • そういうケースに一致するように書いたら今度はサンプル1が合わない.
  • 結局dpで考えるべき状態が間違っていたらしい.

コンテスト終了

  • 死にたい

CodeFestival 2015

2015/11/14-15に行われたCodeFetival2015に参加してました.結論からいうとサイコーでした.

ただメインコンテストの成績が悪いと一気に記憶がなくなりますね.

せっかく超楽しいイベントだったので頑張って思い出します.割と適当なので事実と異なることが書かれていたら指摘してください.

前日

  • 前泊が出ないらしく,上野の1600円のカプセルホテルに泊まることにした.つっつ(@threepipes_s)さんが予約してくれる.
  • 4時に授業終了して,直接新大阪駅に行く.
  • つっつさん,たこ(@a3636tako),sntea(@hogex4)くんと7時頃新大阪出発.本当はろいち(@roiti46)さんとも行く予定だったけど,都合が合わないらしくroitiさん抜きで行く.
  • あの(@nbkwon)君に競プロLINEで見送られながら出発
  • 新幹線では自由席でワイワイ.新幹線では暇だったので去年の本戦問題を解く.Fがムズすぎてコンテスト終了.辛いなあとなる.
東京入り
  • 東京に着く.上野に行く.カプセルホテルに着く.
  • カプセルホテルの人「カプセルで会話したりすると絶対苦情がくるし,コワイ人がたくさんいるから注意だけじゃ済まない場合があります.本当に気をつけてください.」なんやめっちゃ警告してくるやん..気をつけよ.
  • 夜遅かったのでみんなで吉野家に行く.僕だけビール飲む.吉野家なのにも関わらず会計が4桁になりビビる.
  • 帰ったらカプセルで@roiti46さんにエンカウント.とりあえずロビーで明日のことを決めて就寝.

当日

  • ちゃんと起きれる.電車乗る.
  • 会場近くのマクドで朝飯.@sntea君が階段で大転倒する.焦った.大丈夫だったみたい.
  • マクドのトイレ使ったら出てきたウォシュレットが戻らなくなって超焦る.あまりに意味不明だったので無理やり押し込む.
コンテスト会場到着
  • 会場到着.テンションが上がる.
  • あーすげえ競技勢がめっちゃ運営スタッフしとるな...すぬけがこっちを見て手を振っている.りんごさんもいる.ありとあらゆるindeed社員・内定者がおる.
  • 交通費精算をした後,だらだら雑談して過ごす.色んな人とセルフィしまくるv iwi先生ともセルフィキメるvv↑↑
  • 会場に微妙に中毒性のあるBGMが流れている.
  • codefesのオープニングとかを見る.めちゃかっこいい.
  • オープニング見て色々説明された後は,コンテスト開始前のご歓談タイムになる.
  • コンテスト開始時刻がちょっとずつ遅れ続ける.どうやらネットワークがΩ\ζ°)チーンしてる様子.スタッフさん大変そう.
コンテスト
  • 結局40分遅れくらいで本戦開始.
  • (また書きます.省略)
  • コンテスト終了.55位くらい.もうね,ガチ冷え.
  • ただ終わった時に普通に自分に手が負えないタイプだった気がしたので,割と清々しい.がんばって残りのcodefes楽しもうと気持ちを切り替える.
  • パーカーはもらえたのでOK.ただ沖縄行けなかったのがとても悲しい.ICPCチームメイトのustimawさんと一緒に冷えてた.
解説を聞く
  • Fは多分ムリそう
  • Gは思考デバッグの下手さと演習量の足りなさを痛感
  • Hは実は考えなくて良いケースを考慮する思考の浅さを狙い撃ちされた気分
  • Iはもっと思考したほうがよかった.今興味のある根からのパス以外について,「根からばっさり切る」のが嬉しいというのに気づけないのはさすがにアウト.
  • Jは読まなくて結果的に正解だった
コドフェス併設イベント
  • 早速じゃがバター食う.美味さアリ.
  • よすぽとDDRする.筐体は結構ふるいやつ.課題曲のÜbertreffen 13(激)する.速度設定ミスって,スコア68万とか出てびっくりする.音ゲーに対しロバスト性がなさすぎる.
  • よすぽがDDRのせいでマジで死にかけてる.
  • JAPLJとtozanがÜbertreffenをプレイする.どっちもフルコンしている.すごい.うまいなあ.
  • トークセッション回ったりする.kenshoさんトークライブを聞く.重い話に突入してんなあと思ってたらいい話に変わっていたり,AtCoder社長の奇行紹介をしていた.
  • 太鼓の達人のランカーがプレイしていたり,gahouさんが今年もDDRしていたりする.さっぱり交互踏せる気無しみたいな譜面を交互踏みしていてハチャメチャヤバイ.かっこいい.
  • 秋葉先生とひょんさんがペアプロしていてほんと面白い.ひょんさんは相変わらずひょんさんだった.良いキャラしている.
  • バグ取れずに終了かな??と思っていたら, かなり最後の最後でバグ箇所をプロっぽい人が発見しサンプルが通る,それを提出したところ,なんとAC!土壇場でフロアを湧かすhyonさんやり手.
エキシビジョンマッチ開始前
  • roxion1377の席に行ってだらだら観戦準備.真横にエキシビジョン室がある.
  • 上位5人(ほぐろいど,よすぽ,じゃっぷる,みさわさん,ぜろくぎさん)に加え,kawateaさんとrngさんもゲスト参戦....rngさんってそれマジ???
  • ワイサン****とアミラゼさんが司会をしている.
  • ぜろくぎさんの「1時間キレイに座ります」というコメントが印象的
  • コンテスト開始前,会場が映る.よすぽがホイミスライムをめっちゃうまい具合に置こうとして思考錯誤している様子を見て笑う.
エキシビジョンマッチ開始
  • コンテスト開始.問題見る.A,フローっぽいけどなんだコレ?頭に入ってこない.A読んでたら笑いが起きる.なんだなんだ.
  • よすぽの画面見たらオイオイこれはこれはアカンやろオイ.どうして僕の顔写真を表示しながらコーディングする必要があるんですか(正論).
  • よすぽはBは無理と判断してAをやっているらしい.
  • みさわさんは爆速でAを書き始めている.え,はやくない?SCCとか書いてる.何にSCC使うねん.
  • A,さっぱりno ideaなのでBを読む.図がエグい.コンピューターで実験したくないタイプのヤバイ敷き詰め問題だ...90点は実験して多項式補完でしょ(よく知らないし適当)みたいなことを思いついたが,実験が困難.手でやるしかなさそう.
  • じゃっぷる・りんごさんはBを考えていることは分かった.
7分経過
  • みさわさんがなんとAを提出している.さすがフローのみさわさん.
  • しかし惜しくもWA.つい最近本で読んだことがある問題だから解けるはずなんじゃ~~どこが間違っとるんじゃ~~とテキストエディタで主張している.
  • みさわさんが早速詳細に解法を解説しだし,司会の仕事を奪おうとしているw
12分経過
  • よすぽがAの部分点を取る.はじめての正の点数.✌している.
  • 参加者の画面が,特大スクリーンに映ったりする.もちろんよすぽのやつも(図1).よすぽは俺の顔写真取り下げてくれ頼む.
  • 司会者「本人の許可は取っているんでしょうか」とってません
  • Bは実際にありうるケースは少なそうなんだけど,実際どういう形をしているのかよくわからないなあと思っていたら,degwerがこういう感じになりそ~~と図を見せて説明してくる.なるほど.

f:id:kyuridenamida:20151114202510j:image

図1. しぐまさんのブログから拝借(http://sigma425.hatenablog.com/entry/2015/11/15/224851)

28分経過
  • Bをりんごさんが颯爽とAC,満点.さすがとしか言い様がない...
32分経過
  • かわてぃーさんもAの部分点を拾っている.
  • 相変わらずみさわさんはAの何が間違っているか分からない様子で,色々な方法で撃墜ケースを探そうとしてい..たのかな(うろ覚え)
43分経過
  • よすぽがAに提出.「二重提出した・ちょくだいごめん」とか画面に書いてる.なんとACする.FAです.
  • 「俺はね天才✌✌✌✌✌✌」とか書いて調子に乗っている.
  • よすぽ,順位表を確認するとrngさんが既に150点を取っていることに気づく.
  • 「ダメやんけ」と言っている.「Bは無理」らしい.なんか2^(w*h)とかいう明らかにサンプル1からまず通らなさそうな解を投げたりしていて草.
  • みさわさんは相変わらずテストケースを生成して撃墜ケースを探している.つらそう.
  • ぜろくぎさんもAに提出はしているがWAの様子.
56分経過
  • JAPLJがBの部分点を提出しAC!実験の成果が実ったらしい.
  • 続いてhogloidもAをAC!すごい.
  • hogloidがなんJアンテナを開きだして,もうそろそろコンテストも終わりかなーみたいな雰囲気が漂っていた.
59分30秒付近
  • りんごさんがAに2つ解を提出
  • なんとそれが通る!!!!りんごさん全完!!!!司会もびっくり,会場大盛り上がり.
  • なんでエキシビジョンはこんなファインプレーが発生するんだ.
エキシビジョンマッチ終了
  • 適当によすぽっと川柳をつぶやく.
  • プレッシャーの中クソムズ問題2問の1時間コンテスト本当にお疲れ様でした.
  • 早速表彰式.各位のコメントとかが述べられる.
  • りんごさんは最後,アルゴリズムに必要な操作のうち,ありうる2通りの方法のうち1つが正しいみたいな選択に迫られて,考える時間がなかったのでとりあえず2つとも投げたら通ったと言っていた.すごい.
  • みさわさんはフローが好きなのにフローに愛されてないみたいなことを言っていて悔しそうだった.ハマると沼っぽいですね.
  • ぜろくぎさんも宣言通りになってしまったらしく悔しそうだった.スプラトゥーン頑張りますと言っていて草.-
  • その後リレー決めなど諸連絡
ホテルに戻る
  • 品川プリンスホテルに送迎バスで連れて行かれる.
  • 腹減ったナァ...
  • とりあえずhogloid,semiexp,wafrelka,kitayutaとかそのへんと歩いて近くの中華料理屋に行こうとしたら,ラーメン屋を除いて全ての店舗が半年間の耐震工事で一時閉店してて終了.
  • 迷いに迷った挙句,品川の外食は高かったので結局コンビニに行く.いつのまにか歩いているうちにdegwerとtokoharuとかが増えている.
  • 僕含め一部の人間が酒を買う.少しだけお酒を買い,部屋で少し雑談した後解散.
  • 寝る前に少しだけショートコーディングしようとしてしまう.A問題を40分くらい頑張った結果,89~90byteくらいで収束する.久しぶりにショートコーディングした.
  • 結局その後風呂入ったりして4時前くらいに寝る.

2日目

(だいぶ書くの忘れてたので適当に書きます)

  • 朝起きる.バス7時45分くらいまで止まってるかなと思ってたらバスが行っちゃう.
  • ということでタクシーに乗った.運賃はリクルート持ちでした.すみません.
会場到着
  • 朝プロ会場に着く.任意参加イベントなのにほとんどの人がいるって何事.
  • よくみると机になんかじゃがりこ1本置かれてる.なんやねんこれ.
  • 犯人はsigmaだった.また君か壊れるなあ.
DDR
  • ddrする.
  • とりあえずUなんちゃらって曲が,昨日60万点台でびっくりしていたので,速度をいつもの感じにしてプレイする.
  • 86万点くらいになる.ただ,ランキングには乗らないのでΩ\ζ°)チーンだった.
朝プロ開始
  • 朝プロはmedに参加.とりあえず3問解く.あ,結構いい順位.
  • ラスト問わからない.スタックとか使っても嬉しいことが起きる気がしない.
  • priority_queueとかいろいろ使って無理やり解いていたらTLEが取れずコンテストが終わった.
  • コンテスト終わった後に極大な長方形を列挙してから考えればイーよって後ろから現れたiwiwiさんに言われて,マジかってなる.
昼飯
  • かがみずとか浜松の人とかkagasanとか後輩とかいろいろな人と昼飯を食う.
  • 焼き肉弁当?美味しい.
  • 飯食ってるときにかがみずが"""c川柳"""の話をしており,さてさんの顔面がブルーになっている.本当に草生える.
トークセッション
  • 終わった後は,りんごさんのトークセッションに行く.
  • RGB当てとかすぬけ探しとかエモティコ単語推測等の謎クイズが連発する.
  • 最後のやつはクイズ番組ライクで良かった.
  • りんごさんに詳しくない人たちは,ターゲットが出題する予想の斜め上のクイズにびっくりしていたようですが,むしろりんごさんが真面目にクイズやってたら大事件でしょという気分だったw
  • 面白かった.
リレー
  • 色々な人と組む.名前は結構失念してしまいましたが顔は覚えてる...はず.
  • とりあえず多分codefestivalで一番楽しいコンテストだったと思っている.
  • 僕はゼッケンを人々の背中に貼る係をしていました.
  • リレー向きの問題がたくさんあってよかった.
  • Gのバグ取り手伝ったり,Jの考察をみんなでやっていたり(僕は参加していないんだけれど)した.
  • I問題を解いているれぷとんさんがめっちゃ条件制約を番号付き数式で書き下していて超びっくりした(考察メモがとても綺麗).
  • 動く順位表が良かった.
  • J問題をomeさんが辛がっていたんだけど,Iを解いた後実験しに行くって言った矢先にACして帰ってきて,チームで「!?」ってなってた.たしか最終順位は3位か4位だった気がする.
  • 1位ではなかったけど,とても楽しかった.
  • Gを移動やコーディングなど全て含めても5分以内に解けたのは個人的に満足(十分実装を思考する時間があったので).
表彰式
  • なんかいろいろ表彰されている.
  • プログラミングのコンテストにDDR/太鼓のランカーが招待されるってシチュ冷静に考えて異様ですき
  • ショートコーディングでミニクリーナー?を総取りしてる人がいて笑った.
  • コード川柳も賞があるらしい.突然少し嫌な予感がする.ふぁぼ数で決まるんじゃないかこれ...
  • 急いで自分のツイートを見る.ふぁぼ数が24ある.まさか.
  • そのまさかだった.表彰台に呼ばれる.慌てる.
  • それで,さらに驚いたのは書道家の人に何か書いてもらえるという特典がついてきたこと.本当に何を書いてもらうかすごく悩んだけれど,ツイートに含まれているそれっぽい文字列である「天才」にしてもらった.
  • 冷静に考えるとそれを持って記念撮影する可能性が高いことに気づき,書いてもらっている時にすごく焦ってた.
  • 案の定その予感は当たり,素材になってしまった.
  • 嬉しいやらなんやら.
閉会式
  • ビデオが流れる.おおまかな構成は既に想像しているにしろ,1日2日で作れるの,クリエーターはすごいなあと思った.
  • ドローンで記念撮影.紙コップ吹き飛ばされててすき
  • その後大阪に大阪勢と帰る.電車では寝る.