JAG Contest 2016 Domestic A - 阿吽の呼吸

jag2016-domestic.contest.atcoder.jp

問題文

省略

解法(反転して表示)

本質的には括弧列が与えられるのでvalidな括弧列ですかという問題に言い換えれば見通し良く解ける. カウンタを定義する.「A」が来たらカウンタをインクリメント,「Un」が来たらデクリメント,途中でカウンタが負の数になったらNO,最後まで処理してカウント!=0ならNO.

ソース

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int a = 0;
    int n;
    cin >> n;
    for(int i = 0 ; i < n ; i++){
        string t;
        cin >> t;
        if( t == "A" ){
            a++;
        }else{
            a--;
            if( a < 0 ){
                cout << "NO" << endl;
                return 0;
            }
        }
    }
    if( a == 0 ) cout << "YES" << endl;
    else cout << "NO" << endl;
}

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で考えるべき状態が間違っていたらしい.

コンテスト終了

  • 死にたい