競技プログラミングコンテストカレンダーを作る(AtCoderスクレイピング編)

以前にTopCoder部のカレンダーからコンテスト情報を引っ張ってきて、いい感じにGoogleカレンダーに追加するGoogle Apps Scriptを書きました。(TopCoder部のカレンダーをGoogleカレンダーで(そこそこきれいに)見る - blue_jamの日記

しかし、残念ながらTopCoder部のカレンダーの更新が止まっています。あと、AtCoderのカレンダーも更新が滞っています。結果として、現在、僕のGoogleカレンダーにはCodeforcesのコンテストしかありません(参加する気もないのに)。

そのため、TopCoder部のカレンダーから引っ張ってくるのをあきらめ、AtCoderスクレイピングしてカレンダーにコンテストの予定を追加するようにしました。 あと、GoogleがApps ScriptのためのCLIツールを出したようなので、そちらの方に移行させました。

カレンダーはここに置いておきます。カレンダーは毎日深夜3時頃に更新される設定になっています。(こどふぉのコンテストしか追加されていないように見えますが、予定リストに切り替えるとちゃんとCodeFestivalの予選が追加されています。)

ソースコードはここです。READMEは気が向いたら書く。 github.com

依然作ったスクリプトも一応走らせたままにします。

IOI2018の競技プログラミング経験者ボランティアに申し込むために出したメール

(注)この記事は、僕が個人の意思で公開するものであり、IOI2018事務局さんは内容に一切かかわっていません。

IOI2018の競プロ経験者向けボランティアに参加するために、僕が送ったメールを(個人情報を隠して)公開します。参加したいけど、メールに何を書いたらいいかわからないという人は参考にしてみてください。

ここは絶対に変えなきゃダメよというところは字を赤くしています。

情報オリンピック日本委員会 IOI2018JAPAN 事務局 御中

<氏名>と申します.競技プログラミングの経験者として,IOIのボランティアへの参加を希望します. 現在は<会社名>で<役職>として働いています

コンテストの参加歴・運営経験は下記のとおりです.

[参加]

[運営]

  • 2017年 ACM/ICPCアジア地区予選(ICPC OB・OGの会のボランティアスタッフとしての参加.会場準備,後片付け,印刷されたコードの配達など)

よろしくお願いいたします.

--

<名前>

<メールアドレス>

これぐらい簡単なメールでいいとわかったところで、ボランティアに応募したくなった人は、次のページに書いてある応募用メールアドレスにメールを出しましょう。

jp.ioi2018.jp

ARC094 D: Worst Case

同僚に「最近ARCのC,Dを毎日2問ずつぐらい解くようにしてるんだよね」という話をしたら,「何か難しい問題あった?」と聞かれた.(お前ら僕よりよっぽどレーティング高いやろ!)

しばらく考えて解法が思い浮かばなかったこの問題を教えた.ちなみに,問題を教えたときはACしていなかったので急いでACした.(WAを出しているコードでdoubleの誤差で死んでた)

概要

D - Worst Case

解法

M=AB-1とする.

全列挙をやろうとすると時間切れで死ぬ.しかも,1戦目の順位だけを変化させて,積がM以下になる組を個数を数え上げようとすると,setで既に使った順位を管理していないとうまく数え上げができない.

中学校で習った反比例のグラフを思い出すと,y=M/xのグラフは\sqrt{M}までは急激に減少するが,それ以降はかなり緩やかに減少することがわかる. つまり,1戦目の順位を\sqrt{M}以下で変化させている限り,2戦目の順位の重複を気にする必要はなさそう.その逆もまた然り.

したがって,解は2\lfloor\sqrt{M}\rfloorぐらいになりそう.ただし,微妙に意地悪なケースがあって,

  • Mが平方数のとき,先述の値から1をひかないといけない(\sqrt{M}について重複して数え上げを行っているため)
  •  min(A,B) \le \sqrt{M} のとき,さらに1をひかないといけない(高橋君の順位を使うことができないため)

また,Mは最大で18桁ぐらいになるので,doubleのsqrtだと精度が足りなくなるので,自前で平方関数を作る必要がある.

#include<bits/stdc++.h>
#define ALL(c) (c).begin(),(c).end()
#define EACH(i,c) for(auto i=(c).begin();i!=(c).end();++i)
using namespace std;
#define int long long

int sqrtb(int a) {
    int l = 1, u = (int)2e+9;
    while(u - l > 1) {
        int c = (l + u) / 2;
        if (c * c <= a) {
            l = c;
        } else {
            u = c;
        }
    }
    return l;
}

signed main(){
    int Q;
    cin >> Q;
    for(int i = 0; i < Q; ++i) {
        int A, B;
        cin >> A >> B;
        if(A > B) swap(A,B);
        if(B == 1) {
            cout << 0 << endl;
            continue;
        }
        int M = A * B - 1;
        int L = (int)sqrtb(M);
        int t = 2 * L - (M / L == L);
        if(A <= L) {
            --t;
        }
        cout << t << endl;
    }
    return 0;
}

上京して一年後の状況

生まれて初めて東京に住んで一年ちょっとが立ったので、東京に住んでてよかったことと悪かったことを列挙します。 弊社には、博多オフィスを開設してほしいと思っています。

よかったこと

  • 高専の部活の先輩・友人が東京にいるため集まりやすくなった。
  • 電車を逃した時の悲壮感がない。(終電を除く)
  • 大型書店まで気軽に行ける。

悪かったこと

  • 家賃が高い。今の家賃を出せば、福岡なら駅近くの1LDKが余裕で借りられるらしい。
  • 人が多い。新宿、原宿、渋谷などはまっすぐ歩けない。
  • 電車の込み具合が異常。人を乗せる乗り物ではない。
  • 地方にある大型のショッピングセンターのようなものがないため、いろいろなものを買おうと思ったら、いろいろなところ(店・駅)を巡らないといけない。地方にいる頃は、大型ショッピングセンターに行けば欲しいものがほぼすべて手に入ったのに。(大型のショッピングセンターに売っていないものは大体その地方で手に入らないので、あきらめがつく)
  • "豚骨ラーメン"の記述が信じられない。
  • うまかっちゃんがスーパーに売っていない。
  • ポテトチップスの九州しょうゆ味がスーパーに売っていない。
  • 鮮魚類が高いくせに、質が悪い。

クソの役にも立たない社会人一年目の思い出

2017年4月から、新社会人として、某仕事検索会社でソフトウェアエンジニアとして働いています。1年間で体験したどうでもいい思い出を並べます。

4月

英語研修を受けた。今となっては信じられないが、朝9時前に出勤していた。

5月

開発チームのローテーションが始まった。苗字ではなく、名前で呼ばれることに慣れていなかったため、「おい!blue_jam!」と呼ばれるまで自分が呼ばれていることに気が付かなかった。

6月

生まれて初めて合コンに参加する。ここでいう合コンとは、企業合同プログラミングコンテストの意。

7月

生まれて初めて海外に渡航する。アメリカの入国審査員は恐い。 海外初めてのくせに、3か月滞在するという無理ゲー。渡航の最優先目標は無事に帰国すること。

8月

会社に行く以外は徹底して部屋に引きこもっていた。引きこもりのすることはどの国に行っても変わらない。

9月

日本に帰るまでの日にちを指折り数えていた。寿司以外の和風魚料理がめちゃくちゃ恋しかった。煮魚とか。

10月

自分が住むべき国は日本であると確信する。少なくとも、アメリカよりは自分に適している。

11月

楽しみかたは、十人十色

12月

ボーナスの金額を母に伝えると「私がパートで働くのが馬鹿らしくなっちゃうわ。お父さんには金額を内緒にしておきなさい。きっと悲しむから(父のボーナスよりも高額であるため)。」と言われる。

1月

スペースワールドが閉園してしまったため、とても悲しい。

2月

バレンタインデーにもらったチョコレートが1個だった。送り主は姉。

3月

合コン3回目

ACM-ICPC 2017 アジア地区予選つくば大会(JAGスタッフ)

ICPCのアジア地区予選のお手伝いをしてきました。ICPCに行くのは2年ぶり、JAGスタッフとしては初めての参加でした。

0日目(12月15日)

この日は通常通り会社に行って働いていた。つくばは行ったことがあったし、東京からはそんなに遠くないので、出発時刻をこの日の夜まで確認していなかった。※よい子は真似しないでね!

1日目(12月16日)

前日に調べた時間の電車に間に合うように6時に起床。予定よりも少し早い少し早い電車に乗る。結果、集合時間よりも30分早くついてしまった。

集合後、「いつもの面子で安心する~」という言葉とともに諸注意が始まった(気がする)。主に、システムの保護(物理)と選手の安全(物理)にかかわることだった。 そのあとは、ホワイトボードを運んだり、椅子を運んだり、配布資料を揃えたり、風船を膨らませたりという作業をした。個人的には風船を膨らませるのが一番疲れた。

今年はかなりスタッフの手際が良かったらしく、かなり早めに準備が終わった。「みんなこんなに早く終わるんだったらJAXA見学に行きたかったよね」はい。

選手が会場に入り始めると、会場を見回る仕事(通称:徘徊)が始まった。選手に頼まれてトイレまでの道を教えたり、質問があれば対応をしたりした。見知った顔を見るとうっかり話しかけてしまいそうになるが、そこはぐっと我慢。

練習セッションが始まる。練習セッションでは風船を配って歩いた。そののち、tatuyan_edsonさんに風船配布の進捗管理の方法を教わる。配布された風船の管理は、万が一、風船の誤配があったときに必要になる。けっこうアナログな方法で管理されています。

懇親会では、後輩に「焼肉はおごってもらう自信はありますか?」と質問しておいた。あと、司会をしていた陽気な先生に「君は30代に見えるよ!」と言われて地味にショックだった。

2日目(12月17日)

8時集合だといわれていたのに、7時55分ごろに説明が始まった。説明後準備作業に移る。

コンテスト中は風船配布の進捗管理のお仕事をtatuyan_edsonさんとやっていた。コンテスト序盤がかなり忙しかった(多くのチームがA問題を解くため)。ACラッシュがひと段落すると、コンテストの順位が落ち着いてみられるようになる。後輩チームがBで詰まっているな~とか。余裕が出てくると、時々ダジャレを言った。風船配布係から失笑が漏れていた気がするが気にしない。

コンテスト終了後、コンテスタントが外に出ていった後に会場の片づけをする。片付け終了後は表彰式を見に行く許可が出た。やはり、Yes/No演出はよい。

懇親会になると真っ先にご飯を取りに行ったが、周りにご飯を取っているJAGスタッフが見当たらなかったため、本当に飯を食っていいのか不安だった。食事を十分とると、会社のブースのお手伝いに行った。途中、会社の偉い(と思われる)人に「Is the order a rabbit?って知ってる?」って聞かれて戸惑った。

懇親会終了後はCertificate(なぜか僕の分は2枚あった)と企業のロゴが入った名札(同じ会社の人は誰も付けていなかったので存在を知らなかった)を受け取って帰った。無事に家に着いたので僕のICPCはここで終了です。

3日目(12月18日)

普通にお仕事です。出社したら、ICPC参加者が会社の説明を聞いているところを見つけた。興味深そうに見ている同僚に、「彼らは昨日ICPCに参加していた選手たちだよ」と説明しておいた。 先輩がプレゼンをしている中、スクリーン近くにある味噌汁をそーっと取りに行った。

獺祭の正規販売店の一覧マップを作る

獺祭を作っている旭酒造が「頼むから(正規販売店で)正規の値段で買ってくれ」という広告を出したらしい。その広告を見て思った。

「よし。正規販売店で買ってやろうじゃないか…ただし、正規販売店のリストをGoogleマップでくれ!広告にある店名のリストから、最寄り店を目grepで探せるわけがないんじゃ!」

というわけで、旭酒造のWebページから正規販売店の一覧マップを作れるようにしました。

やり方

CSVをダウンロードした後の手続きはGoogleマイマップの公式ドキュメントを参照した方が親切です。

  1. ここでCSVファイルを入手します。
  2. Googleマイマップのページに行き、新しいマップを作ります。
  3. インポートメニューから1で入手したCSVファイルをインポートします。どの列が住所でどの列がタイトルかを聞かれるので、適切に選んでください
  4. 完成

f:id:blue_jam:20171212202342p:plain

やったこと

前述のとおり、Googleマイマップはタイトルと住所が含まれたCSVファイルからマップを作れるらしい。というわけで、店名と住所が含まれたCSVを生成することが今回の目標です。 言語はJavascriptに決定。理由はJSだとHTMLのデータの抽出が楽そうだから。最近は頻繁に触っているし。(スクレイピングツールを使えばいいじゃんというツッコミは無しの方向で)

とりあえず、Webページの形式を確認しに行く。

f:id:blue_jam:20171212203128p:plain

嫌な予感がするぞ…

f:id:blue_jam:20171212203135p:plain

はい。というか、まともなフォーマットだったらExcelで完結するんですけどね。(いや、このままでもExcelでいける気がする。) 一つしか要素がないTRタグを取り除いて、二ついっぺんに処理するといい感じになりそう。

const getPage = (region)=>{
    return new Promise((resolve,reject)=>{
        const request = new XMLHttpRequest();
        request.open('GET', `http://www.asahishuzo.ne.jp/store/ja/${region}`);
        request.responseType = 'document';
        request.addEventListener('load', (e)=>{
            if (request.status === 200) {
                const doc = request.responseXML;
                const trs = doc.querySelectorAll('tbody > tr');
                const filteredTrs = [];
                for (let i = 0; i < trs.length; i++) {
                    if (trs[i].childNodes.length > 1) {
                        filteredTrs.push(trs[i]);
                    }
                }
                const map = new Map();
                for (let i = 0; i < filteredTrs.length; i += 2) {
                    map.set(filteredTrs[i].childNodes[1].innerText, filteredTrs[i + 1].childNodes[1].innerText);
                }
                resolve(map);
            }
        });
        request.addEventListener('error', (e)=>reject());
        request.send();
    })
};

const regions = ['hokkaidou', 'touhoku', 'kantou', 'cyubu', 'kansai', 'cyugoku', 'shikoku', 'kyushu', 'okinawa'];

Promise
    .all(regions.map(getPage))
    .then((maps) => {
        let resultMap = new Map();
        for (let i = 0; i < maps.length; i++) {
            resultMap = new Map([...resultMap, ...maps[i]]);
        }
        document.open();
        resultMap.forEach((name, address) => {
            document.write(`${name},${address}<br/>`);
        });
        document.close();
    });