セキュリティ・ミニキャンプ in 北海道 2016 参加記

セキュリティ・ミニキャンプ in 北海道に参加しました。セキュリティ関係の勉強会は初めて行ったのでついていけるか不安でしたが、グループ議論や演習が充実していて私でも楽しめました。今後セキュリティ・ミニキャンプへの参加を考えている方の参考になればと思い記事を書くことにしました。とはいいつつもめっちゃ真面目に書くつもりはないのでフランクに書いてます。

0日目

このイベントの存在を知ったのは大学の講義中に教授が紹介してくれたのがきっかけ。セキュリティのセの字も知らない状態の私、せっかく近くでこういうのがあるなら行ってみようかなーということで、参加することにした。

その後セキュリティの講義で共通鍵とか公開鍵とか基礎的なことはやるものの、依然としてついていけるかどうか不安のまま・・・。(今思えば心配することなかった)

1日目

実はミニキャンプ当日の6時までラウワンオールしてて、そのあと5時間くらい寝て行きました()
人間がんばれば何とかなるものです。まあ、そんなことはさておき・・・

最初はセキュリティ・キャンプ全国大会の紹介。聞けば聞くほど魅力的な大会だなあと思った。もうちょっと知識つけて出たいなあ、予選は知識なくても通るチャンスはあるといえども、ちゃんと勉強したほうがより大会楽しめそう。セキュリティの資格取りに行くつもりで頑張ったら達成できるかなあ、とかいろいろ考えてた。

次は地域IoTの話。予算がない中でやりくりしなきゃいけないから大変らしい。安全な実装とか、メンテナンスとかどうすればいいかについてグループ議論したけど、取り上げている話題がそれなりに解決困難なのでいい答えは出ず。もっと頭良くなりたいと思った。

その次は演習。HTTP Request / Responseをいろいろいじくって、ムリゲー仕様の携帯ゲームを、脆弱性を突いてクリアしてしまおうというもの。いろいろ見てたら、敵からの攻撃を表すRequestを破棄すればダメージを受けないことが判明してクリア、自分がいたグループが一番早くできたので嬉しかった。でもこれは想定解ではなかったようで、講師側も悔しがっていた。というか想定解思いつかなかった・・・。やっぱり演習形式は、このアプリケーションの何がダメなのかとかが具体的にわかるから好き。

ここで夕食休憩。私からしたらいつもの学食だけど、やっぱり他の大学や高専の人にとっては新鮮なようで、学校の立地について話が弾んでいた 笑

最後は情報学に関する法律の話。自動運転に関する問題が出されて、それぞれの意見を言っていくんだけど、けっこう意見割れてた。どっちの意見もなるほどという感じで、考えされられた。

札幌市民だけど「ホテルが用意されているので泊まっていって！」、ということで、ありがたく宿を利用することに。その後DDPCに出るも2完で無事死亡。上に有資格者何人いるかしらんけどたぶん通らんだろうな・・・。(追記: 通った。ビックリ。本戦終わったらまた記事書きます)

2日目

ホテルで朝食を食べて会場へ。雪めっちゃ降っててつらかった。

朝はクラウドの講義。AWSちょっといじったことはあるけど詳しいことは何もわからないので新しい知識をたくさん得た。個人レベルでどうつかうかとかしか考えたことがなかったので、いちサービスとして提供する側に立った時に何を気をつけなければならないかについてはもう少し日頃から考えていかないとなあと思った。あとでメモ見返したい。

その後はRaspberry piを使った演習。高専生が強いのでサクサク進んだ(ありがとうございます)
あの小さい中にOSが入ってるなんてすごい。前に実験でArduinoを触ったことはあるけど、あれはOS入ってないのでなおさらびっくりした(まあ、ArduinoはOSが載ってない分ハードウェアをフルに使えるのがいいところなんだけどね)
頑張ったらいろいろできそうだし、もうちょい調べてみようかなあ・・・。

これで日程は無事終了。早かったなぁ。

まとめと雑感と

初めて参加したけどすごく楽しめました。来年も参加したいなあという気持ちになってる。

Markdown周りを整えていたおかげでメモがとてもとりやすかった。勉強会でるなら環境つくっておいたほうがいいかも。

あと、高専生つよい。大学よりもはるかにレベルが高そう(主観)なので、あぐらかいてられんなあと思った。

色々と刺激もらったので、これからに活かしていきたいなと思います！！内容のない記事でしたけど最後まで読んでくれてありがとうございました。

Sublime text + Pandoc で Markdown を PDF, Word 形式等に出力 (Linux)

競技プログラミング関係ないです。MarkdownをじゃんじゃんPDF化してSublimeを使い倒しましょう。Linux向けの記事があまり無いように感じたので書いてみました。

※筆者の環境はUbuntu MATE 14.04 LTSです。環境によって設定が微妙に異なる場合があります。

MarkdownをHighlight + プレビュー(数式もOK!)

Sublimeを愛用している私は、ふと「SublimeでMarkdownを快適に編集できたらうれしいなあ・・・」と思いました。

調べたら、ありました。 ↓

Sublime Text で Markdown を快適にする3つのパッケージ - 情報系大学院生のWebメモ

この記事を参考にすると、Markdownが色付けされてなおかつブラウザでリアルタイムプレビューもできちゃいます。素晴らしいですね。

でも物足りない私は、「数式も反映されないかなあ・・・」と思いました。

調べたら、できました。↓

$\LaTeX$ Support in OmniMarkupPreviewer | Timon Wong's Blog

OmniMarkupHighlighterのUser-Settings部に、

{
    "mathjax_enabled": true
}

を書くだけ。おいおい、神かよ。これでMarkdown編集し放題じゃない。これは素晴らしい。ということで、一時は満足しました。

Markdown を 他の形式で出力する

ここからが本題です。まだまだ物足りない私は、「これPDFにできないかなあ・・・」と思いました。調べてもなかなか出てきません。なんとか頑張ったらできたので、書いてみます。

Pandoc のインストール

Pandocをインストールしますが、2種類あります。

まずは、sudo apt-get install pandocでインストールするPandoc。Sublime上だけに限らずコマンドラインでも使えますね、いろいろできますよ。詳しい使い方はググってね。

そして、SublimeのパッケージであるPandocもインストールします。こちらは、Package Controlをインストールした状態(インストールがまだならすればいいじゃない！)のSublime上で"Ctrl + Shift + p" → "Package Control: install package"と入力 → "Pandoc"と入力 → クリック でインストールできます。ほかのパッケージのインストールの方法と全く同じです。

インストールが終わったら、次はSublimeのパッケージ側のPandocの設定変更です。Preferences → Package Settings → Pandoc → Settings - Defaultと進み、中身をSettings - Userにコピペしてください。そして、14行目の"pandoc-path"のところを次のように変更します。

"pandoc-path": "/usr/bin/pandoc"

これでPandocのpathが指定出来ました。環境によってパスは違うかもしれないので、その場合はwhich pandocとかwhereis pandocとか叩いてみてください。

さらに、62行目からの"PDF"の"pandoc-arguments"を次のようにします。この設定をすることで、日本語に対応できます。(lualatexが入っていなければ、インストールしてください)

"pandoc-arguments": [
    "-t", "pdf",
    "--latex-engine=lualatex",
    "-V", "documentclass=ltjarticle"
]

PDF出力でエラーが出たら・・・

さて、ここまできたらSublimeで適当なMarkdownファイルを開き、もう一度"Ctrl + Shift + p"でウインドウを開き、そこに"Pandoc"と入力してみましょう。Enterを押すと、出力するファイル形式を尋ねられます。PDFとかWordとか選べて便利ですね。

で、Wordとかは問題なくできるはずです。が、PDFがダメなときがあります。こんな感じでエラー出たら、次の対処をしてください。

Error when running:
/usr/bin/pandoc -f markdown -o /tmp/tmpqof5of.pdf
pandoc:Error producing PDF from TeX source.
! Font T1/cmr/m/n/10=ecrm1000 at 10.0pt not loadable:
Metric (TFM) file not found.
<to be read again> relax
l.100 \fontencoding\encodingdefault\selectfont

細かいことはさておき、どうやらフォントが無いようですね。ということで、以下のコマンドを実行します。

sudo apt-get install texlive-fonts-recommended

フォントインストールするとこのエラーは出なくなります。

環境によってはまだエラーが出ます。

! Package fontenc Error: Encoding file `eu2enc.def' not found.

こんなことを言われたら、sudo apt-get install xetexを叩きましょう。euencはxetexパッケージに含まれているらしいです。これらの設定を踏めば、PDFエクスポートできるはずです！！

簡単にメモったりしたものがTeXの形でPDFで出力できるとは胸熱ですね。有効活用していきたいです。

何か不明な点があればコメントお願いします。では。

AtCoder Regular Contest 009 C: 高橋君、24歳

問題概要

原文 → C: 高橋君、24歳 - AtCoder Regular Contest 009 | AtCoder

長さの順列を並び替えたとき、 (1-indexed)となる要素が個になる組み合わせは何通りか。1,777,777,777 (素数) で割った余りを出力せよ。

解説

まず、となる要素をどこにするかを決めます。これは個の中から個を選ぶ組み合わせであるため、と同値です。1,777,777,777を法として計算するため、この計算をするためには逆元の知識が必要ですが、それは他のサイトに委ねます。階乗の計算すると思うけど再帰で書いたらダメですよ、もれなくスタックオーバーフローします。

問題なのは、となるような長さkの順列が何通り作れるかを求めることです。漸化式を求めれば解けそうな雰囲気はしますが、どんな漸化式になるでしょうか。

最初に、長さの場合を考えましょう。

長さ1で元と異なる位置に置く組み合わせは当然存在しないので、0通りです。

長さ2では、[1, 2]に対して[2, 1]と変えることで条件を満たせます。これ以外には存在しないため、1通りです。

それでは、長さではどうなるでしょうか。これは番目の要素でを選択したとき、番目の要素でを選択するかどうかで場合分けをすれば求まります。文章で言ってもわかりづらいので、図で(パソコンで書くのめんどくさいので手書き)示します。なお、長さの順列でこれを満たす組み合わせの総数をと置いています。

ちなみにこのような順列は「完全順列」と呼ばれ、完全順列の総数をモンモール数と呼びます。フランスの数学者、ピエール・モンモールにちなんで名づけられた、らしい。

ソースコード

int const MOD = 1777777777;

ll fact_mod(ll n, ll mod) {
    ll f = 1; repq(i,2,n) f = f * (i % MOD) % MOD;
    return f;
}

// 繰り返し二乗法 (再帰バージョン)
ll mod_pow(ll x, ll n, ll mod) {
    if(n == 0) return 1;
    ll res = mod_pow((x * x) % mod, n / 2 , mod);
    if(n & 1) res = (res * x) % mod;
    return res;
}

// 組み合わせ nCr を求める (modあり)
ll combination_mod(ll n, ll r, ll mod) {
    if(r > n-r) r = n-r;
    if(r == 0) return 1;
    ll a = 1;
    rep(i, 0, r) a = a * ((n-i) % mod) % mod;
    ll b = mod_pow(fact_mod(r, mod), mod-2, mod);
    return (a % mod) * (b % mod) % mod;
}

signed main() {
    int n, k; cin >> n >> k;
    int ans = combination_mod(n, k, MOD);
    int dp[555555]; dp[1] = 0, dp[2] = 1;
    repq(i,3,k) dp[i] = (i-1) * (dp[i-1] + dp[i-2] % MOD) % MOD;
    ans = (ans * dp[k]) % MOD;
    cout << ans << endl;
    return 0;
}

数学に強くなりたいね・・・