セキュリティキャンプ2019: Cコンパイラ開発記

(本文は随時追記します) (もし書いてることが間違っているのに気づいたらこっそり教えてください)

6/6

セキュキャン通過!

md19970824.hatenablog.com

6/7~6/9

院試勉強をやる

6/10

院試勉強がとりあえず一周した(させた)のでCコンパイラ作成に手をつけ始めました. 今日はもう遅いのでgithubリポジトリを作って一番初めのところをやって終わりにします.

とりあえずリポジトリをつくりました.

github.com

基本的にはRui Ueyamaさんが書いたこのサイトに従って進めていくことになります.
最初は算術式をコンパイルできるようなプログラムを書いてみました.とても簡単です. 微塵も進んでいませんが,今日はもう眠いのでおしまい.水曜日辺りにガッと進めたい.

~6/15

今週は結局院試対策とバイトしかしなかった... 事前課題フェイズ始まったらちゃんとやりますm( )m

セキュリティ・キャンプ2019に通過しました

セキュキャン2019通過してました。
今年で年齢制限なので応募したのですが、倍率高いらしいし受かるわけがないと思っていたのでめちゃくちゃ驚いてます。 というか今も半信半疑です。何度も自分のIDと通過者のID一覧を見比べていますが、今の所同じ数字が書いてあるので多分受かってるんだと思います。 コースはシステムプログラミングトラックのCコンパイラ自作コースです。 事前課題と院試勉強を並行して進めることになるのでかなり忙しくなると思いますが、なんとか両立出来るように頑張ります。(研究は?)(競プロは?)
応募用紙に書いたことを軽くまとめます。(そのまま貼るのは恥ずかしいので、、、)

問1 これまでのプログラミング歴(C言語に限りません)について好きなだけ語ってください。何か作ったものがあれば、それについても教えてください。

githubのリンクを貼って、実験とバイトと競プロのことを書きました。
railsを使ったwebページ作成(バイト)
・miniMLインタプリタ(実験3SW)
・miniMLコンパイラ(実験4の前半がすぐ終わったのでアセンブリ吐くとこまでやってみた)
brainfuckインタプリタ(実験3の追加課題として書いてみた)
・3層NNの実装(実験4前半)
・自作CPU(実験3HW)
・競プロ
・自作OS(応募に向けてやってみたけど間に合いませんでしたと正直に言った)

実験4後半書かれてなくてウケる

問2 コンパイラソースコードから実行バイナリを生成する過程について、現在知っている範囲で説明してください。ソースコードの言語については、好きなものでかまいません。

前処理→字句解析→構文解析中間言語生成→アセンブル(オブジェクトファイル生成)→リンク
の流れで、途中で各種最適化と型検査が挟まる

↑を述べて、各内容について詳しく説明しました。大体授業資料を参考に書いて、リンクのところはパタヘネを参考に書いた。数えたら3000字ちょいでした。

問3 C言語コンパイラを書く際に、最も難しいポイントはどこだと思いますか?考えたことや、これまでのプログラミング経験を元に、具体的に教えてください。

アセンブリ生成を挙げました。レジスタ割当てむずかしくないですか。 あと、字句解析・構文解析を自分でやるならそっちのほうが難しいと思いますと書きました。

問4 何か他にアピールしたいことがあれば、自由に書いてください。この設問も含め、誤ったことを書いていても減点はしません。書いておきたいことは何でも書いてください。

一応情報学科に在籍しているので、「基本的なCSの知識はあります!」と豪語しました。 あとすいばかと一緒にTAPLを読んだので、操作的意味論さわったことありますって書きました。 最後にヤケクソで、ほんとにやれるかわかんないけどいつか自作OSに自作コンパイラ載せてみたいなあという願望を書きました。やるぞ。

応募用紙に書いたことは以上です。
正直ほとんどは計算機の人たちなら書ける内容な気がします。
後輩のみんなは年齢制限引っかかってなければ、そして少しでも興味があれば来年絶対応募したほうがいいです。しろ!!!

どんな5日間になるか、今から楽しみです。
コンパイラ書き始める前に院試勉強を一段落させなきゃ、、、

精進禄

競プロメモ

AGC019-B
B - Reverse and Compare
端が違う文字なら他の位置を反転した文字列とかぶることはない。
アルファベットごとに出現個数を持っておいて、左から探索。O(n)

AGC020-B
B - Ice Rink Game
にぶたんしてO(klogk)くらいかなーと思ってたらなんか線形で解けた。

APC001-C
C - Vacant Seat
どこかでMFMFMF...の規則が入れ替わらないとおかしいので、にぶたんできる
まず0を出力した時の答えが
男のとき:a[男]=0, a[女]=1
女のとき:a[女]=0, a[男]=1
と符号化する。
l = 1, r = nを初期値として区間[l, r)をもつ。
mid=(l+r)/1を出力したときに受け取った結果をresとおくと、
P(mid) = (a[res] == mid % 2)として
if(P(mid)) {
l = mid;
} else {
r = mid;
}
区間を狭めて行くことで答えにたどり着く。

Codeforces #523 div2 C

問題

数列a1, a2, ..., anが与えられて、そこからいくつかの要素を、順序を変えずに取り出した数列b1, b2, ..., bkについて考える。k>1かつ、1 <= i <= kなる任意のbiがiで割り切れるようなものの個数を10e9+7で割った値を求めよ。
1 <= n <= 100,000
1 <= ai <= 1,000,000

Problem - C - Codeforces

解く

ぱっと思いつくのが
dp[n+1][n+1]
dp[i][0] = 1;
dp[i][j] = dp[i-1][j] (if ai % j != 0)
dp[i][j] = dp[i-1][j] + dp[i-1][j-1] (if ai % j == 0)
みたいなdpで、最後にdp[n]を1番目からn番目まで足せばいいんですが、愚直に実装するともちろん時間が足りません。

そこでvector <map<int, int>> dp(n+1)を作って約数として出てくる部分だけ考えようとする。iごとにaiの約数を調べ、大きい方から順に更新していく。が、MLE。

ここでようやくDPを1次元に落とせることに気づき、map<int, int> dpでやろうとするが、今度は更新の順番を間違えていることに気づく。(降順に更新するのはわかっていたけど、約数のペアを同じタイミングで更新していた。ちゃんとvectorに放り込んでソートしましょう)

やっと通ると思って投げると、今度はTLE。
よく考えたら脳死でmapを使うとaiの約数のうちnより大きなものまで更新してしまっている。O(105 * √106)でギリ間に合わないんだろうかとか思いながら、ちゃんとvector dp(n+1)になおしてAC

めっちゃ時間かかってしまった。

CODE THANKS FESTIVAL 2018 参加記

一回生からちょくちょく手を出してた競プロをこの夏から真面目にやったら、THANKSに参加できてしまった人の参加記です。
(6月時点のレートが609で、現在レート1340)

予選

ここ数年の参加記を眺めていると、年々枠が減ってるみたいですね。
予選の回数も減っていてかなしい、、、

qualA

解けまへん。
やはり地力不足で、2完でした。333位。

qualB

前日のAGCで晴れて水色になりました。

f:id:mdyh2a380824:20181120042056p:plain
その時の記録
モチベも上がり、気合十分な状態でのqualBですが、、、

Dを解いたのが9人(!?)で、予選が3完早解きコンテストと化す。
しかし、まだまだ未熟な僕にとってはこれが幸いしました。普通のコンテストだったらたぶんTHANKS参加できてなかったです。
40分ちょいで3完、190位。

通過確定、ほぼ確定の人をみて、いいなーと思いつつ賞賛をおくる。
この時点ではまだ予選落ちたと思ってました。(もともと来年に向けて経験しとくくらいの気持ちで参加していた。)

通過

上位で通った人の通過報告から数週間遅れてメールが届きました。
僕の10~20番くらい下だったれなすが落ちてたので、ほんとにボーダーギリギリの通過でした。(彼は遅刻してなければ、、、!と悔やんでいた。)
qualBの通過人数は本選40名、THANKS40名なので100人ちょい繰り上がってます。すごい。

前日

朝の新幹線に乗って東京へ向かう。
KMC勢と合流して晩飯を食べる予定だったが、3時頃にホテルについてベッドに横になった結果なんとそのまま6時間寝てしまった(各位ごめんなさい)
ちょっとだけ問題を解いて寝る。

当日

寝坊せずちゃんと起きる。
10時40分ごろに会場に着いた。いろいろ手続きをして席につく。
会場の後ろの方にはお菓子や飲み物がたくさんあった。
コンテストが始まる12:00まで知り合いと喋ったり配られた弁当を食べたりしながら時間をつぶす。

コンテスト

コンテスト開始!
※ネタバレ注意

まずA問題を解く。(1:39)
ほんとにやるだけと言った感じの問題。chokudaiさん曰くDPでも解けるらしい。

B問題は、10^9やけど間に合うやろ!って感じで投げるとACした(6:31)
655msなのでまあ余裕だった。

C問題。死亡。
ソートして差を取るとこまではすぐ思いついたけど、それぞれの区間が出て来る回数の処理をバグらせる。結局30:00にAC

D問題
しょーもない誤読をしてWAを生やす。すぐ気づいてAC(37:50)

悲しいかな、この時点で解ける問題がなくなる。この後何もわからず、2時間半地蔵になってしまった。(一応Fを解こうとはしていた)

終了後

結果は4完87位。うーん。
やはりオンサイトに進める人はレベルが高いなあと感じた。次はパーカー獲得を目標にします。
懇親会ではビンゴとコミュ力の融合ゲームがあり、人数の多い京都大学が圧勝していた。(zakiとamanoさんおめでとうございます)
僕もなんだかんだビンゴしてレポートパッドをもらいました。計算用紙おいしい!

懇親会終了後は京大の人たちとお寿司を食べに行きました。amanoさんが認知してくれていたのが驚きだった。

感想

結果はあまり良くなかったけど、やり始めて実質4ヶ月くらいなので出れただけでもよしとします。
今週末はHTTF本選なのでそっちは1ページ目にはいるぞ!