2017-12-23

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に参加していた選手たちだよ」と説明しておいた。先輩がプレゼンをしている中、スクリーン近くにある味噌汁をそーっと取りに行った。

2017-12-12

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

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

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

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

やり方

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

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

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();
    });

2017-12-05

コードレビューで英語実質ネイティブの人々がよく使ってくるAcronymのまとめ

公用語が英語の会社でコードを書いているので、コードレビューのコメントも英語で来る（それはそう）。よく、英語話者が使うAcronym（頭字語と訳すらしい。代表例はLGTM）がわからなくなるので忘れないようにメモる。

Acronym	意味	別解	備考
AFAIK	As far as I know		アメリカ人のマネージャーは”あふぁいく”みたいに発音していた
AFAIR	As far as I remember		前述のマネージャーはAFAIKとAFAIRの違いは特に気にしたことがないらしい。
IIRC	If I remember correctly
IMO	In my opinion	国際数学オリンピック（International Mathematical Olympiad）	なんでコードレビュー中に数オリの話が出てくるのか
LGTM	Looks good to me
NVM	Never mind	Node Version Manager	なんでJavaのコードレビュー中にnodeの話を始めるのか
RC	Release Candidate	鉄筋コンクリート（Reinforced-Concrete）
SGTM	Sounds good to me

他に何か気が付けば追加する。

2017-06-13

徳山こうせん（not 高専）の標識まとめ

ネタ

高専生ならみんな入力したことのある○○光線ですが，実在する○○光線があります．

それは徳山光線です．ちゃんと証拠の画像もあります．

f:id:blue_jam:20170613005806j:plain

暗くて字が読めなかったので，色味の調整をしていますが，それ以外の画像編集は一切していません．ちなみに，Google マップでも確認できます．

徳山光線は"とくやまひかりせん"と読みます．その名のごとく，旧徳山市（現周南市）と光市を結ぶ道路です．山口県道8号徳山光線 - Wikipediaによると，都濃郡都濃町が徳山市に編入された時に現在の名称になったようです．なお，徳山市が周南市になったときは名称の変更はなかったもよう（周南市でかすぎるんもんね．）

ちなみに，徳山港線（Google マップ）も存在します．山口県道52号徳山港線 - Wikipediaによると，こっちは"とくやまこうせん"と読むらしい．．．

2016-12-18

証明を書こう！

この記事はCompetitive Programming （その2） Advent Calendar 2016 - Adventarの記事として書きました．

この記事に，技術的に有用なことはありません．「証明を書こう！」という話です．

何か月か前に，とある方から次のような質問をされました．

競技プログラミングをやっていて，こういうのがあったらいいなあってものてある？

僕は「ちゃんとした解法の証明がほしい！」と答えました．その後に理由を長々としゃべりましたが，大体次のようなものだったと思います．

解説では解法の方針がざっくりと説明されているだけだから．
（僕の研究室では）重要なスキルの一つに証明を書くことがあるから．（この質問の前に「競プロって研究の役に立ってる？」という質問をされていた．）
（僕は証明無しでアルゴリズムについて話をするとうちの先生方に説教を食らうのに，みんなサボってずるい！）

1つ目の理由は，ざっくりとした説明だけではわかった"つもり"にしかなれないと思っているからです．特に，最近は競プロの問題の難易度がどんどん上がってきていて，「本当にそれでうまくいくの？」と思うような解法がたまにあります．牛ゲーとか，高難易度の貪欲とか「証明があったらうれしいなあ」と思うことがよくあります．なぜその解法でうまくいくのかを確認するには，やっぱり証明を追わないと．

2つ目の理由は，僕の所属している研究室の研究内容に大きく依存しています．僕はアルゴリズム関係の研究室に所属しています．研究室仲間がやっている研究は様々で，マッチングをやっている人もいるし，乱択数え上げをやっている人もいるし，分散アルゴリズムをやっている人もいます．僕らに共通して必要なスキルは"証明を書くこと"です．だから，証明を書く練習がしたいし，そのお手本があったらうれしいというわけです．

ちなみに，この会話の最後に「お前がやればいいんだよ！」というツッコミをいただきました．アドベントカレンダーを書くまでに，問題の証明を書こうと思っていましたが，残念ながら間に合いませんでした．今後，時間が空いたときに何かしら書いていこうと思います．

以上「（僕が）証明を書こう！」という話でした．最後までお付き合いくださった方，ありがとうございます．

2016-06-25

ICPC2017国内予選参加記（引退します）

ICPC

チーム名はyotei_awanaiです．チームメイトのハンドルを知らないので，N君とK君とします．

結果

どう考えても5完セットでした．6完ワンチャンだったと思います．でも3完74位です．

引退 & JAG入会待ったなし．

結論

コミュニケーション大事
練習大事
平常心大事

準備

秘密の数は836705．

チームメイト全員と顔を合わせることができたのは，予選本番前の30分前でした．原因が体調を崩しまくった僕のせいです．チームメイトの皆さん本当にごめんなさいでした．

チームメイトにはお詫びになんばん往来をあげました．東京の人に渡す予定だったのに，会えなくて余らせていたものだったのはここだけの秘密です．

環境は，本番前日に決まりました．本当に何やってるんだろうね．．．他の二人は慣れない環境（Win+MSYS2）に戸惑っていたようです．はじめから，アジア地区ではUbuntuだから，Ubuntuでやるよ～とかアナウンスをしておくべきだった．

流れ

A問題

K君単独．問題概要は知らない．開始8分でAC

B問題

N君．当確判定がわからなかったみたいなので，適当にアドバイスしました．（のこりの票を全部2番目の人に入れるんだよ～みたいな）開始47分でAC

C問題

篩う． N君がB問題を解き始めてた時には紙コーディング終わってました．ファイルの更新時間によると，B問題を提出してから10分でACしてたみたいです．

D問題

K君が一生懸命考えていたので，すこしアドバイスをしました．今考えると，僕も一緒にじっくり考えていた方がよかったと思います．

E問題

EはEasyのE（解けるとは言っていない）．問題をちゃんと読むとパスかサイクルになることがわかる．パスやサイクルに対する操作を悩んでいる間に時間切れ．

でも，そもそも辺のコストの計算を間違えている（体積にしてた）とか結構問題があった．もっと落ち着こうな．

F問題

無向グラフ同型判定は～みたいなことは知っていた．時間足りず

G問題

わーい幾何だー

H問題

知らん．

今年度の参加記は以上

最後のICPCを終えて

高専時代を合わせると計4回ICPC国内予選に参加しました（高専時代に登録だけして参加できなかったやつを除く）．アジア地区予選へは計2回進出しました．

楽しかった思い出も，苦い思い出もあります．今後参加する人の参考になるかもしれないので，

楽しかった思い出

夏合宿

夏合宿は全日程参加を1回，飛び入り（コンテスト時に混ぜてもらっただけ）を1回しました．

競技プログラミング漬けになれるのは，JAG合宿だけ！別の学校の同じぐらいの強さの人と部屋が同室になるので，話がはずんだりします．

交通費だけで30,000円以上かかったけどな！たしか，雑費を含めて40,000円~50,000円ぐらいかかった．でもそれだけの価値があったと思う．

アジア地区予選

オンサイト独特の雰囲気があっていい．いろいろな人（学生も，企業の人も）とも話ができる．

小中高の全校集会での偉い人のお話は全く聞く気がなかったけど，アジア大会でのスピーチだと思うとありがたみが一気に増すぞ！

焼肉

企業賞おいしかったです． $\sqrt{29}$ さんごちそうさまでした．

交通費まで出していただいて．．．

苦い思い出

解答権喪失

稀にみる悲しい状況です．初めての国内予選で経験しました．

WAだったらまだ大丈夫ですが，あの画面はやばいです．頭の中が真っ白になります．本当に．マジで．トラウマ．

これは極端な例かもしれませんが，普段は普通に書けるコードも，本番で制限時間が付くと急に書けなくなります．（僕がとても緊張に弱いというのもあるでしょうが）

落ち着けるルーチンがあったらよかったかもしれません．

練習するときは，制限時間を付けたり，あえて集中できない環境でやったりするのもいいかも？

僕は他の人の声や，キーボードの打鍵音がかなり気になるタイプなので，耳栓とかを持ち込んだ方がよかったかなと思います．（ルール上平気かは要確認．アナウンスが聞こえなくなるので注意）

健康管理

今年とか極端な例ですが，心身の健康は大切です．コンテストに限った話ではないですが，健康は大切にしましょう．深夜コンテストに参加しまくって，昼間寝て太陽の光をまったく浴びないなんてことがないように．（昼夜逆転しても平気な人は参加してどうぞ）

2016-05-04

SRM 690(Div.1 Easyのみ)

ケアレスミスでEasyを落としました．（何やってんだか．）

解いた問題

Easyのみ.120点ぐらいでの提出だった．

問題概要

整数 $N$ と $K$ が与えられる．（ $1\le N\le 100, 1\le K\le 15$ ）

1 ~ 100 までの整数のうち， $K$ 個の数 $u_1, u_2, ..., u_K$ を選び，どのように $v\in \{-1,0,1\}^K$ を選んでも， $\sum_i u_i v_i$ が $N$ にならないようにする．

解法

等差数列 $a + d(i-1)$ でよさそう．

このように数列をとると，どう選んでも， $b a + c d$ （ $b,c\in \mathbb{Z}$ ）にしかならない．この形では， $\operatorname{gcd}(a,d)$ の倍数しか作れないということは一般常識．

よって， $a$ と $d$ を変化させて適当な数列を作る．

念のため， $N$ と $K$ を変化させて全通り試すと， $N=60$ ， $K=15$ でこの方法ではうまくいかない．最も長く作れて，14個（ $a=7,d=7$ とする)．よって，この時だけ1を追加すればよい．．．はずだった．

ミスしたところ

初項 $a$ ，公差 $d$ の等差数列の $a$ 以上 $e$ 以下の項の個数は， $\lfloor (e-a)/c\rfloor+1$ でえられる．

int k = (100 - a) / d ;

はい．見事に+1を忘れました．

解法では， $N=60,K=15$ がコーナーケースと言いましたが，これだと $K=14$ の場合もできないと判定してしまいます．

それだけだったらよかったのだが， $N=60,K\ge 14$ のときに，1と""2""を加えるようにしてしまった．この2つを足すと3になって， $-3 \equiv 60 \pmod{7}$ となってしまう．加えるのであれば，8（7を法として1と合同）とかにすべきだった．．．

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ALL(c) (c).begin(),(c).end()

ll gcd(ll x, ll y){
    return y == 0 ? x:gcd(y, x % y);
}

struct WolfCardGame {
  int N;
  int K;
  vector<int> createAnswer(int _N, int _K) {
    N = _N, K = _K;
    for(int a = 1; a <= 100; ++a){
        for(int d = 1; d <= 100; ++d){
            if(N % gcd(a,d)){
                int k = (100 - a) / d; //ミス その1
                if(k >= K){
                    vector<int> ret(K);
                    for(int i = 0; i < K; ++i){
                        ret[i] = a + d * i;
                        if(ret[i] >= 100) cout << "oops" << endl;
                    }
                    return ret;
                }
            }
        }
    }
// ミス その2
    vector<int> ret(K);
    for(int i = 0; i < 13; ++i) ret[i] = 7 + 7 * i;
    ret[13] = 1;
    if(K == 15){
        ret[14] = 2;
    }
    return ret;
  }
};

// Powered by Greed 2.0-RC

実は，ミスその1については気が付いて，修正もすんでいたが，前のままでも問題ないと思って提出していなかった．出力判定関数も書いていたのに，そもそもその判定関数が間違っているという．．．

もっと落ち着いて問題を解こうな．