飲酒プロコン参加記

これは、2019年12月22日に行われた飲酒プロコン（忘年会0次会）の参加記です。

開催されるまで

11月終盤ごろに、amylaseさんが「今年中に飲酒プロコンをやりたい」と言っていたので、「やってください！」とお願いしておきます。12月の初めに「今年中はさすがに無理では」とamylaseさんがぼやいていましたが、なぜかkenkooooさんが主催してくれました。

準備

僕はお酒を飲みすぎると吐いてしまうタイプなので、いつ吐いてもいいようにエチケット袋を準備しておきます。ヨドバシの通販で600円でした。

飲酒プロコン用に買った pic.twitter.com/vFCZHjMajJ

— アルゴリズムを背負う男 (@blue_jam) December 18, 2019

集合

集合時間は11時で、仕事のスタンドアップよりも遅いので、当然、集合時間に間に合うように起きることができます。財布の中に1000円札が存在しないことに気が付いたので、少し余裕をもって出発し、目的地の近くでお金をおろすことを目標にします。

電車に乗っている間、大手町駅のすぐ近くに、自分が使っている銀行があることを知ります。電車を降りてから銀行まで行ってATMを探していましたが、閉鎖されていたためあきらめてレストランに向かいます。

レストランの前にbeet君がいたので、軽く挨拶します。そのあとでコンビニに行ってポケットティッシュと胃薬を買います。胃薬を買う理由は、以前「酒を飲みすぎたら吐いた」という話をしたら、「胃薬と大量の水を飲むと翌日が楽になる」という話を聞いたからです。医学的な根拠は知りませんが、プラシーボ効果を狙っていきます。

飲酒プロコンのグループチャットを見てみると、SRMに参加していた人たちが寝坊報告をしているのが見えました。まさかの起床フェーズ。

11時ごろになると、amylaseさんが到着します。まだkenkooooさんが来ていなかったですが、時間になったので店に入ることにします。ところで、17人で予約していたのですが、11時に入店したのは5人でした。

注文

とりあえず、酒と食べるものを注文します。飲み物にボトルのワインばかり書いてあってビビりますが、地ビールを見つけることができました。後で説明しますが、ワインは1杯で1問開く＋1提出ですが、ビールは0.5杯で同じ権利が得られるためお得です。

若者がピザを食べたそうにしていたので、ピザを4種類注文します。生きているうちに、一回やってみたかったので、ピザのメニューを指さしながら「ここにあるものを全部一つずつお願いします（ピザのメニューは4種類あった）」と言ってみましたが、店員さんはきょとんとしていました。また、僕が食べたかった＆手が汚れるものを頼んで人を妨害したかったという理由で、手羽先のから揚げを注文します。

コンテスト

コンテスト開始直前にこのようなメッセージが届きました。

さすがはkenkooooさんです。

そうこうしているうちに、コンテスト開始時間になりました。ところでルールはこんな感じでした。

• コンテスト開始時に問題を1問を開ける権利が与えられる。
• アルコール10ml（目安はビール0.5杯、またはワイン1杯）を摂取するごとに、問題を1問開ける権利と1回コードを提出する権利が与えられる。

1問目は完全に素面で問題の考察ができるため、どの問題を選ぶかがとても重要です。自分の実力を考慮し、とりあえずC問題を開きます。問題を読むと尺取りをやってくださいと書いてあります。僕は尺取りを書くのが苦手なので、1問目に尺取りを引くことができたので運がよかったです。ところで、コンテスト開始前にビールが届いていて、僕はそれをすでに3分の1ぐらい消費していたので、1問目を読み始めたときにはそれなりに酔っていました。ビールは千葉の地ビール（IPA）でした。

若干、回りが悪い頭でコードを書き始めます。とりあえずかけた状態でサンプルを通すと答えが合いません。なぜでしょうか？出力するものが違いました。早速訂正してサンプルを走らせてみます。合いませんでした。

自棄になって手羽先のから揚げを食べます。私は、名古屋紹介マンガの八十亀ちゃん観察日記を読み、手羽先の効率的な食べ方を学習していたので、効率的に手羽先を食べることができました。

八十亀ちゃんかんさつにっき: 1 (REXコミックス)

手羽先を食べている間に直すべき場所に気が付いたので、提出します。AC。

そこそこ厄介な問題を倒したので、次は簡単なものを解くことにします。A問題を読むと、長さkの部分文字列をsetに突っ込んで、要素数を出力してくださいと書いてあります。実装して提出します。AC。

このころには2杯目のビール（地ビールのスタウト）とグレープフルーツジュースが届いていました。酒を飲んでいる途中にソフトドリンクで休憩を入れるのは酒飲みの常識です。

ビールを飲みつつ、B問題を開きます。人口の和を計算していじいじすると解けると書いてあります。Kotlinでちょっとカッコよく解いてやろうと色気を出して若干時間がかかります。AC。

D問題を開きます。+で文字列を分割して、0を含まない文字列の個数を数えてくださいと書いてあります。実装して提出するとACします。

この時点で3位でした。

E問題を開きます・・・えぇ・・・めんど・・・ 酔った状態でナップサックの3種類の実装をするのはつらすぎます。ちまちまコードを書いていましたが、全然終わる気がしません。また、自分の飲酒量の限界を感じていたので、かけたとしても提出するのは絶望的だなと思いました。

残り15分ぐらいで順位表を見ると、hogloid君、amylaseさん、sigma425君が全員自分より下の順位にいます。皆さんがご存じの通り、彼らはとても強いので、彼らのうちだれか一人よりも上の順位を取ると僕の中では大金星です。そのあとhogloid君は1問解いて僕より上の順位を取りました。さすがです。

最終順位は6位でした。

amylaseさんとsigma425君にプログラミングコンテストで勝てたことを一生自慢していこうと思います。

その他

レストランから出たらとりあえず水を買いに行きました。忘年会1次会で飲み物が提供されるものだと思っていましたが、すぐには提供されないようだったので、kenkooooさんと外のコンビニで10本ぐらい買ってきました。

自宅に帰るまでエチケット袋を使う機会が訪れなかったので良かったです。

飲酒Ratedコンテストの楽しみ

この記事はCompetitive Programming (2) Advent Calendar 2019の21日目の記事です。

飲酒は20歳になってからです。未成年の人は20歳になってから読みに来てください。

僕がRatedコンテストにお酒を飲みながら参加している理由と、（自分の中での）レギュレーションについて書きます。

飲酒Ratedをやっている理由

Twitterを検索すると、遅くとも2018年の8月ごろから自分は酒を飲んでからAtCoderのRatedコンテストに参加をしているようです。

MUJINコンの準備です pic.twitter.com/y2BWn7fupW

— アルゴリズムを背負う男 (@blue_jam) August 4, 2018

飲酒をしながらコンテストに参加をするようになった一番の理由は、自分がレートが下がることを恐れてコンテストに参加しなくなっていたからです。当時の自分は長いこと精進もしていなかったし、コンテストに参加してもレートが下がることは確実でした。

そこで、酒を飲みながらコンテストに参加すれば、レートが下がっても酒のせいにできるのではと考えました。我ながら最低です。

あと、土日はみんな酒飲みたいだろ。

飲酒Ratedのやり方

最後に、自分なりの酒を飲んでからコンテストに参加する方法を書いておきます。

1. コンテスト開始10分前ごろを目安に酒の準備を始める。
   • 目安はビールであれば320ml缶1本、日本酒はグラスに一杯(200ml)。気分によってはカクテルを作る。
   • 居酒屋等に行きたければ、開店時刻（大体の店は17時ぐらい）を狙っていく。開店直後は人が少なく、一人でも入りやすいのでお勧め。店で飲む場合は、飲み会で飲む量を飲む（自分の場合はビール中ジョッキ2,3杯程度）。一人で行くと、長くても二時間程度で満足するので、コンテストに間に合うように帰る。
2. 飲酒Ratedを実行する意思表示を行うため、今から飲む酒の写真をTwitterに投稿する。

   ABC参加準備、ﾖｼｯ! pic.twitter.com/qlC4jnFB6u

   — アルゴリズムを背負う男 (@blue_jam) November 24, 2019

   • 何を飲んだかわかるように、缶や瓶のラベルが見えるように写真を撮るとなおよい。
   • カクテルの場合は、メインとなるリキュールの瓶を写す。
3. 酒を飲みつつ、飲料水(0.5 ~ 1L程度)を準備する。
   • 酒を一杯飲み終えた後、コンテスト中は水を飲む。これにより、簡単な問題を解く序盤は頭が回らないが、難しい問題を解く終盤には頭が冴えてくる。
   • 簡単な問題を酔った状態で解くのはかなり楽しい。

オンサイトコンテストスタッフのおしごと

この記事はCompetitive Programming (2) Advent Calendar 2018 - Adventarの15日目の記事として書かれました。

この記事で言いたいこと：

ACM-ICPC OBOGの会では、競技プログラミングが大好きで、ICPCを引退した人達を常時募集しています！

FrontPage - ACM-ICPC Japanese Alumni Group

競技プログラマの皆さん、今日も一年お疲れ様でした。今年はオンサイトコンテストに参加できましたか？今年、僕はオンサイトコンテストに4回参加しました・・・スタッフとして。内訳は、IOI、所属企業主催のコンテスト2回とICPCアジア地区予選横浜大会です。

この記事では、今年の経験をもとに非企業コンテストのオンサイトスタッフの仕事を紹介します。

どんな人がスタッフをやっているのか

IOIやICPCのスタッフは主に次の2種類に分けられます。

• コンテスト周りの仕事をするスタッフ
• コンテストとは関係のない仕事をするスタッフ（受付やクロークなど、通称学生バイト）

前者は競技プログラミング経験者が担当します。後者はコンテスト会場近隣の大学またはホスト校から来ていることが多い印象です（詳しい出元はしらない）。この記事では、主にコンテスト周りの仕事をするスタッフの話をします。

コンテスト周辺の仕事をするスタッフを競技プログラミング経験者から選出する理由は、僕が効いた範囲では

• コンテストのルールを把握している
• 印刷物を配布の失敗がコンテスタントに影響を理解している

という部分が大きいそうです。後者はコンテストの結果や公平性に大きな影響を及ぼしかねないので、特に重点を置いているように感じます。

スタッフの年齢層はコンテストの選手よりも高めになります。理由は

• 参加権を持っている人たちはコンテストに参加している（それはそう）
• スタッフの募集がOBOGの会に送られている（ICPC）
• 選手の年齢が若すぎる（IOI）

といったところでしょうか。ICPCにおいては、参加権を失っていると（WF2回出場引退の猛者でない限り）修士2年以上になるので、社会人の割合が多くなります。

突然ですが、ここでオンサイトコンテストの楽しみ方を紹介します。

そういえば、オンサイトプロコンの社会人スタッフを眺めながら、「日本の平均年収を上回っている人達が、風船配りなどの雑用をほぼ無償でやっている」と考えると、めちゃくちゃ笑えてくるのでおすすめです。

— 見下げ果てた先輩 (@blue_jam) December 8, 2018

事前にスポンサー企業の求人を調べておくと、年収の下界がおおよそわかるので、より楽しめるようになります（スポンサー企業に属しいているOBOGも多い）。スタッフの中に所属企業がわかっている人がいれば、その企業の求人を調べましょう。

スタッフの仕事

ICPCのスタッフの仕事は次の記事でも紹介されています。

ratea.hatenablog.com

仕事の割り当てはコンテスト直前まで決まっていないことが多いです。仕事の割り当ては、コンテスト前日・当日に状況に応じて運営を管理している先生が割り当てたり、あるいは、人が足りていない場所に自主的にカバーに行ったりして決まります。

会場の準備・後片付け

会場の準備では

• 電源・ネットワーク・マシンの配置・回収
• マシンのセットアップ・確認作業
• 椅子の配置
• 配布物（Tシャツ、飲み物、マニュアルなど）の配置
• 風船の準備（ICPC)

を主に行います。ICPCでは、会場の準備・後片付けに学生バイトの人たちも加わっていました。

電源・ネットワーク・マシンの配置がどの程度スタッフの仕事になるかはコンテストによって異なります。

IOIでは全部業者がやっていました。

今年のICPCで普通のスタッフが行った電源・ネットワーク・マシンの配置は、配線の固定程度でした。ただし、今年はコンテストと懇親会が同じ場所で行われたため、電源・ネットワーク・マシンはコンテスト終了後にスタッフ総出で片づけました。

受付・クロークの支援(ICPC)

受付・クロークは学生のバイトの人が行いますが、時々コンテストルールに関わる質問が選手またはバイトから出てきます（「これは持ち込み可能か？」）。それらの質問についての回答はコンテストのルールを把握しているスタッフが行います。

手荷物検査

非企業コンテストではコンテスト会場に持ち込めるもの・持ち込めない物が定められています。選手入場時に持ち込めないものがないかチェックします。

コンテスト中の仕事

コンテスト中は主に次のことをやります。

• 物の配達（風船、印刷物、食べ物）
• コンテスト会場のパトロール
• トイレの案内（IOI）
• 解説中継（よく知らない）

大部分のスタッフは物の配達かコンテスト会場のパトロールになります。

コンテスト会場のパトロールでは、マシンやネットワークでトラブルがあったときに対応するのが仕事になります。（大体の場合は、困っている人を見つけて、対応ができる人を呼ぶまで。）

スタッフをやることの利点

コンテストグッズ

スタッフをやるとコンテストグッズ（主にTシャツ）がもらえます。僕はこれで1週間分のアルゴリズムTシャツを手に入れました。また、ICPCではスタッフとして参加したことの証明書（Certificate）がもらえます。

慰労会が行われることがある

コンテスト運営の思い出話を話すオフ会です。

観戦ができる

コンテスト中はスタッフ控室で問題や順位表を眺めています。おそらく、最もコンテスト会場の近くで観戦ができます。（もちろん仕事が最優先ですが）

スタッフをやるようになった理由

僕がスタッフをやるようになった理由は「ICPC OBOGの会に勧誘されたからなんとなく」です。僕がICPCに参加していた頃はかなりOBOGの会の勧誘が盛んだったので、引退とともに直ちにOBOGの会に入会しました。

そして、社会人になって東京に来て、「ICPCのスタッフを募集します」という案内を見て「お世話になったコンテストだから、手伝いたいなぁ」という（わりと軽い）感じでスタッフに応募しました。

軽い決意でスタッフに応募して、行ってみると大変でしたが、参加して後悔したことはないです。理由は、コンテストが終了すると「無事に終わってよかったな」という達成感があることと、何よりコンテスト終了後にコンテスタントが楽しそうにしているのを見ると嬉しいからです。コンテストに参加している選手を見ていると、今まで選手として参加していい思いをさせてもらった分を、次の世代につなげられているという喜びを感じます。おそらく、これからも可能な限りスタッフとして参加し続けるのだと思います。

ところで、ACM-ICPC OBOGの会（通称JAG）では近年スタッフの高齢化が進んでいます。また、最近はICPCのスタッフの集まりが悪いという危惧が上がっていたりします。競技プログラミング経験者で、ICPCの参加権を失った人はぜひJAGに入会をよろしくお願いいたします。

FrontPage - ACM-ICPC Japanese Alumni Group

JAGのICPCスタッフ以外の仕事内容は次のブログ記事に詳しく載っています。

kujira16.hateblo.jp

番外編：交通費や宿泊費を出してもらうのは申し訳ない？

時々、「スタッフに興味があるけど、遠方に住んでいるので交通費や宿泊費を出してもらうのが申し訳ない」と言ってスタッフに応募することを躊躇している人を見かけます。実際、修士2年のとき僕は福岡に住んでいたのでICPCスタッフとしての参加を見送った経験があります。

実際にスタッフになって経験を積むと「学生はそんなことを気にしなくていいのでどんどん応募してほしい」という気持ちになってきました。コンテストを運営している偉い人たちはスタッフにお金がかかることよりは、必要な人数のスタッフが集まらないことを心配していることの方が多いような気がします。IOIでもICPCでもスタッフが足りないのではないかという危機感が漂っていました。

コンテストを運営する上での一番の問題はスタッフが集まらなくて、コンテストの運営が成り立たなくなることです。経費のことは気にせず、どんどんスタッフに応募してもらえたらと思います。(十分な人数が集まって、遠方から人を召喚する必要がなくなったら、運営側からお礼兼お断りのメールが来ると思うので、みんな気にせず応募しましょう。)

The Even More Incredible Machine

この記事はプログラマーにオススメしたいゲーム紹介 Advent Calendar 2018の8日目の記事です。

この記事では、The Even More Incredible Machine（日本語版はもっともっとインクレディブル・マシーン）を紹介します。 Incredible Machineはルーブ・ゴールドバーグ・マシーンを作るゲームのシリーズです。ルーブ・ゴールドバーグ・マシーンというのは、単純な作業を手の込んだからくりを使って遠回りに実現する装置のことです。いわゆるピタゴラ装置ですね。

The Even More Incredible MachineはIncredible Machineシリーズの2作目で発売年は1992年（日本語版は1995年）だそうです。僕は小学生の時に、家にあった古いWindows 95のノートパソコンで遊んでました。

めちゃくちゃ古いゲームですが、現在はGOG.comというストアでWindows XP,Vista,10で動作するものが購入するできます。なお、The Even More Incredible Machine単体での販売ではなく、シリーズの数作がまとまったMega packが約$10で購入できます。お得ですね。（GOG.comで購入できるMega packはWindowsのみ対応らしいです。昔はMacで動くやつも販売されていたらしいんですが。）

ゲームの形式は次のようになっています。

• 各ステージ毎に課題と道具の初期配置（固定）、自由に配置できる道具のセットが与えられます。
• 自由に配置できる道具を配置して、課題をクリアしたら勝ち。

一つだけ例をやってみます。

このステージでは一番右の蝋燭に火をつければ勝ちです。自由に使える道具は画面右側のツールボックスにあります。今回はシーソーとロープ、滑車、虫眼鏡、懐中電灯、白熱電球（スクリーンショットでは隠れている）です。

課題を解決するには例えば次のように道具を配置します。

これを動かしてみると次のようにして課題が解決できます。

1. バケツが重力に従い落下し、一番左の白熱電球を灯す
2. 虫眼鏡を通った白熱電球の光がロケットに火をつける
3. ロケットが発射し上に向かう。途中でダイナマイトに火をつける
4. ダイナマイトが爆発して、ボウリング球を右側に飛ばす
5. ボウリング球が懐中電灯のスイッチをつける
6. 懐中電灯の光が虫眼鏡を通ってロケットに火をつける
7. ロケットが発射し、シーソーにぶつかる
8. シーソーにつながれたロープが滑車を通して、白熱電球を灯す
9. 白熱電球の光が虫眼鏡を通ってろうそくに火をつける

動画で見るとこんな感じです。

ちなみに、このゲームにはフリーエディットモードがあり、使える道具の制約なしに自分の好きなルーブ・ゴールドバーグ・マシーンを作ることができます・・・と聞くと半加算器を実装したくなるのが人情というものですよね。せっかく「プログラマーにオススメしたいゲーム紹介」という企画だったので、そこそこ頭をひねって実装してみました。

1bit半加算器

これが俺の答えじゃー！（ババーーン）

左側のスイッチ付きコンセントが入力装置です。スイッチの上に野球ボールを置くと1、置かないと0とします。 右側の家は下位ビットの出力です。家の中に人が入ると1、入らないと0です。 右側の猿が乗った自転車が上位ビットの出力（桁上がり）です。猿が自転車をこぐと1、こがないと0です。

動作させるとこんな感じになります。（野球ボールの位置をミスって何回かトライしてます。）

AND回路の実装は簡単だったのですが、XORの実装方法を考えるのが難しかったです。何度、YouTubeで検索しそうになったことか・・・

お付き合いいただきありがとうございました。

競技プログラミングコンテストカレンダーを作る（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のボランティアへの参加を希望します． 現在は<会社名>で<役職>として働いています．

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

[参加]

• 第9回日本情報オリンピック 本選
• パソコン甲子園 2010
• ACM/ICPCアジア地区予選 (2014年, 2015年)

[運営]

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

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

--

<名前>

<メールアドレス>

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

jp.ioi2018.jp

ARC094 D: Worst Case

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

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

概要

D - Worst Case

解法

とする．

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

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

したがって，解はぐらいになりそう．ただし，微妙に意地悪なケースがあって，

• が平方数のとき，先述の値から1をひかないといけない（について重複して数え上げを行っているため）
• のとき，さらに1をひかないといけない（高橋君の順位を使うことができないため）

また，は最大で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;
}