複数バージョンのDコンパイラを切り替えて使う

趣味の開発にD言語を使いたくなったので 人生最良の選択 *1 をしようと思いました。

今までの僕のD言語の用途は専ら AtCoder だったので、ローカルにはジャッジ環境に合わせた DMD v2.070.1 をインストールしていたのですが、これは 人生最良の選択 としては少々古すぎます。 しかしながら AtCoder のためには古いバージョンも持っておきたい……というわけで表題の通りです。

Digger という bisect ツールがあるのですが、これが今回の目的にも使えそうな感じだったので使っていきます。 以下、OS は Window を想定していますが Linux などでも大差ないと思います(多分……)。

下ごしらえの手順は以下の通り:

  1. 最新の DMD をインストールする: https://dlang.org/download.html
    • 最新版なら dub も一緒にインストールされるはずです
  2. dub fetch digger で Digger をグローバルにインストールする
  3. 適当にディレクトリを掘る (以下ここを wd とします)
  4. wd で dub run digger -- build ... を実行し、古いコンパイラをビルドする

以上で wd/work 以下に古いコンパイラ(を動かすために必要なファイル群)が生成されます。

古いコンパイラを使いたいときには:

  1. wd に移動する
  2. dub run digger -- install

dmd --version でバージョンをチェックして古くなってたら成功です。

digger install は 現在のD環境を wd/work 以下のファイルで 部分的に 置き換えます。 その際、 <path to dmd>/.digger-install に元のD環境を復元するために必要な情報が格納されます。

元に戻すときには、dub を 経由せず、digger uninstall のように Digger の実行ファイルを直接叩きます(切り替え先のコンパイラのバージョンによっては dub run digger -- uninstall が動かない可能性があるからです)。 Windows の場合には digger.exe が AppData\Local\dub\packages\digger-<version>\digger にあるはずです。

*1:https://qiita.com/outlandkarasu@github/items/84cc41c37d6c82f75f62#dmd%E3%81%AE%E3%82%A4%E3%83%B3%E3%82%B9%E3%83%88%E3%83%BC%E3%83%AB

JSC2019決勝参戦記

はじめに

この記事はへっぽこ水色コーダーによる AtCoder 第一回日本最強プログラマー学生選手権決勝 (JSC2019) の参加記です。 当日の出来事を時系列順に思い出すままを綴った散(らかった)文という捉え方もあります。そういうわけなので文章まとまってません悪しからず。

なお、戦績だけ先に書いておくと、196人中183位でほぼドベ、正のスコアを得た人のうち下から2番目です。 予選通過ボーダーギリギリだったことを考えると順当ではあるものの、もう少し頑張れた気もして悔しい。

時系列順振り返り

会場まで

会場は新橋の電通ホール。駅から徒歩4分だそうだが、絶対迷子になるという確信めいた予感があったので早出することに。

京浜東北線が遅れていて朝から幸先が悪い。重ねて腹を下して途中下車。受付TLE*1あるぞこれ。

早出が功を奏して受付に間に合うが、代償に昼飯の時間を失う。食後は頭回らなそうだしまあいいか……

会場着から開会式前まで

受付で名札を受け取り、ユーザネームを書き込んで首から下げる。オフ会みたいだなあ。

受付を抜けて競技会場までの僅かな距離の間に、にっこにこしたスポンサーの人事の方？に拉致られてスポンサーブースに引きずられてしまった。各社担当者さんから大量の資料、特に VOYAGE さんからは社名ロゴの入ったチロルチョコを頂いた。昼飯！！

やっぱり学生を釣るなら飯ですよ。そういうわけなので社会人各位は焼き肉を奢ってください。

競技会場に入る。ホールであって前方にステージとスクリーンがあるということを除けば TOEIC の試験会場のようなレイアウトだった。長机が並んでいて競技者はそこに座る。試験会場と言うには前後左右の人が近すぎるかなあ。「すいません後ろ失礼します」って10回は言った。

初めてのオンサイトコンテスト*2なので、もう少しそわそわしてしまうかなと思っていたのだが、妙な安心感がある。これあれだ、abc *3の空気感に似すぎている。周りの人間全員僕より強いんだろうなーみたいなところが特に似てる(クイズよわよわ勢並感)。違うところと言えば、机が用意されていて、周りの人間がみんな TweetDeck かエディタを開いてることくらいだ。というか、プレスのカメラが周りにあるのに Deck 開いてるの度胸がすごいな。

PC 開いて電源(会場に用意されていた)繋いで、Wi-Fi(これも会場に用意されていた)のセットアップして、コンテストのために適当にディレクトリを掘って、で、何もすることがなくなったので TweetDeck を開いた。

開会式

10分ほど #jsc2019 のカラムをほげーっと眺めていたら、周りが急に静かになった。開会式が始まったらしい。

と、めっちゃテンション高い人が前で何か喋り始めた。もしかしてあの人は chokudai *4さんでは？

「わー生 chokudai 初めて見たー」「ところで開会式の BGM めっちゃエモいなサントラ欲しい*5」以外に感情がなかったため、何を喋っていらしたのか全く記憶にない。各位頑張ってくださいとか言っていたと思う。

大会前にかっこよさげな BGM かかってるとことか完全に abc やんけ。

コンテスト本戦

ここで競プロに詳しくない人のためにざっくりとルールを説明しておくと: 競技時間は3時間。問題は A から H まで8問用意されていて、配点は 300-400-700-800-800-800-1200-1400。競技時間中に正しいプログラムを作成して提出すればその場で点数に加算される。順位は点数順、次いで「最後に新規の正答をした時刻」の早い順に決定する……といった感じ。

問題の難しさと配点には強い相関がある(それはそう)ので、配点だけ見れば大雑把な立ち回りの方針が立てられる。ABC *6の問題で言えば、僕は500点以下なら概ね解けて、600点は解けたり解けなかったりして、700点以上はもう無理という感じなので、今回はA問題(300点)とB問題(400点)に全時間をかけることにした。

さて、ほとんど前置きらしい前置きもなく、サクッと本戦が始まった。ところで、コンテスト開始までのカウントダウンするとことか完全に abc だった。やっぱこれ abc だな？

早速A問題に目を通す。数列 A, B が与えられ、 a_i + b_j = a_k + b_l を満たす組 (i, j, k, l) (i \neq k, j \neq l) を2秒以内に探す問題。ただし数列の長さは {10}^5 くらい。

と、右隣の人が驚異的なスピードで打鍵し始める。僕は下手すると非プログラマの人々よりタイピングが遅いので、めちゃ速い人の打鍵音を聞くと気圧されてしまう。というか、タイピングゲームとかと違って打つべきものは自分で考えなくちゃいけないのにその打鍵速度はおかしくない？本当に人か？え？ていうかもうこれわかったんですか？

隣の人の動きで動揺してしまうのとか、オンサイトならではだなあ。それはそれとして、よそはよそ、うちはうちと言い聞かせながら再度問題を眺める。与式は a_i - a_k = b_l - b_j だから、各集合の上で可能な差を全列挙すればいいわけだが、それだと2秒に間に合わない。脳死で半分全列挙では～～～～？？？とか言ってみるが、5秒ほどして冷静に考えて何も半分にならないことに気づく。……は？なんだこれ？

右隣の人のキーボードも静かになった。入力を拾う典型部分だけ先にコーディングするタイプの人だったのかな。やっぱこれ難しいですよね？と勝手に同族意識を持つ。

制約に \forall a \in A, \forall b \in B: 1 \leq a, b \leq {10}^6 とあるので、 |a_i - a_k| の値としてあり得るのは高々 {10}^6 通りしかない。任意の d (0 \leq d \leq {10}^6) に対して |a_i - a_k| = d なる (i, k) を O(\log |A|) くらいで見つけられればいいのか……？そんな方法ある？とか思いながらボールペンをゴリゴリと走らせるが何も得られず。

300点問題を解けないのはやばすぎでは……という考えに後ろ髪を引かれまくってA問題を粘ったが、1時間も過ぎたかというあたりでちょっと頭冷やそうと思ってB問題に移った。後から考えるとAからは即座に撤退すべきだった……。

B問題は x, y, z の3層からなる未知のネットワークに対して、 x- y の隣接行列と x- z の到達性を表す行列が与えられるので y- z の隣接行列を求める問題。ただし、各層のノードは高々 {100} 個。

直感的には正しそうなアルゴリズムがすっと浮かんだのでその通りに書いた。提出。TLE。余計なループが1つあるのに気づいたのでそれを外すと AC*7 できた。っしゃあ地蔵は避けられた。大体40分くらいかかった。

地蔵回避の安堵感から順位表を眺める。Aが解けているのが4割くらい、Bは9割くらいの人が解いていて、C以上を解けている人はほぼ皆無。やっぱA地雷だったんか……みんな見切りを付けるのが早くてすごい……。

赤コーダー*8 がうじゃうじゃいるのにほぼ解かれていないのはヤバすぎるので、当初の予定通りC以上には触らないことにした。残り時間をAにつぎ込む。

しかし何も進展を得られず残り時間10分を宣告される。やけになって謎の枝刈りを始める。 |a_i - a_k| = d なる (i, k) を探すのに O(|A|) かかる*9のはもう諦めて、 d の候補を絞ればいいのでは？ A の要素を数直線上にプロットして……隣接するプロット間の区間をプライオリティキューに突っ込んで……キューの先頭を引っこ抜きながら拡大した区間をぽこぽこ放り込めば……？オラ提出だ食らえ！

びっくりしたことに TLE にならなかった。ならなかったが、1ケースだけ WA*10 した。でももうバグを取る時間は残っていない。

この最後の特攻とほぼ同時にコンテストが終了した。chokudai さんがお疲れさまでしたーみたいなことを言って会場拍手。やっぱこれ abc の 1R でしょ*11。

コンテスト終了後

順位表は終了30分前時点で凍結されたので、最終的な順位は発表を待たないといけない。が、30分前時点でもA問題の AC 率は競技中に一度見たときと大して変わっていなかった。つまり A と B が解けるだけで上位 50% だったということになる。それ以外の人々 は B しか解けていない。世紀末みたいな問題セットだ。

競技終了後に #jsc2019 に流れたツイートを見るに A は鳩の巣により全探索が許されるとかなんとか。……あ？………あああああああ！！！！！

内心絶叫しているうちに順位発表が始まる。上位20位は前で表彰されて賞金も出る。僕でも名前は知っているようなつよい人々が順当に表彰されていった。C以上の問題を2つ正解できれば大体20位以上だったっぽい。表彰された人も全員がAを解けたわけではないようだが、赤コーダーが解けない300点問題って何？？？？？

続いて関係各位から短めのお話が何本か、そしてトークセッションがあって、色々とぶっちゃけたお話を聞けたりした。「競プロができれば就活は無敵みたいに思ってる人いますけど、まずみなさんは会話ができるようになりましょうね」みたいな。耳が痛すぎてもげた。他にも面白い話題は多くあったが、詳細は割愛する。

その後、懇親会まで1時間強の休憩が入り、会場設営のためにみんな外に出された。昼飯がまだだったのもあって、行きに見つけた怪しい蕎麦屋で腹ごしらえ。結構美味しかったのでおすすめ。

会場に戻るとあちこちに人の輪ができてたので、適当なところに入れてもらう。「オンサイトだと参加者を予選か何かで絞らねばならず、結果として毎度同じ面子になってしまう」みたいな話*12がちょっと印象に残った。確かに上位陣には身内ノリらしいものが存在したように見受けられたし。これ、競技クイズ界隈の文脈にもそのまま当てはまる話だよなあ。

懇親会は身内がひとりもいないので厳しいかと思われたが、たまたま同じ大学のはじめましてな人がいたのでずっと喋ってた。実質身内で話していたようなもんだ。会話ができねえんだなあ……。

ところで、懇親会めちゃ豪華な料理が出たんですよ。知ってたら蕎麦食わなかったのになあ！

雑感

学生限定で、しかも予選通過枠200人という大規模な大会で、加えて予選でたまたま運が良かったからオンサイトコンテストなんてものに出られたわけで、貴重な経験だったなあという。

最近しみじみと感じていることに、わりとしょぼいことでも評価してもらえているのは、評価の先頭に「まだ学生なのに」が付くからなんだよなあというものがあって、今回のもそのひとつだと感じている。学生の紋所も来年度からはもう使えないわけだし、素の腕力を鍛えていかないとなあ。

*1:制限時間に間に合わないことを表す競プロ用語

*2:自宅から参加するオンラインコンテストに対して、物理的な会場に集まって行うコンテストのこと。

*3:競技クイズの学生大会。AtCoder Beginners Contest とは無関係。

*4:AtCoder の社長。

*5:大会通して随所で BGM が挿入されていたが、どれもこれも非常に好みだった。かっこいい。

*6:オンラインコンテストの AtCoder Beginners Contest のこと。競技クイズの学生大会とは無関係。

*7:正解することを表す競プロ用語。

*8:要するに競プロのランカー。

*9:愚直にやれば O(|A|^2) だが、長さ {10}^6 の配列を用意して A を埋め込めば O(|A|) になる。

*10:誤答を表す競プロ用語。

*11:abc の最初のラウンドでは全員が一斉に黙々とペーパークイズを解く。で、終わった瞬間にみんなで拍手する文化がある。

*12:話の主旨からは外れた抜粋ではあるが。

水色になった

こんな本質から外れたことばっかやってるから水色になれないんだぞ。(前回記事末尾より)

水色になれました。嬉しい。

TL;DR

これは「AtCoder で水色になれたのが嬉しすぎてなんか書きたくなった」というだけの記事です。それでも敢えて要約するならば:

  • 競プロは楽しい
  • 全探索と簡単なDPが書けると、運が良ければ水色になれる。
  • 就活のコードテスト対策に競プロは部分的に有効だが、すべての出題傾向には対応できない。競プロ傾向の問題への対策だけならば AtCoder の緑色レベルで十分。

本編

水色になった

「じっくり時間をかけてでも、コードが Readable であるように努めるべきだ」という宗教上の信条により Readability に無頓着な*1競プロは若干敬遠していたのですが、あるとき Twitter で流れてきた初心者向け問題が時間をかけても解けなかったのが悔しくて競プロに手を染めてしまいました。 そもそも解けないんじゃあ信条も何もないわけで。やらないだけなのとできないのは違うよなあという話です。

実際手を出してみれば問題はパズルみたいで面白いし、時間に追われるままガーッと書き上げるのも脳内麻薬が出てイイ感じだなと思えるようになりました。やっぱり食わず嫌いは良くないんだなあ。

で、この度、当面の目標だった水色に到達しました。わーい*2。

f:id:penpenpng:20190722202050p:plain

ところで余談ですが、去年中頃からのグラフにプロットがやけに少ないのはしょうもない事情があります。 というのも、この調子でレートグラフを更新していくとちょうど就活の時期に僕がただのクソザコナメクジであることが御社にバレてしまうのではみたいな……。別に就活のためにやってたんじゃないんですけど、だからこそ趣味を理由に評価を下げられたくないなみたいな……。

でも最近見かけたこの辺を読むに、もしかしたら前面に押し出していってもよかったのかもしれないです。過ぎた話なので分かりませんが……。

水色になるまで

何かを練習するとき、「とりあえずやってみる」と「本か何かで理論を大雑把に把握する」をちょうどいい塩梅で並行するのが最も効率がいいと経験上感じています。感じてはいるのですが、僕はどちらかというと後者が好きなので座学に偏重しがちで、コンテストに参加する前にとりあえず蟻本を通しで読みました。読んだだけで体では分かってないやつです。

そのうち実際に問題を解いていくうちに、水色を目指すレベルでは「蟻本の2章を体で理解すること」「分かる問題でバグらせないこと」が重要っぽいことを察したので、そのあたりをちょっとやりました。具体的には:

  • 蟻本2章の写経をした上で、紙とペンで絵を描いて動作を追う。該当章の内容は:
  • コーディング中に考えることを少なくすることで、バグを埋めるリスクを減らす。
    • 0-based indexing な言語で 1-based indexing な問題を解くときには先頭にダミーを挿入するなど、問題文中の表現とコード中の表現を可能な限り一致させる。
    • 積極的に部分問題を(できれば純粋な)関数に分離する。
    • 番兵を使う。

これで足りたのは問題運が良かっただけかもしれないなーとは思います。そのうち僕がまた緑に落ちたらそういうことです。

就活と競プロ

別に就活のためにやってたんじゃないんですけど、

とは言うものの、実際のところ大分役に立ちました。

前述の通り、ナメクジを晒したくなかったので面接で特に競プロ経験を主張したりはしなかったのですが、とりわけ面接前のコーディングテストでは大いに役立ちました。

どうも同じIT系でも業界ごとに傾向は随分と違うようですが、少なくとも僕が受けたようなところが コーディングテストで出題する問題の半分くらいは AtCoder で言うところの緑色以下の問題で、もう半分くらいは競プロっぽくない問題です。 競プロっぽい問題については皆さんご存知の通りですので、競プロっぽくない問題について言及すると、例えば

  • Webサーバ の URL と Web API の仕様が与えられ、これを叩く問題
  • ハフマン符号を構成する問題(何故か複数社で問われた)

みたいなのが出ました。後者は僕が知らないだけで競プロにも出るのかも。

これから

次は青色になりたいです。どうすればいいかはこれから考えます。

*1:少なくともジャッジサーバは可読性をスコアに反映しないという意味で、それ以上にネガティブな意味はないです。

*2:次回のコンテストで普通に緑に落ちかねないので今のうちに喜んでおこう。