Code Thanks Festival 2017 参加記

Code Thanks Festival 2017に参加してきました

12/2(土)に行われたCode Thanks Festival 2017に参加してきました. 運良く予選で良いパフォーマンスを出すことができて, 参加権を勝ち取ったという感じです.

www.recruit-jinji.jp

会場到着まで

起きると脳が直感的に開始時刻に間に合わないことを理解した. 開始時刻が11:25なのに対して僕が起きた時刻が10:30, 会場のお台場まで1時間はかかるのでどう考えても間に合わない. とにかく家を飛び出した. 久しぶりのゆりかもめに揺られながら会場への到着を待つ.

あの、報告なのですが、遅刻が確定しました()

— Shinya Kato (@0x19f) 2017年12月2日

結局なんとかコンテスト開始前には会場にたどり着くことができ, ほっと胸を撫でおろす.

コンテスト

コンテストは100 - 200 - 300 - 300 - 400 - 500 - 600 - 600の計8問. 1800点以上だとパーカーがもらえるとのことなので1800点を目標に頑張ろうという気持ちになる.

コンテスト開始と同時にA, B, Cと順調にACしていく. D問題には少し苦戦した, 制約を見るにgcdなんだろうなぁと思うのだがどうすればいいのかわからない. いろいろと悩むが, 高校数学で教わった1次不定方程式を思い出しAC. あと2問でパーカーだ.

しかし, ものごとはそう順調には進まない. E問題がインタラクティブ形式, 問題を見てすぐに13の累乗をクエリとして出力すればいいと思った. しかし, これが罠だった. よくよく考えると13⁴は10000を超えてしまうのだ. 頭のついていない僕はこのことに気づくのに30分を要した. 問題を読み始めてから1時間ほど経つが一向に糸口がつかめない. 焦りばかりが募っていく. 落ち着け, まだ問題は他にもあるんだ, そう自分自身に言い聞かせた.

心を切り替えてF問題を読んでいく. 制約が小さければ, 単純なDPだ. しかし, 制約が大きい. 代わりに和が一定で抑えられるという謎の条件が付け加えられている. 瞬間的に頭にルートという言葉が浮かんできた. そうだ, 何かがルートで抑えられるに違いない. 大量のWAを出しながら, 一歩ずつ答えに近づいていく. 残り40分というところでついにFを通した.

ここで, 苦戦していたEに戻る. これを通せばパーカーだ, 何としても通したい. なんらかの方法でクエリからコインの重さが復元可能なのであれば, 和と5種類のコインの重さの組は1対1に対応するはずだ. そう思い手当たり次第にいろいろな枚数の組み合わせで, このような条件を満たすものを探し始めた. すると5の累乗であればこの条件を満たすことを発見した. 残り20分, まだ焦る時間じゃない. そう言い聞かせながら, 不恰好なプログラムを書いていく. クエリの応答からコインの重さを逆引きするテーブルを作りそれを参照する作戦だ. 一心不乱にコピペを駆使してプログラムを書き上げ, 提出した. 結果は......AC. 残り時間は10分だった.

結果は参加者100人中の54位. なによりも1800点を達成できたことが嬉しかった.

表彰 and 解説

大学の先輩であらせられるtossyさんが1位だったり, imulanさんが3位だったりして, やはり目指すべきはあそこなんだなぁと思った. ふーらくたるさんが折角の5位なのにマイクが入っておらずコメントが全く聞き取れなくておもしろかった.

ふーらくたる「%$*#(@(*W)$#)($#(@」

— Shinya Kato (@0x19f) 2017年12月2日

あと, chokudaiさんはファッション英語勢なのかと思っていたけれど, 本当に英語苦手みたいだった.

懇親会

TLのみなさんにこんにちは. 名前入りの名札を見て「あの赤いCの人」とわかってもらえるのは非常に便利なので, みなさんも実名Twitterしていきませう. 懇親会の間にtreeoneさんの通知が400件溜まっていたらしく, 本当におもしろい.

解散の後も参加者の方々とボーリングしたりカラオケしたりしてきました. いやー, 非常に楽しかったですねぇ.

【メモ】UNIX V6コードリーディング(クロック割り込み, p160〜170)

今回の内容

前回までは, 割り込みとトラップが発生してからハンドラが実行されるまでの流れを追っていました.

0x19f.hatenablog.com

今回は, クロック割り込みハンドラのお話です. クロック割り込みによって処理される指定時間実行とsleepシステムコールも一緒に見ていきます.

クロック装置

UNIX V6では以下の2種類のクロックが使用可能です.

• 電源周波数に従うクロック: KW11-L
• プログラマブルクロック: KW11-P

前者のクロックは電源周波数が50Hzか60Hzかによってクロック周波数が変わります. 後者のクロックの間隔などを設定することができるようです.

クロック周波数はparams.hの中でHZとしてdefineされているようです. 書籍ではどちらの装置を用いるにしてもクロック周波数が60Hzであるという前提で解説を進めています.

クロック割り込みハンドラ

クロック割り込みハンドラはC言語で書かれたclock関数になります. この関数に前回まで見てきた箇所で積まれたスタックの中身が引数として渡ります.

C言語で書かれている関数は, コンパイルの際に先頭にcsvというアセンブリで書かれた関数の実行が挿入されます. 簡単に説明だけしておくと, r2, r3, r4を退避する関数です. このcsvについては, 書籍の78ページから詳しく説明されています. (このメモを書き始める前に読んでます.)

csvが実行された直後のスタックの状態とclock関数の引数の対応は以下のようになります. 引数の内容がわからなくなったらここを見ましょう.

	値	引数	備考
sp	pc		csvから戻るのに使用されるだけ(あまり関係ない)
	退避されたr2
	退避されたr3
	退避されたr4
r5	退避されたr5
	pc(割り込みハンドラから返る先)
	マスクされたPSW	dev
	割り込まれたプロセスのsp	sp
	古いr1	r1
	PSW	nps
	古いr0	r0
	割り込まれたプロセスのpc	pc
	割り込まれたプロセスのPSW	ps

クロック割り込みハンドラの中身を読んでいくと以下の処理が上から順にされていることがわかります.

• クロック毎の処理
  • クロック装置のレジスタを再設定
  • 指定時間実行の処理を行う ... (1)
  • CPU時間のインクリメント
• 1秒毎の処理
  • 時刻のインクリメント
  • sleepしているプロセスを起こす ... (2)
  • プロセスの実行優先度を再計算 ... (3)
  • スワップ処理を継続できない場合の再スケジューリング ... (4)
  • シグナル処理 ... (5)
• 4秒毎の処理
  • lightning boltの処理 ... (6)

以下, いくつか数字を振ったものについて補足しておきます.

(1) 指定時間実行

これについては, 書籍の162ページから詳しく書かれています. 指定時間に実行したい関数を登録するtimeout関数などのソースコードが出てきますが, 書いてある通りに読めば難しい箇所はないと思います. クロック割り込みハンドラの中では, 指定時間になった関数の実行をしています.

(2) sleepしているプロセスを起こす

書籍の165ページにsleepシステムコールのハンドラであるsslepが掲載されているのですが, これだけでは少し何が起きているのかわからないのでメモをば.

まず, timeはグローバル変数で現在の時刻を秒単位で管理しています. いわゆるUNIX時間(？). この時刻データは, 2 word分(32 bit)に収められています. dpadd, dpcmpはこの2 wordをまとめて足したり比較したりするための関数です. 書籍の441ページに説明があります.

もう一つ関数の中に出てくるグローバル変数に, toutという時刻データがあります. これは, 次にsleepから起こされる関数が起こされる時刻を表しています.

個人的にここが今回得られた理解の中で一番おもしろかったのですが, sleepしているプロセスはtoutが示す時刻を過ぎたらすべて起こされます. そして, 指定された時刻を過ぎていないプロセスは再びsleep状態に戻ります.

これを実現しているのがsslep関数中のwhile文です. while文の条件が真になるのは, 指定された秒数分sleepした場合のみです. 真になるまでは, if文によって直近に起こさないといけないプロセスを起こす時間をtoutに格納して, sleep関数を呼び出しています. sleep関数については, 73ページにソースコードが掲載されています. sleep関数の第一引数には待っている資源のアドレスを渡すのですが, ここではtoutのアドレスを渡しています. clock関数の中でwakeup関数にtoutを渡して, すべてのsleep中のプロセスを起こしています. 起こされたプロセスはwhile文の最後から処理を再開し, while文の継続条件を判定してsslep関数から抜けるもしくは再度sleep関数を呼び出します.

このようにしてsleepシステムコールは実現されているわけですが, これって何かに似てるなーと思ったらJavaのマルチスレッドプログラミングで出てくるwait/notifyAllと同じようなもんかなという気持ちになりました. あれもnotifyAllですべてのプロセスが起きた時にwhile文でガードするってことをしますよね.

(3) プロセスの実行優先度を再計算

プロセスのあたりは一応読んだはずなのですが, 細かいところはかなり忘れているので再度読み直します...

(4) スワップを継続できない場合の再スケジューリング

スワップ辺りを飛ばしているので, あまりよくわかってないです...

(5) シグナル処理

シグナルの話は次の章に出てくるので一旦飛ばす.

(6) lightning bolt

lightning boltというのは, カーネルが特に待ち時間は決まっていないけれど適当に待たせておきたい時に使用するものらしいです. lbolt変数を待ち資源にしてsleepさせておくんでしょうか？ 4秒に1度clock関数の中で起こされます.

次回の予定

トラップハンドラの中身を読み進めていきたいと思います.

【メモ】UNIX V6コードリーディング(割り込み, p154〜159, その2)

今回の内容

前回の続きから.
アセンブリで書かれたtrapとcallを詳しく見ていきます.

0x19f.hatenablog.com

前回解決できなかった疑問点

nofaultが設定されている場合の割り込み箇所への復帰方法について, 前回の記事には,

もう一つわからないことがあって, この後のトラップハンドラからどうやってユーザープログラムに復帰するのかということ.

なんてことを書いたのですが, そもそも前提が間違ってました.
nofaultを設定した上で命令を実行するのはカーネルプロセスでした.
このnofaultというのは, カーネルプロセスが例外が起きるとまずい命令を実行する前に設定するというものみたいです.
ここからは推測ですが, こういった命令を実行する直前にカーネルはnofaultにエラーハンドラを設定しカーネルスタックに戻り先のアドレスを積んだ状態で命令を実行するのではないかと.
すると, 例外が起きた場合には, スタックに戻り先のアドレスのみが積まれた状態でnofaultが指すアドレスにジャンプし, その処理の最後にrtsで戻り先に復帰するという風になるんじゃないでしょうか.

こっちの方はわかってないのですが, 読み進めていく上ではあまり問題なさそうなので一旦スルーします.

ここが若干謎で, SR0の1ビット目が1になるとMMUが有効になるらしい.
しかし, なぜこのタイミングでSR0に1を格納しているのかがわからない.

trapでnofaultが設定されていない場合

nofaultに値が入っていない場合は, 前回軽く書いた通りSR0, SR2を退避, SR0を初期化してjsr命令でcall1へとジャンプします.
この時, 古いr0の値がスタックに積まれ, r0には_trap(C言語で書かれたtrap関数のアドレス)が格納されることに注意してください.

call1にジャンプすると, spをひとつ上にずらし, プロセッサ優先度を0にし, callの途中へとジャンプします.
ここからの処理は後述するcallでの処理とほぼ同じです.
callの1行目を実行した直後とスタック, r0の状態は同じ形になっている点に注意.

最終的なスタックの状態は以下のようになっており, r0にはtrap関数のアドレスが入っています.

	値
sp	トラップ種別を含んだPSW
	古いr0
	割り込まれたプロセスのpc
	割り込まれたプロセスのPSW

callの処理

前々回ぐらいのおさらいになるのですが, callに処理が移った時のスタックの状態は以下のようになっています.

	値
sp	古いr0
	割り込まれたプロセスのpc
	割り込まれたプロセスのPSW

ここにPSWの値が積まれて以下のような状態になります.

	値
sp	PSW
	古いr0
	割り込まれたプロセスのpc
	割り込まれたプロセスのPSW

ここからはtrapのnofaultが設定されていない場合と同じ処理になります.
スタックが同じような形をしているところに気をつけてください.

まず, 古いr1がスタックに積まれます.
次にmfpi命令を用いて割り込まれたプロセスのspをスタックに積みます.
mfpi命令はPSWの前のモードの仮想アドレス空間から値を取得して現在のモードのスタックに積む命令です.
ここで得たspを用いて割込みハンドラの中でスタックを操作するのかな？と予想しています.
さらに, SPWをスタックに積み, 下位5ビット以外を0でクリアします.

ここで, 割り込まれたプロセスがユーザーモードだったかカーネルモードだったかで処理が分岐するのですが, やっていることは大きくは変わらないです.

ユーザーモードだった場合は, jsr命令で現在のpcをスタックに積みながらr0に設定された割り込みハンドラにジャンプします.
ここで積んだpcが割り込みハンドラからの戻り先になります.
割り込みハンドラから処理が戻ると, コンテキストスイッチを行います.
割り込みによってプロセスの実行可能状態や優先度が変化した分を考慮するためのものかなと考えています.
最後に, mtpi命令で前モードのspの値を戻します.

カーネルモードだった場合は, PSWの前モードをユーザーモードに書き換えてから, 割み込みハンドラへジャンプします.
ここは上記と同様にjsrを用いています.

割り込みハンドラが呼び出される時のスタックは以下のような状態になります.
実際にはこれがハンドラ関数の引数として扱われます.
具体的にどのように使われるのかはclock, trapなどの関数を見ていくことになるかと思います.

	値
sp	pc(割り込みハンドラから返る先)
	マスクされたPSW
	割り込まれたプロセスのsp
	古いr1
	PSW
	古いr0
	割り込まれたプロセスのpc
	割り込まれたプロセスのPSW

ここからは両モード共通です.
スタックに積んでいたr1, r0を復帰してrtt命令で割り込まれた箇所に復帰します.

まとめ

ソースコードを読むだけだと理解しづらいので, 簡単にまとめておきます.

• カーネルは例外が起こりうる命令を実行する前にnofaultを設定することがある.
• nofaultが設定されているトラップは設定されたハンドラによって処理される.
• そうでないトラップはtrap関数によって処理される.
• 割り込みはそれぞれの割り込みハンドラによって処理される.

次回の予定

割り込みハンドラ(clock)とトラップハンドラ(trap)を読んでいく予定.

【メモ】UNIX V6コードリーディング(割り込み, p154〜159)

今回の内容

前回の続きから.
アセンブリで書かれたcallとtrapの実行を詳しく見ていきます.

0x19f.hatenablog.com

call, trapの実行

書籍ではあまり言及されていない箇所が多くあまり進みませんでした.
以下, ざっくりとした理解です.
(間違っている箇所がありそう.)

割り込みの場合は, callの内部でr0に格納された割り込みハンドラが呼び出されます.
このr0に割り込みハンドラが格納される箇所は前回見たとおりです.

トラップの場合は, nofaultにトラップハンドラが指定されている場合とそうでない場合で分岐が発生します.
nofaultにトラップハンドラが指定されている場合は, そのトラップハンドラが呼び出されます.
そうでない場合は, callの中へとジャンプしC言語で書かれたtrap関数が呼び出されます.
(アセンブリ中では_trapで参照されています.)

基本的には, スタックになにが積まれていくのかが大事なようです.
ちらっと先読みした感じだと, この後割り込みハンドラ/トラップハンドラに処理が移った際にこのスタックがC言語で書かれた関数の引数になるようです.

trap

トラップ種別が含まれたPSWの値をカーネルスタックに格納します.
trap関数内でこの種別によって処理が分岐するんでしょうか.
nofaultが0かで分岐するのをtst, bne命令で実現しています.

nofaultにトラップハンドラが指定されている場合:
SR0レジスタを1で初期化.
ここが若干謎で, SR0の1ビット目が1になるとMMUが有効になるらしい.
しかし, なぜこのタイミングでSR0に1を格納しているのかがわからない.
実は割り込みが発生したタイミングでMMUが無効になってたりするんでしょうか.
nofaultをカーネルスタック上の割り込みされたプロセスのpcが格納されている場所に格納.
rtt命令でnofaultが指すトラップハンドラに飛びます.
もう一つよくわかっていないのが, この後のトラップハンドラからどうやってユーザープログラムに復帰するのかということ.
rttによって割り込まれたプロセスのPSWとpcが元に戻されているところまではわかるのですが...

nofaultにトラップハンドラが指定されていない場合: あまり細かく読んでいないのでざっくりと. jsr命令でr0を退避, _trapのアドレスを代わりに格納してcall1にジャンプ. callの中へジャンプ.

call

全然読めてないです.
最終的には割り込みハンドラへと飛んでいく感じ？

次回の予定

もう少しcallとtrapを詳しく.

DDCC2017本戦に参加してきました

11/3(金)にDisco Discovery Channel Code Contest 2017の本戦に参加してきました.
予選ではC問題を解くのが遅めで本戦通らないかと思ったのですが, 19卒枠の繰り上がりで本戦に参加することができました.

https://discoverychannel.jp/ddcc/discoverychannel.jp

会場はDiscoのオフィスでした(200人も入れるスペースがあってすごい).
到着するとすでに多くの方がDDCC Tシャツに着替えて準備万端という感じでした.

コンテスト本戦

まずは, 10:30からコンテスト本戦.

ddcc2017-final.contest.atcoder.jp

コンテスト時間は2時間で問題は5問.
自分はABを解いて2完, 最終的な順位は200人中の88位.
90分間座ってるだけコンテストでした.

A問題:
問題を見た瞬間に第一象限だけ調べて4倍しようと思ったのですが, 200/Kや300/Kが奇数の場合に正方形の頂点がグリッド上に乗らないことに気づき場合分け.
結構時間がかかってしまいました.
円の中心を(0, 0)に置くって固定観念にとらわれなければもう少し楽に解けますね...

B問題:
サンプルを見てこれはA[i]とZのGCDを計算してLCMを取ればいいのでは？と思い書いてみたら通ってしまいました.
個人的にはAよりもBの方が簡単だと思います().

C問題:
何もわからない, ばなな.
そもそもグラフの上でループを考える時にどうすればいいのかが全くわかりませんでした.
解説を読んでもあんまり理解できてないです.

D問題:
一応目を通しましたが, 見た瞬間にわからなさそうだということがわかりました(？).

E問題:
実はC問題がわからなさすぎてコンテスト中はずっとE問題を考えていました.
まぁ, もちろん解けませんでしたよね.
これ以上辺を伸ばしたら直径を維持できないという状態になったあとは葉を選んで辺を伸ばしていけばいいと思ったのですが, その状態までがどうすればいいのかわからず.

お昼のビュッフェ

お昼は会場でビュッフェでした.
以前にオンサイトでお会いした方やTwitterではよく絡むけど実際には会ったことないという方と交流できて楽しかったです.

ただし, お腹いっぱいになってきたタイミングで寿司が出てきたことだけは許さない().

座談会

お昼の後は, Ponanza開発者の山本さんとプロ棋士の西尾さんの対談(with モデレーターのchokudaiさん)でした.

いろいろと面白いお話が聞けたのですが, 中でも興味深かったのがプログラムを生成する人工知能が今後どれぐらいの速度で成長するのかという話題.
競技プログラミングにおいても問題を解くAIというのがちょこちょこ研究されているらしいですが, 驚くことにそういったAIはすでにAtCoderのレートで言うと1000を超えてきているとのこと.

ちなみに, このAIはサンプルの入出力に合うようなプログラムをひたすら投げ続けるというものみたいです.
前日にDDCC参加者のみなさんとご飯を食べていた時に話題に出たのですが, 過去のAtCoderのコンテストでこの方法を使って3秒でA問題をACしたという事例があるそうです.
(探してみたけれどこれでしょうか？Submission #286413 - AtCoder Regular Contest 030 | AtCoder)

問題の内容を把握した上で正解を導くというのはまだまだ先になりそうですが, こういった無理やり試す系のものはこれからどうなっていくのか楽しみですね.
懇親会の時にも, CodeforcesなどのHackが可能なコンテストなら大量にプログラムを収集してきて適当な入力を入れてみて出力が同じになるものとそうでないものに分ければ後者をHackできるのでは？などといった話が出ていました.

他に印象に残っているのは, プロ棋士の方が機械学習のアイディアを取り入れて将棋の学習をしている話でしょうか.
細かいことは忘れてしまったのですが, 棋譜を学習データとテストデータに分けるらしいです.
いや, 凄まじいなと...

会社見学

会社見学ではA問題の元ネタ(？)であるシリコンウェハから正方形のチップを切り出す機械などを見せていただきました.
そもそも「Discoって何してる会社なの？」という感じだったので, 非常におもしろかったです.
ちなみに, シリコンウェハが円盤状なのはシリコンの単結晶が円柱状になっていてそれをスライスしてシリコンウェハが作られるかららしいです.

懇親会 & 記念撮影

懇親会も豪華で再びお寿司が出てきました.
なお, お寿司は一瞬でなくなりました.
一般枠で参加されていた大学のOBの方とお話ができたりもしました.

あと, 話題のchokudaiさん看板で記念撮影もしてきました.
僕はchokudaiさん本人が看板の写真と同じポーズをしている公式コラ画像(？)が一番好きです.

いまさらだけど #DDCC2017 pic.twitter.com/cFiIWEqMuA

— Shinya Kato (@0x19f) 2017年11月4日

最後は参加者全員で記念撮影.
コンテスト運営の方々, お話してくださった参加者のみなさん, ありがとうごいました.
CODE THANKS FESTIVALに参加される方はまた近いうちに, そうでない方はまたいつかお会いしましょう.

おつかれさまでしたー！！ #DDCC2017 pic.twitter.com/pH5sP86tF0

— chokudai(高橋 直大) (@chokudai) 2017年11月3日

【メモ】UNIX V6コードリーディング(割り込み, p144〜153)

勉強会の趣旨

UNIX V6ソースコードを読もうという会です.
この本に沿って読み進めてます.

はじめてのOSコードリーディング ~UNIX V6で学ぶカーネルのしくみ (Software Design plus)

月曜5限後にラーニングコモンズでひっそりやってるので興味がある方がいればぜひどうぞ.

これはその勉強会の内容のメモです. (自分が後から見返すよう程度なのであんまり参考にはならないと思います.)

今回の内容

10/30
第3部の割り込みから.
途中からメモを取り始めたので, 第1部, 第2部のメモはないです...
ざっとプロセスについて読んで, execあたりで心が俺て飛ばすことにした(forkあたりまでは読んだ感じ).

割り込み・トラップ

割り込み

• 周辺デバイスからの非同期的な要求を処理するための仕組み.

トラップ

• CPU内部で起こる出来事を非同期的に処理するための仕組み.
• 0除算, バスタイムアウトなどの例外発生をシグナルとして処理する.
• システムコールはトラップを用いて実現される.

割り込みとトラップの違いは, きっかけとなる要因が外部デバイスかCPUか.

優先度

割り込みには0から7までの優先度が設定される.
割り込み優先度の方がPSWのプロセッサ優先度より小さい時だけ割り込みは処理される.
トラップには優先度がない.
トラップは発生すると即座に処理される.

割り込み・トラップベクタ

カーネルプロセスが割り込み・トラップ処理を開始する際に設定されるPSW, pcの値が格納されているアドレス.
(このアドレスはユーザープロセスの仮想メモリアドレス？カーネルプロセスの仮想メモリアドレス？)
ベクタの値はPDP11によって決められているっぽい.
ベクタデータはカーネルプログラムの下位アドレス部に書かれている.

割り込み・トラップの発生

割り込み・トラップの発生
→PSW, pcをカーネルスタックに退避, ベクタが指すアドレスからPSW, pcを読み込む(ハードウェア処理).
→読み込んだpcから処理を再開(call, trap関数が実行される).

カーネルプログラムの下位アドレス部分を読むと, 0番地にジャンプ命令があって飛んだ先でstart関数を呼び出している.
その部分を除くとだいたいは割り込み・トラップベクタのデータになっている.

ベクタデータの中身は, トラップの場合は, trap関数のアドレスとPSWが格納されている.
割り込みの場合は, それぞれ関数が用意されていてそのアドレスとPSWが格納されている.
その関数の中でcall関数が呼び出される.
ここで使われているjsrが少しわかりづらい.
REF: PDP-11のjsrの動き：いや、まさにログ的な：So-netブログ

ややこしいのが, trap命令とtrap関数がどちらも同じtrapという名前なところ.
一応, このアセンブリではsys命令が擬似trap命令になっているらしく, trapと書いてあったらtrap関数だと思って良さそう(？).

これまたややこしいが, br4〜br7はPSWの値.
トラップの場合はPSWの下位3ビットにトラップの種類を表す値が格納される(br7+4など).
(下位3ビットと書いてあるのに, +9とかしている箇所があって謎.)

次回の内容

call, trap関数の中身を詳細に読む予定.
割り込みが発生した場合, トラップが発生した場合の処理を丁寧追う必要がありそう.
特に, 割り込みの方はjsr命令によってr0とpcの値がいろいろと変わるので気をつける必要がありそう.

会津大学競技プログラミング合宿2017に参加してきました

いろんな人の参加記を見ていたら自分も書きたくなったので書きます.
9/18〜20で会津大学の競技プログラミング合宿に行ってきました.

3日間の日程があってそれぞれ立命館大学, 会津大学, 北海道大学が作問した問題をICPC同様のチーム戦で解くという感じでした.
ちなみに, チームはほぼその場で強さが偏りすぎない程度に適当に決めてました.
実は初めてのオンサイトコンテストだったのでACすると風船が上がる感じとかとても楽しかったです.
コンテスト自体はAOJ上で行われていて, オンラインで参加している方もたくさんいました.

Day 1

東京駅を9:00に出発, 12:00頃に会津若松駅に到着.
郡山まで東北新幹線使うとかなり近いですね.
そして駅からしばらく歩いて会津大学に到着.

1日目は立命館大学が作問した問題セットでした. ACPC2017Day1 (解説)

チームは会津大学の方二人と組ませていただきました.
自分はB問題を解いたのですが, バグらせまくって本当に申し訳ないという感じです...
B問題を通した時にはすでにA, C, Dが解かれていました.
残ったE, F, Gは結局解けませんでした, 残念.

合宿終わった後に全部問題ちゃんと見た感想です.

• A: 丸付け (解答)
  • 2文字ずつ見ていけばO(N)で判定可能.
• B: 全日本帰りたい協会 (解答)
  • 次の人を迎えに行くまでに1Fに戻っても間に合うならば, 1Fに行くのが常に最適.
  • ...なのですが, 結構チェックしないといけない箇所が多かったりして実装がしんどいです.
  • ちなみに, 僕は最初の人を迎えに行けるかどうかの判定を忘れて2WA出しました.
• C: ツイート数 (解答)
  • DFSしながら葉からの最短距離を求めていけばOK.
• D: 次元旅行 (解答)
  • i次元からi - 1次元にだけ辺を張ってダイクストラすればいいというのが面白かったです.
  • 普通に全部に辺を張ったらMLEしたので解説見ました.
• E: 敵襲から守れ
  • まだACできてないです.
  • あんまり最大フローがよく理解できてないのですが, この期に理解してしまいたいので頑張って通したいと思います.
• F: Steps
  • ランダムウォークではよくあるタイプの問題らしいのですが, あんまりちゃんと理解できてないです.
• G: Cryptex
  • めちゃくちゃ頑張ると解けるらしいです(遠い目).

Day 2

二日目は会津大学が作問した問題セットでした. ACPC2017Day2
僕 + 立命館の方 + 社会人の方の3人チームでした.
自分はA, C, F, Lを解きました.
A問題は人生初のFA(オンサイトのみ)で結構嬉しかったです.
FAなので風船にかわいい動物がついてきました.
圧倒的にチームのみなさんが強くてオンサイト1位でした.

以下各問題の感想です(解けたもののみ).

• A: Clock (解答)
  • 割って余り求めたらいけるやろ〜とか言って提出したら通りました.
  • 人生初オンサイトFAやったね！
• B: Hating Crowd (解答)
  • ちょっと面倒ですが愚直にやると解けました.
• C: Palindrome (解答)
  • N^2が間に合う制約なので, 回文にするときのペアを探してから辞書順に貪欲にとっていけばOKです.
  • ちょっと実装がややこしくてバグらせましたが...
• D: Fissure Puzzle Easy (解答)
  • 白いマスの連結成分の数を数えて1引いて3で割ると答えが出るというちょっと面白い問題でした.
  • 領域を4分割していくのでも解けるみたいです.
• E: Piano (解答)
  • 連続して増加, 減少している部分の最大を求めれば解けます.
• F: nCm (解答)
  • 問題を見たらすでに考察がされていたので, その通りに実装したら通りました().
  • 結局2^kのところだけ見ればO(logN)で解けるようです.
• I: Making Pairs (解答)
  • 木の上でマッチングをする問題.
  • DFSしながら, マッチしていないものと貪欲にマッチさせていけばOK.
• L: RMQ 2 (解答)
  • クエリはQ個しかないので, 全部コピーする時は以前に変更があった箇所だけコピーすれば間に合います.
  • コンテスト時間中に通せてよかった...

コンテスト後はリクルートコミュニケーションズのアドテク部さんのおかげで無料で懇親会に参加することができました.
(その謎のお金は一体どこから出てきてるんでしょうねぇ......)

Day 3

三日目は北海道大学が作問した問題セットでした. ACPC2017Day3
僕 + 会津大学の方 + 立命館大学の方みたいなチームで臨みました.
B問題が鬼難しくて, Bとは何かについて哲学的な考察をしていました.

以下問題の感想です.

• A: A-Z- (解答)
  • 一文字前の出てきた文字を覚えておき, それ以下の文字が出てきたら答えを1増やすみたいなことをしました.
• B: えびちゃんと数列 - Ebi-chan and Integer Sequences - (解答)
  • 等差数列の和を求めると答えが出るのですが, N = 1がコーナーケースになっていたり, modを取るのが足りないとWAしたりと大変でした.
• C: たったひとつの部分列 - Unique Subsequence - (解答)
  • 部分列を前からマッチングさせた結果と後ろからマッチングさせた結果が一致していればユニークで, そうでなければユニークでないと判定できます.
• D: 優柔不断 - Indecision - (解答)
  • AOJを信じて10^8のDPを投げると通ります.
• E: たい焼きマスターと食べ盛り - Taiyaki-Master and Eater (解説)
  • 二次元BITを使う問題です.
  • 初めて二次元BITを実装しました(Githubで栽培してます).

まとめ

初めてのオンサイトコンテストでしたがとっても楽しかったです.
また, 作問している方々を見て素直にすごいなという感想を持ちました.
うちの大学でも強い競プロerの人々がコンテスト開きたいと言っているので, その時は作問側もやってみたいなと思いました.

最後になりましたが, コンテスト運営してくださった方々, 作問をしてくださった方々, 当日チームを組んで下さった方々, 本当にありがとうございました.

(ちなみに, 実は会津合宿の帰りにもう一泊して「全部ACするまで帰れま10」という企画もやったのですが, その時のことはまた別記事で書きたいと思います.)