2019-10-20

SC受験記(2019秋)

資格

令和初の情報処理技術者試験(情報処理安全確保支援士; SC)を受けてきました。せっかくなので受験記を書きます。

結果

午前2は既に公式解答が公表されているので自己採点しました。 https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2019h31_2/2019r01a_sc_am2_ans.pdf 午後は合格寄りだとは思いますが正直分からないです。

午前1: PASSED(免除)
午前2: PASSED(21/25)
午後1: 不明(70点くらい？)
- 選択した問題: 問2, 問3
午後2: 不明(65点くらい？)
- 選択した問題: 問1

（上振れてくれ〜〜〜）

試験勉強について

勉強自体は8月から開始しました。細く長く勉強した感じです。勉強前のステータスについては、IaaSでサービス設計する業務をした経験があるくらいですね。正直ネットワークとセキュリティはかなり苦手意識がありました（今もそう）。また、2018年春にデータベーススペシャリスト(DB)を取得していたので、午前1免除組です。

基礎知識の勉強（8月上旬〜8月中旬）

セキュリティ技術の教科書をざっと読みました。後で読み返すつもりでしたが、読み返すことはありませんでした。一日20ページくらい読むペースで進めていました。漫然と読んでいただけでしたが、一日ごとにScrapboxとかにメモを残したほうが効率がよかったと思います。

午後対策（8月中旬〜試験前）

教科書を読了した後はひたすら過去問・模擬試験を解きました。午前2は直前に対策してもどうにかなるので、午後問題から解きました。しかしながら、仕事や競プロをやりながらだったので、何もやらない日も決して少なくなかったです。

過去問解く上で使ったのは以下です。

それぞれ午後1の問題だけ1, 2周しました。昔の過去問を無理に解くよりは、最近の過去問を2回解く方がいいと思います。これは1回目で解けなかった問題に関する知識を定着させるためです。また、午後2の問題についてはほとんどやっていません。午後1ができればどうにかなる説を信じていたのと、一回の勉強で2時間近く時間を割くのはやってられなかったからです。本番の試験時間はゆとりがあるので、時間配分の練習も不要だと思います。

SCは午後問題の選び方がDBより難しいですが、問題を解くなかで解きやすいジャンルが見えてくると思います（ジャンル分けは 2019 情報処理安全確保支援士「専門知識+午後問題」の重点対策が参考になります）。ちなみに私の場合は以下が解きやすいと感じました。

セキュアプログラミング
ログ
インシデント対応

逆に苦手意識があるのは以下でした。

認証
PKI
電子メール

解きやすいジャンルが見えてきたら、それらのジャンルを伸ばした方がいいと思います。午後は選択式なので苦手な問題からは逃げればよいのです（あまり山を張るのは考えものですが...正規分布的に努力値を振るイメージで）。

午前2対策（9月下旬〜）

情報処理安全確保支援士過去問道場をひたすらやります。それだけです。模擬試験は一周20分もあればできるので、「隙間時間に解く」や「寝る前にベッドで解く」でいいと思います。最後のあがきとして、試験当日の朝もやりましょう。私は朝に4周しました。そして、本番の点数を2点は加算できたと思います。

試験当日について

午前2

10:30までに集合となっていますが、呑気に洗濯してたら10:40くらいに会場に到着しました。当然ですがとくにペナルティはなかったです。この時間に到着した人も結構多く、会場の建物のエレベーターに行列ができていました。

試験自体は問1で面食らってしまいましたが、問2以降は道場のおかげで精神的に楽な状態で解けました。 10分で1周して、もう10分で見直し・自己採点。自信をもって回答できた問題が15問あったので勝利を確信できました。残り20分は空腹に耐えながら前日のAtCoder Beginner Contestの問題を振り返っていました（おい）。

昼飯

すき家の高菜明太マヨ牛丼にハマっているので、試験会場から徒歩1分のすき家へ。試験終了後直ちに移動したので混雑に巻き込まれることなく高菜明太マヨ牛丼を食すことに成功しました。同時にSCを受験した友人とLINEでワイワイしながら腹を満たしました。

午後1

ここからが本番です。回答用紙を見て、「問2が記述回答多くてダルそうだな〜いや実はとっつきやすい問題だったりするのか？」とか考えていました。試験開始後、問題を開くと問1（電子メールの問題）は知らない単語ばっかりで早くも捨て確定。問2, 問3を眺めるとどちらもコードが見当たらず（セキュアプログラミングの問題がないことに）焦りますが、どちらもインシデント対応に関する問題なので問2, 3で確定です。解いている中でちょこちょこ不安な要素はありましたが、「何が何だか分からない」は避けられたので落ち着いて解くことができたと思います。時間も20分くらいは余ったので、ていねいに見直しできました。

午後2

思ったより午後1ができたので、午後2も諦めずにしっかりやります。回答用紙が配られた時点で、問2はネットワークの要素が強めな問題であることが分かるので問1濃厚かなーと考えていました。問題を開くと、問1は実家のような安心感がある問題で問2はネットワーク構成が複雑がダルそうだったので、問1確定。午後2は問題選定に10分程度はかけていいと言われていますが、今回は1分で選定できました。

問題文は長いですが、ストーリーが分かりやすく、また業務でも似たような展開があったのでイメージしやすかったです。巨大で複雑な問題を解く、というよりは複数の問題を単にシーケンシャルに解く感じでした（設問4なんてただの知識問題だし）。記述問題の文字数が多く十分な記述ができたかは不安ですが、部分点はそれなりに得られているのではないかと信じています。見直し込で時間は30分余り、やることがなくなったので30分前に途中退室しました。

おわりに

正直、試験勉強しているときは楽しいという感情がほとんど沸かずつらかったですが、試験本番は解き応えがあって面白かったです。ただ仮にこれで合格したとしても、情報処理安全確保を支援できる人材になれた気はまったくしないですｗしばらく資格取得はいいや、という気持ちですが、またモチベが湧いたら今度は統計検定あたりに挑戦したいと思っています。

2019-09-22

技術書典7に一般参加

技術書典7 に一般参加しました。技術書典には初参加です。

戦利品

f:id:wotsushi:20190922192142j:plain

コンペに関する本が多いですね。これを機にKaggle, CTFにも手を伸ばせればと思っています。総額1万円くらい？

立ち回り

時間は割とテキトーです。

13:00: 会場入口で友人と合流
- 少し遅刻してしまいました（友人、申し訳ない）
- 12:30には池袋駅を出るくらいの気持ちがよさそうです。
13:10: 入場
- 待機列は予想よりずっと短かったです
- なお、14時くらいには予想していた長さの列が形成されていました。
14:00: 2Fの周回完了。3Fへ
14:15: 3Fの立ち読みコーナーで面白そうな本を立ち読み
- 先に立ち読みしたかったでですね。
- 気になる本をメモるのが地味に面倒。
14:45 3Fの周回完了。再度2Fへ
15:00 退場

メモ

トートバッグは入り口でもらえます
- ただし、トートバッグの数は有限（もらえない可能性はある）なので、一応カバンは持っていくべきでしょう
14:00-15:00に並ぶとつらそう
1000円札はたくさん持っていきましょう
- なんだかんだ現金安定
- 後払いアプリは一回も使いませんでした
カンファレンスでもらえるTシャツを着ていくと、その分野に関する売り子さんと円滑に会話できるらしいです（要検証）

2019-09-17

PyConJP 2019 参加記

Python

はじめに

PyCon JP 2019 に一般参加しました。 PyCon JP にはこれが初参加です。

Day 1

開始前

会場に近いため、余裕の8時起床。雨でテンションが下がりつつも出撃準備。会場で飲み物が出るか分からなかったので、念のためコンビニで緑茶のペットボトルを購入したが、別に必要なかったです。道中滑らないように気を付けながら9:30過ぎに到着。会場にはサンドイッチとフルーツが用意されていました。PyConに来てよかったと感じました。

PyConJP情報です #pyconjp pic.twitter.com/7j5NDZodsE
— wotsushi (@wotsushi) September 16, 2019

サンドイッチとフルーツをいただいた後、ブースを周回。ステッカーをもらうなどしました。

keynote

独学プログラマーの著者の方の発表。チンタラしてたら席が埋まってたので立ち聞きしました。 CS非専攻だったがPythonを使い始めてからメキメキ強くなった話でした。 Pythonistaの平均年収は1,300万円という話も。私はPythonistaではないのだろう。ちなみに、レシーバーを借りると同時日本語通訳も聞けたようです。視力と聴力（英語リスニング力）に乏しいので、借りればもう少しちゃんと話を聞けたと思います。残念。

Python開発を円滑に進めるためのツール設定

スライド: https://www.slideshare.net/aodag/python-172432039

つまらないミスをなくそう、というコンセプトで、lint, formatter, testツールをまとめられた発表です。具体的には、flake8, black, mypy, pytest, tox について紹介されています。 2019年におけるモダンなPython開発ツールについて知る・復習できるよいセッションでした。

昼食

4種類くらいの弁当から一個＋お茶が支給されました。基本的に机で食べる選択肢はなさそうだったので、ホールの椅子に座って昼食。昼食後は外で休憩（ゲーム）したり、ブースを周回するなどして、ギリギリまで昼休みしてました（悪手）。

Yet Another Isolation Debian packageと紐づく環境分離

スライド: https://speakerdeck.com/puhitaku/yet-another-isolation-debian-packagetoniu-dukuhuan-jing-fen-li

「Djangoで実践ドメイン駆動設計による実装」の方を聞く予定だったのですが、悠長に昼休みを過ごした結果、満席になってしまいました。仕事でもプライベートでもDebian環境とはあまり縁はないのですが、環境分離の話は興味あったので、このセッションに参加。会場で展示されていたLOVOTというロボット上でのPython環境分離について、その苦労話を聞くことができました。正直あまりピンとは来なかったですが、環境管理系のツールについてこれまでの歴史や最近のツールについて知ることができたのでなかなか有益だったと思います（どうせPipenvが最強でしょ、と思っていたがそんなことをないみたいです。例えば、 Poetry）

PyRun - Shipping the Python 3.7 runtime in just 4.8MB

スピーカはPython 1系の時代からPythonに関わっていたガチ勢。僅か4.8MBのPythonランタイムを作ったのは驚きましたが、種は理解できませんでした。容量制約の厳しい環境（マイコンとか？）やコンテナでPythonを動かすときに有用そうですね（小並感）。 https://ep2019.europython.eu/talks/wGmo3yT-pyrun-shipping-the-python-37-runtime-in-just-48mb/

Coffee Break

お菓子列に並ぶ人々が蛇のように並んでいて、PyConに参加していることを実感しました。お菓子はどら焼きをいただきました。 Coffee Breakは1時間くらいありましたが、昼休みの反省を活かし、早めに次のセッションの部屋に移動しました。

Pythonを使ったAPIサーバー開発を始める際に整備したCIとテスト機構

スライド: https://speakerdeck.com/hgsgtk/python-api-ci-test

CI導入から活用例までカバーした発表です。モックを用いたテストなど、テスト方法についても知ることができます。 Pythonに限らず、CIに興味のある方は一度見てみるといいのではないかと思います。具体的で分かりやすい内容でしたが、15分という発表枠はちょっと狭かったですね。

pandasのStyling機能で強化するJupyter実験レポート

スライド: https://speakerdeck.com/komofr/pyconjp-2019

Excelの条件付き書式をPandasでやる方法について紹介した発表です。 CSSを関数の引数として渡すと聞いてダルそうだなと思いましたが、コードを見てみると直観的で良さげでした。セルにバーを表示する機能もあって、Pandas最強だなと思いました。最後に to_excel という上司向けのメソッドもあるのには驚かされました。

LT

PyQt5でオレオレブラウザを作った話が印象的でした。制限された環境がつらいというのは分かりみが深いのですが、それに対するアクションが激しくて笑いました。この行動力は見習いたい... 結局、その職場から転職したというオチも面白かったです。

Party

カンファレンスでおなじみの立食パーティーです。最初は会場の広さに対して人数が多く、ほとんど身動きがとれませんでした。まわりに知り合いのいない "ぼっち” 状態でしたが、最大公約数の最小値がPythonであることが保証されているので、会話は切り出しやすかったですね。業務でPythonをバリバリ活用している人は少なく、サブウェポンとして活躍しているという声が多かったです。食事については、カレーが近くにあったのでカレーを2杯、お酒はビールとハイボールをいただきました。寿司を食べ損ねたのが残念...

Day 2

開始前

会場と同時（9時）に入場。サンドとフルーツをいただきました。朝食後は早めにkeynote会場に着席しました。

keynote

スライド: https://www.slideshare.net/ikemkt/pyconjp2019python

キュウリ農業×Python な発表です。IoT, AI, ナレッジ伝承などキャッチーな内容が多く含まれますが、決してにわかな内容ではなく、地に足のついた内容です。試行錯誤しながらキュウリ選別機の精度や使い勝手を上げていく過程は引き込まれるものがあります。発表者はMakerコミュニティのメンバで、調味料調合機なども自作している、現代のエジソンでした。また、他の発表でも言及されていましたが、Pythonはそのフレンドリーな文法が人気を得ていることが改めて分かりました。

講演終了後、速やかに次のセッションの部屋に移動する人々を見て、Pythonistaの学習能力の高さを感じました。

Pythonではじめてみよう関数型プログラミング

スライド: https://speakerdeck.com/meganehouser/pythondeshi-metemiyouguan-shu-xing-puroguramingu-058b9e1e-22f1-4f5e-80ba-4563f965140e

F#に出会ってから関数型プログラミングに関心を持った方による発表です。 F#のコードをベースに、fn.pyだと〜のように書けるという内容になっています。関数型プログラミングについては、ある程度知識を持っているつもりでしたが、永続データ構造に関する話は新鮮でした（お前本当に競プロerか？？）。また、モナドもトピックとして挙がっていましたが、さすがに軽く紹介する程度でした。なお、「Pythonで一からはじめるモナド」をいつか発表するかも、とのことです。超絶聞きたい...

昼食

同僚の先輩（隣の席）とエンカ。Day 1は参加していなかったようなので、「Day 1は最高でした」と言っておきました。弁当は豚の角煮に釣られて和風の弁当を選びました（煮物はあまり得意でないくせに）。

婚活・恋活領域におけるPythonを使ったマッチング最適化

大人の事情により、スライドは公開されないようです。

マッチングアプリにおける、ユーザーを見つけるプロセスに焦点を当てた内容です。発表の冒頭で安定結婚問題やGale-Shapley法という言葉が出てきてテンションがアガリましたが、マッチングアルゴリズムやメカニズムデザインについては深入りしない内容でした。全人類に対してペアのスコアを計算しようとすると死ぬので、人類をグループ分けし、各グループについて、そのグループに属すペアのスコアを計算するという内容だったと思います。また、Auto MLを用いることでスコアリングの精度を最大20%改善できた、という報告もありました。

入門自作検索エンジン

スライド: https://speakerdeck.com/ryook/the-first-step-self-made-full-text-search

自分の手でゴリゴリと検索エンジンを作るお話です。手を動かしながら聞きたいかも！？バックグラウンドとなる知識がないと追いつくのはちょっと厳しい印象です。とはいえ車輪の再発明の面白さが伝わる発表でした。

機械学習ライブラリのPython API作成方法

機械学習とありますが、機械学習は本質ではなかったです。外部ライブラリのラッパーを作る話で、pytestだとメモリ使用量が変わるという問題をに気づくのに時間がかかった、というネタがありました。正直、タイトルから乖離がある内容かなと思いました。

Ansibleを通じて「べき等性」を理解してみよう

スライド: https://attakei.net/slides/pyconjp-2019/index.html#/

べき等性とは何か、べき等性を満たすツールは何が嬉しいか、Ansibleはどのようにべき等性を満たしているのか、という内容です。説明がていねいで、初心者にとってもわかりやすかったです。 Ansibleに関するトークが少ないのは個人的に意外でしたが、Ansibleはどちらかというとインフラエンジニアに受けがよく、PyConの参加者とはそれほどマッチしないため、Ansibleに関するトークは少ないのではないかとのことでした。

LT

Xonsh は俺得だなと感じました。後日、遊んでみたいと思います。 PyConのネットワークに関するトークも興味深いですね。あれだけの人が参加するカンファレンスで、あそこまで快適にネットワークが使えるようにした技術力には脱帽です。

おわりに

素敵な二日間で、Pythonistaとしての経験値を大量に獲得できました。一方で、自分も経験値をアウトプットする側に回りたいという気持ちも生えました。あるいはスタッフとしてPyCon JPコミュニティにcontributeしたいですね。 Pythonは長年お世話になっている言語なので、何らかの形で恩返しができるようこの一年を過ごしたいと思います。

最後に、PyCon JPのスタッフのみなさま、参加者のみなさまに心より感謝を申し上げます。

2019-07-04

PythonistaがRustはじめました#008 -- 可変Vecで動的計画法

ABC Rust

なんとか仕事は山を越えました。明日からはきちんと定時に帰って、記事を書く頻度を上げられるようにしたいです（フラグ）。

最近はRustもだいぶスラスラ書けるようになった気がします（ただし、競技プログラミングのみ）。制限時間がシビアな高得点問題をRustで解く選択肢もそろそろ見えてきました。

ABC132-F

入力: 正の整数N, K
出力: （隣り合う項の積がN以下であるような長さKの正の整数列）の個数

https://atcoder.jp/contests/abc132/tasks/abc132_f

解き方

ポイントは正の整数X, A, B について、X = AB ならば min(A, B) <= sqrt(X) が成り立つことです。

P = floor(sqrt(N)), Q = floor(N / M) とします。 [1, N] の整数から成る集合を以下のP + Q - 1 個の集合に分割します。

G_1: 1のみ含む集合
...
G_{P}: P のみ含む集合
G_{P + 1}: floor(N / i) = Q - 1 を満たす整数iの集合
G_{P + 2}: floor(N / i) = Q - 2 を満たす整数iの集合
...
G_{P + Q - 1}: floor(N / i) = 1 を満たす整数iの集合

このとき、以下が成り立ちます。

i <= P ならば |G_i| = 1
i > P ならば |G_i| = floor(N / (P + Q - i)) - floor(N / (P + Q - i + 1))
G_i に属す要素g_iと G_j に属す要素g_j について、i + j <= P + Q ならば g_i g_j <= 2N

長さがL、かつ、隣接して並んでいるどの2つの整数の積もN以下、かつ、列の最後の要素が G_i に属すような列の個数を dp[L][i] とします。以下が成り立ちます。

L = 1 ならば dp[L][i] = |G_i|
L >= 2 ならば dp[L][i] = |G_i|(dp[L - 1][1] + ... + dp[L][P + Q - i])

求める解は dp[L][1] + ... + dp[L][P + Q - 1] となります。

RustでDPするには

値の変更とか面倒そうですが、意外と簡単にDPできます。例えば、要素数Nの1次元配列を用いてDPしたい場合、

let mut dp = vec!(0; N);
dp[0] = 1;
dp[1] = 1;
for i in 2..N {
  dp[i] = dp[i - 1] + dp[i - 2];
}

のように書くだけです。 vec!(x; N) で各要素がxである長さNのVecが得られます。 Vecの値は書き換えたいので、 mut を忘れないように気をつけましょう（忘れるとコンパイラに怒られます）。

注意: Vecの添字にはusize型を指定する

dp[i] のようにVecのi番目の要素を取得する際、iはusize型である必要があることに注意です。 Nをusizeの値とすると、 (0..N) が生成する整数はusizeとなるので、整数が非負ならばusize型として宣言したほうがいいかもしれません。

コード

fn main() {
    let (N, K) = get!(usize, usize);
    let MOD: usize = 1000000007;

    // floor(N / i) の値に応じてグループ分けし、
    // グループ単位で条件を満たす列の個数を動的計画法で求める
    let P = (N as f64).sqrt() as usize;
    let Q = N / P;
    let R = P + Q;
    let C = (0..R).map(|i|
        if i <= P {
            1
        } else {
            N / (R - i) - N / (R - i + 1)
        }
    ).collect::<Vec<_>>();
    let mut dp = vec![vec![0; R]; K];
    for i in 0..R {
        dp[0][i] = C[i];
    }
    for j in 1..K {
        let mut acc = 0;
        for i in (1..R).rev() {
            acc = (acc + dp[j - 1][R - i]) % MOD;
            dp[j][i] = (C[i] * acc) % MOD;
        }
    }
    let ans: usize = dp[K - 1].iter().sum::<usize>() % MOD;

    println!("{}", ans);
}

ちなみに上記と同等のPythonコードをPyPyとして提出したらTLEでした。一方で、上記Rustコードは45ms.　圧倒的ではないか！ Pythonは縛りプレイと呼ばれている理由が理解できますね。

2019-06-22

PythonistaがRustはじめました#007 -- クロージャは便利

極限残業ラッシュにより、10日ぶりの記事になっちゃいました。来週も厳しい一週間になりそうですが、Streakは切らさないようにしたいです。

CADDi 2018-C

入力: 正の整数N, P
出力: a1 a2 ... aN = P を満たす数列 a について、 a の最大公約数の最大値

例えば、(N, P) = (2, 720) ならば 12を出力すればよいです（a1 = 60, a2 = 12 とすることで P = a1 * a2 であり、 gcd(a1, a2) = 12を満たす。これより最大公約数が大きくなるようなaは存在しない）。

https://atcoder.jp/contests/caddi2018/tasks/caddi2018_a

方針

300点問題だけあって、straight forwardな解法では解けないです。ポイントは素因数分解です。 2以上sqrt(P)以下の整数でPを割り続けることで、P を 2^P2 * 3^P3 * ... の形に表したときのP2, P3, ... を求めることができます。そして、各素数について、P2, P3, ... を a1, a2, ... aNになるべく等分割することで、gcd(a1, a2, ..., aN) を最大化できます。

数え上げの際に便利なfold

あとは実装するだけです。ループをゴリゴリ回して解いてもいいのですが、Rustは高階関数も豊富なので、それを使って解いてみましょう。今回使うのはIteratorの fold メソッドです。 Pythonでいうreduceですね。例えば、1+2+...+N を以下の式で表現できます。

(1..=N).fold(0, |acc, i| acc + i)

非常に簡潔ですね！！（和なのでsum使えばもっと綺麗なのですが、任意の演算について上記のように書けることがポイントです） Pythonより綺麗だと思います（Pythonだと reduce(lambda acc, i: acc + i, range(1, N + 1), 0) ですね。lambdaがだるい）。おっと、初めて出てきた記法が二つあるので、それらを解説していきます。

Range

(1..=N) はRangeと呼ばれるオブジェクトです。 Pythonでいう range(1, N + 1) ですね。ちなみに、(a..b) だと a, a + 1, ..., b - 1 のように半開区間となります。

クロージャ

今日の本題？です。 |acc, i| acc + i はクロージャと呼ばれるものです。クロージャに関する詳しい説明は公式ドキュメント https://doc.rust-jp.rs/book/second-edition/ch13-01-closures.html を読めばよいです。ざっくりと、クロージャを使う上でのポイントを挙げてみます。

関数はシグネチャの定義が厳密ですが、クロージャはかなりゆるふわです。Pythonのラムダ式とほぼ同じノリで使えます
再帰は無理です（Pythonのラムダ式でもそうですよね）
クロージャは式として扱えます
パターンマッチによる引数の束縛が可能です（重要！）。例えば、クロージャ |(a, b), c| a * b + c に ((3, 2), 1) を引数として呼び出すと 7 が返されます。

最後がかなりお気に入りです。Pythonだと lambda t, c: t[0] * t[1] + c のように書く必要があり、非常につらい気持ちになります。 foldを適用する際、(解, 補助累積値)のようなタプルを畳み込むケースがかなり多いので、そのときは気持ちよく束縛していきましょう。

コード

素因数分解の指数部を求める関数をfとしています。

fn f(p: i64, i: i64) -> i64 {
    if p % i == 0 {
      1 + f(p / i, i)
    } else {
      0
    }
}

fn main() {
    // 入力
    let (N, P) = get!(i64, i64);

    // 素因数分解した結果を用いて解を求める
    let (ans, _) = if N == 1 {
        (P, 1)
    } else {
        let Q = ((P as f64).sqrt().ceil() as i64) + 1;
        (2..Q).fold(
            (1, P),
            |(acc, p), i| {
                let k = f(p, i);
                (
                    acc * i.pow((k / N) as u32),
                    p / i.pow((k as u32))
                )
            }
        )
    };

    // 出力
    println!("{}", ans);
}

2019-06-10

PythonistaがRustはじめました#006 -- 文字列を扱う

有休を取得するも、雨で一日中引きこもっていました。一部の競プロerで評判のよい映画「響け！ユーフォニアム」を観に行って、その帰りに久々に北極の火山を食べるムーブをしたかったのですがねぇ...。しかし、その分いろいろと精進する時間があり、（質素ですけど）ポートフォリオを作ったりしてました: https://wotsushi.github.io/portfolio/ GitHub Pages便利だね。

本題。Rustで少しくせのある文字列の扱いについてです。

tenka1-2019 B

入力: 文字列S、整数K
出力: SのK文字目と異なる文字を * に置換した文字列

https://atcoder.jp/contests/tenka1-2019-beginner/tasks/tenka1_2019_b

RustのStringはランダムアクセスできない

C++, Java, Pythonなど多くの言語では文字列型の値に対して、そのi文字目を取得することは容易です。例えば、Pythonでは S[i] と書けば (0-indexedで) それはi文字目を表します。しかしながら、RustではStringにそのようなメソッドは用意されていません。

参考: 文字列型 - The Rust Programming Language -- 文字列に添え字アクセスする

そのようなメソッドが存在しないことの詳しい理由は上記リンクに譲りますが、ざっくり言うと、RustのStringはUTF-8によるエンコード列を1バイトごとに区切ったシーケンスであるためです。つまり、ひらがなのように2バイト文字が文字列に含まれる可能性を考慮すると、Stringのi番目の要素はi文字目を意味しないため、メソッドとして提供するのはいかがなものか？という考えです。

とはいえ、競プロにおいては基本的に1バイト文字から成る文字列しか扱いません。やはりPythonのように、i文字目にアクセスしたくなります。

文字列をVecとして扱う

1バイト文字しか扱わないならば、char型のVec（シーケンス）に変換する手があります。流れは以下の通りです。

Stringのcharsメソッドを使いcharsに変換する
charsのcollectメソッドを使い Vec<char> に変換する。なお、collectは何型にするかを指定する必要があるが、それには Vec<_> と指定すればよい（いちいちVec<char> と書く必要はなし）

得られたVecに対して、i番目の要素にアクセスすることでi文字目を得ることができます。それだけではなく、以前取り上げた操作も適用できます。つまり、into_iterメソッドを使い、Iteratorのメソッドで遊び倒せるのです！遊び終わったら、collectメソッドを使ってStringに戻して出力すればよいです。

map

さて、Iteratorに変換後にできる楽しい遊びとして、お馴染みのmapがあります。これは、引数の関数をIteratorの各要素に適用した新たなIteratorを得るメソッドです。

mapの引数に関数を指定する際、無名関数をしばしば指定しますが、Rustでもそのような指定が可能です。記法はRubyに近く、例えば以下のように書きます（iterをi64のIteratorとします）。

iter.map(|e| 2 * e)

コード

これまでの新しい道具を用いることで、tenka1-2019 Bを解けます。コードは以下の通りです。

fn main() {
    // 入力
    let N = get!(i64);
    let S = get!(String).chars().collect::<Vec<_>>();
    let K = get!(usize);

    let p = S[K - 1];
    let ans = S.into_iter().map(|c| if c != p { '*' } else { c })
        .collect::<String>();

    // 出力
    println!("{}", ans);
}

型変換が忙しいけど、メソッドチェーンが楽しいね！ https://atcoder.jp/contests/tenka1-2019-beginner/submissions/5788747

そして、明日はバチャコン。そろそろRustでリベンジしたい。

2019-06-06

PythonistaがRustはじめました#005 -- 所有権

Rustの最初の難関っぽい所有権についてまとめてみます。

参考までに、Rustの学習曲線として以下のグラフがあります。ライフタイムは所有権に関係していると思っています。

https://keens.github.io/slide/rustnokoremadetokorekara/

100時間はROMってろ！って感じですね。

それでは、公式ドキュメントを読みながら理解していきましょう。 https://doc.rust-jp.rs/book/second-edition/ch04-01-what-is-ownership.html

所有権規則

以下の3つのルールが基礎を成すようです。

ルール1: Rustの各値は、所有者と呼ばれる変数と対応している。
ルール2: いかなる時も所有者は一つである。
ルール3: 所有者がスコープから外れたら、値は破棄される。

上記の規則により、Rustでは ガベージコレクション 機能はないようです。

この所有権規則はプログラマにどのような制約を課すのでしょうか？ NG例が分かりやすいですね。

let s1 = String::from("hello");
let s2 = s1;

println!("{}, world!", s1);

大多数のプログラミング言語では、上記のようなコードは問題なく hello, world! を出力するでしょう。しかし、Rustでは上記コードをコンパイルすると、以下のコンパイルエラーが出ます。

error[E0382]: use of moved value: `s1`
              (ムーブされた値の使用: `s1`)
 --> src/main.rs:5:28
  |
3 |     let s2 = s1;
  |         -- value moved here
4 |
5 |     println!("{}, world!", s1);
  |                            ^^ value used here after move
  |                               (ムーブ後にここで使用されています)
  |
  = note: move occurs because `s1` has type `std::string::String`, which does
  not implement the `Copy` trait
    (注釈: ムーブが起きたのは、`s1`が`std::string::String`という
    `Copy`トレイトを実装していない型だからです)

これは、所有権のルール1, 2に反するためです。 Rustではヒープ領域に存在する "hello" というデータに対して、それを所有する変数という概念があります（ルール1）。そして、"hello" の所有権を持つ変数はs2のみです（ルール2）。 let s2 = s1; で "hello" の所有権は変数 s1 から s2 に移ります。その結果、s1の "hello" の所有権は放棄されるので、s1を通して "hello" にアクセスはできなくなってしまいます。

この所有権のルールは、関数の引数渡しにおいても成り立ちます。

fn main() {
    let s = String::from("hello");  // sがスコープに入る

    takes_ownership(s);             // sの値が関数にムーブされ...
                                    // ... ここではもう有効ではない
}

fn takes_ownership(some_string: String) {
    println!("{}", some_string);
}

上記のサンプルコードにおいて、 takes_ownership に s が渡されていますが、これにより、 "hello" の所有権は take_ownership の some_string に移ります。したがって、 take_ownership 呼び出し後、 s を通して "hello" にアクセスできなくなります。

借用

所有権ルールに関するサンプルコードを見ると分かる通り、所有権ルールは非常に強い制約です。とくに関数の引数渡しで一々所有権の譲渡が行われるのはしんどすぎます。変更するなら譲渡の手続きはやむを得ないとしても、参照させるだけならもうちょっと簡略化できないものかと思ってしまいます。この簡略化手続きが借用になります。

以下のサンプルコードが分かりやすいです。

fn main() {
    let s1 = String::from("hello");

    let len = calculate_length(&s1);

    // '{}'の長さは、{}です
    println!("The length of '{}' is {}.", s1, len);
}

fn calculate_length(s: &String) -> usize {
    s.len()
}

ポイントは引数に&をつけること。 ABC116-BのHashSet.containsの引数につけた謎&は参照渡しの&だったという訳です！上記コードは、sに対して変更を加える訳ではないので、所有権ではなく参照権だけもらえればいいや、という気持ちを表現しているのです。 HashSetのcontainsも引数が集合に属すかどうかを判定するのに使うだけなので、参照権だけで十分ですよね？したがって、所有権を渡すというオーバーキルを避け、&をつけて参照権だけ渡すことになっているのです。

ちなみに、mutをつけることで、可変な参照権を渡すことができます。ただし、可変な参照権は一つしか渡せない、既に不変な参照権を渡している場合、可変な参照権は渡せない、などの制約があります（トランザクション分離レベルっぽいですねぇ）。

ほとんど、公式ドキュメントの引用になってしまいましたが、ひとまず以上です。なお、ここまでの話ではABC098-Aのコンパイルエラーが error[E0597]: borrowed value does not live long enough 説明できていないと思います。これは、ライフタイムの話をまとめる際に解説しようと思っています。

結果

試験勉強について

基礎知識の勉強（8月上旬〜8月中旬）

午後対策（8月中旬〜試験前）

午前2対策（9月下旬〜）

試験当日について

午前2

昼飯

午後1

午後2

おわりに

戦利品

立ち回り

メモ

はじめに

Day 1

開始前

Python開発を円滑に進めるためのツール設定

昼食

Yet Another Isolation Debian packageと紐づく環境分離

PyRun - Shipping the Python 3.7 runtime in just 4.8MB

Coffee Break

Pythonを使ったAPIサーバー開発を始める際に整備したCIとテスト機構

pandasのStyling機能で強化するJupyter実験レポート

LT

Party

Day 2

開始前

Pythonではじめてみよう関数型プログラミング

昼食

婚活・恋活領域におけるPythonを使ったマッチング最適化

入門 自作検索エンジン

機械学習ライブラリのPython API作成方法

Ansibleを通じて「べき等性」を理解してみよう

LT

おわりに

ABC132-F

解き方

RustでDPするには

注意: Vecの添字にはusize型を指定する

コード

CADDi 2018-C

方針

数え上げの際に便利なfold

Range

コード

tenka1-2019 B

RustのStringはランダムアクセスできない

文字列をVecとして扱う

map

コード

所有権規則

借用

入門自作検索エンジン