Atcoder Beginers Contest 123 の解法ふりかえり
最近 アルゴリズムとデータ構造 の重要性を業務で意識させられることがあって, ちょこちょこ Atcoder Beginners Contestの過去問を解いている。
生のコンテストも出たいなと思いつつ時間がなかなか合わなかったのだが, 今回はタイミングあったので出場した。
結果
利用言語は Python3
A, B, C は解けた, Dはゴリ押し解法でサンプル一個目だけ通せたが時間制限に間に合わず。。。
以下, それぞれの問題について振り返ったあと, 全体の感想述べていく。
問題振り返り
A
考えたこと
- 入力の時点で sort されているので, 最大の差分は 先頭の要素と末尾の要素の差分
- 直接回答書き始めたら for の後の
:書きそこねてて RE くらった. 最低限の local debug はしましょう... 最初は 配列初期化 + append で入力作っていたが, 内包表記 で書ける
解説での学び
- Aは想定通りだったので, 特になかった
AC 回答
- before
a = [] for i in range(5): a.append(int(input())) f = a[-1] - a[0] <= int(input()) print("Yay!" if f else ":(")
- after
a = [int(input()) for i in range(5)] d = a[-1] - a[0] <= int(input()) print("Yay!" if d else ":(")
B
考えたこと
- Bは 全探索 で間に合うパターンが多いのは過去問見てて思ってたいので最初考えたが, 下一桁が0以外のもので最小のものを探せば良いことに気づいた。
下一桁が0以外のもので最小のものを探す関数を map, filter 使って作ったが, テストケースで最後のものだけ RE- RE の原因気づくのに時間がかかったが, すべての入力の下一桁が 0のとき
min([])するような関数を作っていたからだった。 - python の map or filterで 無名関数 使いたいとき
lambdaの文字列タイプするのはやや面倒
RE回答
a = [] for i in range(5): a.append(int(input())) def ceil10(n): if n % 10 == 0: return n else: return ((n // 10) + 1) * 10 def min_1(a): a2 = list(filter(lambda a: a > 0, (map(lambda e: e % 10, a)))) return min(a2) ans = sum(map(ceil10, a)) - 10 + min_1(a) print(ans)
解説での学び
- 切り上げの実装は, 下一桁が0 のケースで場合分けする方法もあるが, 9を足して
((n + 9) // 10) * 10のようにする方法もある。 - わざわざmap, filter使わなくても, loopで書けるしその方が読みやすい(解説がC++だからというのはあるかもしれない)
AC 回答
- before
a = [] for i in range(5): a.append(int(input())) def ceil10(n): if n % 10 == 0: return n else: return ((n // 10) + 1) * 10 def min_1(a): a2 = list(filter(lambda a: a > 0, list(map(lambda e: e % 10, a)))) if len(a2) == 0: return 10 return min(a2) ans = sum(map(ceil10, a)) - 10 + min_1(a) print(ans)
- after
a = [int(input()) for i in range(5)] def ceil10(n): return ((n + 9) // 10) * 10 ans = 999 # > 123 * 5 for i in range(5): t = 0 for j in range(5): if j == i: t += a[j] else: t += ceil10(a[j]) ans = min(ans, t) print(ans)
C
考えたこと
- 入力範囲が
<= 10 ** 15なので, O(N) くらいのアルゴリズムでも難しそうだと思った。 あとから計算量について参考になりそうな資料を見たので以下に貼っておく。
- 計算量の目安は以下のまとめがとてもわかりやすかった
- こういうのをブックマークに入れてると便利
- Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell
algorithm complexity cheatsheet(from http://bigocheatsheet.com/)
- Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell
- python だと 計算量 の一覧はこの辺
正攻法を諦めて, 数値が小さいケースで 手元のホワイトボードに書き出して状況を整理
- 最も容量が小さい経路がボトルネック になりそう -> ボトルネックになる経路で何回運搬が必要かに注目して実装
- 証明はできなかったが, テストケース通ったので提出 -> AC
解説での学び
- だいたい想定通り
- pdf回答には証明も書いてあったので, 後から確認した
AC 回答
n = int(input()) a = [int(input()) for i in range(5)] ans = n // min(a) + 4 + (1 if n % min(a) != 0 else 0) print(ans)
D
考えたこと
- 愚直な 全探索 は
(10 ** 10) ** 3なので間に合わない - 出力が大きい順なので, 入力は sort desc しておいたほうが効率が良い.
10 ** 10の sort の O(NlogN) はセーフ
- 出力はuniqueなので, 今まで計算した値は cache しておきたい
- 和を考えるため, 各配列の最大の要素を比較して, 最大のものから取り出して行けば大きい順に出力が構成される
- それぞれの値は A なら Y * Z 回使われる, B,Cについても循環的に考えて同様, 利用回数も cache
=== この辺りでコンテスト終了
解説での学び
- 回答を見て, 出力の制限 (
K<3000) にも着目するべきだった点に気づいた. - 回答には4種類の解法があったが, まだ解法1しか見ていないので後ほど それぞれ 確認, 実装する予定
AC回答
解法#1 O(k2 log k) 制限2000ms に対して max 1945ms かかっていたのでギリギリ
from itertools import product x, y, z, k = list(map(int, input().split())) a = sorted(list(map(int, input().split())), reverse=True) b = sorted(list(map(int, input().split())), reverse=True) c = sorted(list(map(int, input().split())), reverse=True) ab = [ai + bi for (ai, bi) in product(a[:k], b[:k])] ab.sort(reverse=True) abc = [abi + ci for (abi, ci) in product(ab[: min(k, x * y * z)], c[:k])] abc.sort(reverse=True) for abci in abc[: min(k, x * y * z)]: print(abci)
他の人の回答を見て
コード長が短いコード を見て, パット見でに気になったものは以下
c_r_5 さんの回答 より
a,*_,e,k=eval('int(input()),'*6);print(':('*(e-a>k)or'Yay!')
- eval で 文字列として
'int(input())'と 書ける - if-else ではなくて or で表現できる
終了後の雑多な感想
- 参加者 が過去最大規模(約4000人!) だったらしく, コンテスト開始直後アクセスちょっと重かった
- 最近資格試験など受けたりもしていないので, 時間制約付きで問題を解く機会がなかなかなかったので楽しかった
- 入力だけでなく, 出力の制約 にも着目して解法考えるの大事
Python が比較的慣れているから, 書きやすいが map, filter辺り使い始めると method chaining ないのが辛い。この辺り書きやすい言語は模索してみる。 script 言語で時間問題なさそうなら Rubyとかかな? Dで時間, メモリ的にだめなら Julia, Kotlin あたりが候補
以下のpodcast で聞いてデバッガちゃんと使おうという気持ちになったので, pdb をちゃんと使ってみた。今まで IDE debuggerに慣れてたけどこれは便利。 anchor.fm
GCJ は出そびれたのでまた来年...
- データ構造については, Open Data Structure の邦訳がありがたいことに無料公開されているので, そちらで勉強中
- 一人でやるとダレそうなので, お互い進捗報告しあうやつやりたい
書籍レビュー 経営システム 28巻2号「ビジネスでインパクトが出せるデータサイエンティストになるには」
@pseudo_finite さんより, 経営システム 28巻2号をいただいたので, @pseudo_finite さんの解説記事 「ビジネスでインパクトが出せるデータサイエンティストになるには」の感想などを書いていきます。
(1/24 には届いていたのに引っ越しなど諸々忙しくて感想を書くのが遅くなりました :pray:)
本記事では, まず自分の立ち位置を示した上で記事の各章について本文の主張に関連して感想や実務を通して身につけた自分の考え方を述べていこうかと思います。
書いてから記事を読み直すと, 本文が学術誌ということでこの記事の書き方もやや硬めの書き方になってしまいました。
解説記事の章立ては以下のとおりです
1. はじめに 2. データサイエンティストが力を発揮する場 3. 課題設定 4. 解決方法の設計 5. 検証 6. 育成 7. まとめ
このフォーマットはu++ さんのものを大幅に参考にさせていただきました :bow:
【書籍メモ】「ビジネスでインパクトが出せるデータサイエンティストになるためには」 - u++の備忘録
また一旦勢いで書いたのでこの記事はdraft に近いです。参考になるリンクなど随時追記していきたいと思います。
自分の立ち位置
アドテク会社のData Mining (Machine Learning) Engineer 新卒2年目(もうすぐ3年目)です。
肩書はEngineer とはいえ, 会社の特性上, ログ, KPIの分析, 文献調査, offline検証, 設計, 開発, online検証, 運用 など割と全部やるため, フェーズによってはいわゆるデータサイエンティストっぽい業務もあります。
1. はじめに
いわゆる序論で導入と記事の構成の説明を行っています。
導入の中で 近年データサイエンス自体に注目が集まっているのはもちろんだが, 本来的にビジネスの場で必要とされているのは広義のサイエンティストである という要旨の記述があり, とても同意しました。
データサイエンス(以下DS)やMachine Learning(以下ML)は, いわゆるエンジニアリングとは違って結果が確率的なものであるため, 方法論ありきのやり方は失敗しやすいなと最近いろいろな方の話を伺って感じているところです。
2. データサイエンティストが力を発揮する場
企業という場に絞って, 表題通りの内容について解説しています。
本文中で大事なのは主に以下2点だと述べられています。
1 について, DS, MLは0->1や1->10というよりは 100000 を10000 * 1.01 にするような役割を果たすことが多いため, 解説記事中にあるようにニッチな産業あるいは十分なデータがない新規事業だとビジネスインパクトを出すのは難しいと思っています.
ただ例外はあると思っていて, DS, MLの知識自体を売るモデル(教育, コンサル) や既存事業のデータを活用した新規事業の場合はこの限りでないかなと思います。
2 について, 量については割と当たり前なので質の部分に触れていきます。
本文中ではデータの質に関して, 匿名データより実名データ, 閲覧データより購買データの方がユーザの性質をよく表しているため質の高いデータであるという旨が書かれています。
自分の業務(アドテク)周りだと, アドフラウドなどで不正なclick除外したり, conversion はユーザによって定義が違うので気をつける必要があります。実務のML Engineer の業務は前処理がほとんどと言われるのもこの辺りの所以なのかなと思います。
またデータをどう活用するかという観点からテーブル定義やロギングの設計を行うのもとても大事なことです。
3. 課題設定
適切な課題設定が大事だと言う話でそもそも解くべき問題か?を考えるのが重要だと述べられています。
伝え聞く話では Japanese Traditional Big company などでは, "Deep Learningでいい感じにしてくれ" というようなオーダーがお偉方から降ってくるらしいですが, そのような方にこそ本章を読んでいただくのが良いのではないでしょうか。
ただ翻ってみると自分も方法論ありきで課題を設定してしまう(この言語, フレームワーク,ライブラリ, アルゴリズム が使いたい)ということはあるなと思ったので気をつけようと思いました。
4. 解決方法の設計
前半部では, 手法の検討において, ML, 数理計画, 確率モデリングなどを解決手法として公平に考える必要がある旨が述べられています。
こちらの主張もほぼ同意で, 自分の意見を加えるとプロジェクトの期限やリソースに寄ってはルールベースのロジックで設計するのも検討する必要があるなと考えています。
いずれにせよ前章でも触れたように方法論で解決方法を決めるとロクなことにならないは確かです。
若干後付けですが, 自分も解法をMLで縛りたくないため MLエンジニアではなく Data Mining Engineer の肩書を名乗っています
(弊社では肩書は個人で決めてOKだった)
後半部ではML, 数理モデリングにおいて重要なことがおおまかに以下のように述べられています。
- 実装可能性(いわゆる feasibility)
- 不可能な場合は問題の方の性質を変更する
- 実装容易性, 保守, 運用の容易性
- 近似の精度
それぞれについて, 自分の考えを述べます。
実装可能性
これはちょうど最近あまり考えず雑にタスクを進めてしまったせいで, アプリケーションエンジニア, インフラエンジニアとのコミュニケーションコストが増大して余計に開発期間を要したということあったので耳が痛い話でした。
新規にロジックを実装する場合は アプリケーションエンジニア, インフラエンジニアには事前に確認とっておきましょう。。。
実現容易性, 保守, 運用の容易性
本文中にも述べられていますが, 実務だとモデリングの手直しが必要なことはままあります。
実際に経験したのは オンライン検証の結果モデルに問題があることが判明した, 本番運用において入力データが想定しない形で変更された などです。
本来はモデリングの際に考慮できていればよいのですが, 完璧な考慮は無理です。
したがって改修が容易なコードで実装しておくのが良いため, 設計, リファクタリング周りの勉強はDS, ML Engineer でもしておくと良いと思います。
学習コストとのバランス考えたときの個人的なオススメ本は以下あたりです。
リーダブルコード ―より良いコードを書くためのシンプルで実践的なテクニック (Theory in practice)
- 作者: Dustin Boswell,Trevor Foucher,須藤功平,角征典
- 出版社/メーカー: オライリージャパン
- 発売日: 2012/06/23
- メディア: 単行本（ソフトカバー）
- 購入: 68人 クリック: 1,802回
- この商品を含むブログ (140件) を見る
新装版 リファクタリング―既存のコードを安全に改善する― (OBJECT TECHNOLOGY SERIES)
- 作者: Martin Fowler,児玉公信,友野晶夫,平澤章,梅澤真史
- 出版社/メーカー: オーム社
- 発売日: 2014/07/26
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (11件) を見る
- 作者: 児玉公信
- 出版社/メーカー: 日経BP社
- 発売日: 2011/05/26
- メディア: 単行本
- 購入: 6人 クリック: 23回
- この商品を含むブログ (6件) を見る
近似の精度
実務において何がしかの近似は必ず必要になってくるので, その影響を考えるのは大事です。
時に近似が思わぬ挙動をすることがあるので, モデルの予測精度まで時系列で監視できるような基盤があるのが望ましいかなと思います。またDS, ML周りで物理の強い人が多いのはこの辺りが強いなのかなと思います。
5. 検証
本章で重要だと述べられているのは主に以下2点です。
- スピード重視で検証をおろそかにするのはNG
- 施策の「良さ」の評価
スピード重視で検証をおろそかにするのはNG
これはもちろんで要件定義の段階で検証でモニタリングするKPIはビジネスの意思決定者と握っておくのが望ましいでしょう。
ただし, 対象KPIは検証を行う過程である程度柔軟に変更,追加できるようにしておくほうが良いです。
モニタリングについては改善すべきKPIはもちろん非機能要件の精度, データの量, 質などについても行っておくのが望ましいです。
また, ないとは思いますがMLのフリーランス, SIでPoCまともにやらないところは避けたほうが良いです(社会性フィルタ)
どの程度の確信度で検証を行いたいか。
DS, ML では特に 施策の良さの評価が難しい. 常にmore better の施策が存在することが多いうえにそれを確かめるすべがないという旨が書かれていました。
本文ではよりよい施策の探索法として以下二点が挙げられていました。
- 仮説を元に網羅的に施策を走らせる
- 複数のDSに施策を競わせる
これは業務上では前者は時間や後者は人的リソースの制約で厳しいパターンが多く, (DS, ML Enginner にとって)十分な検証ができないまま開発が進んでしまうのが多いのかなと感じています。
この辺り解決するいい感じのOSS, SaaSが生まれてくれればよいのですが...
6. 育成
サイエンスの能力 と 実務遂行能力 の二点を育てるのが大事だと書いてあります。
実務遂行能力 については,いろいろな人にレビューをしてもらうように著者は心がけていると記述があり, この点についてはとても同意できました。
実務においてまず身につけないといけないのはドメイン知識でありその部分はレビューの中で質問するのが身につくのが早いと考えています。
あとちょうど昨日こんなツイートが流れてきて, そうだなーと思いました。
「コンサルタント型のデータサイエンティストや一部の機械学習エンジニアは直接の開発部隊から部署が離れていることがあり，開発経験が積みにくいことがあります」「開発力のないデータサイエンティストは自分の技術の出口を持てないため価値を出すのが難しいです」 https://t.co/ugiVHVdpJz
— kng (@kng_ac) 2019年3月29日
新人でDS職の人でも最低限のproduction deploy くらいは経験積んでおいたほうが良いかと思います。
サイエンスの能力 については正直アカデミアでないと満足な教育が難しいため各自大学時代に勉強するのが一番大事だと思います。
企業の中では社内での書籍, 論文の紹介仕合いや有識者による勉強会などがあると良いのかなと思いました。
全体を通しての感想
ML, DSは新しい分野であるが故に企業で成果を出すためのノウハウは形式知化してないことが多く, その点で本解説記事はとてもよくまとまっていて良いと思いました。
自分もスキル的にまだまだ未熟ですがスキルを成長させるのはもちろん, 実務で得た知識も積極的に世の中に還元して DS, MLに関わるひとがハッピーになるように貢献できればと思います。
久々に長めの文章を書いて疲れた
よく使うツールまとめ - 個人wiki, タスク管理編
ちょいちょい聞かれるのでまとめてみる。 結構いろいろ試したが, 最近は
個人wiki -> Inkdrop タスク管理 -> ClickUp
で落ち着いた感がある。 簡単に今まで試したものと今使っているものの使い方についてまとめていく。 今まで使った事あるやつの個別の使用感は直接聞いてください。
個人wiki
https://inkdrop.app/
が個人的には今の所ベスト, 有料サービスで 4.99$/mo
今回の記事もdraftは inkdrop で書いている。
今まで試したもの
この辺
自分が使う上で欲しかった機能
- クロスプラットフォーム対応
- マークダウン記法のショートカット機能
- クラウド同期
- 全文検索
- タグ機能
- revision管理機能
- 動作が軽い
- 準WYSWIG
使い方
とりあえずなんでもメモを放り込む感じ, 全文検索があるのでタグ付けとかは気が向いたときにする。 昔はslackやissue投稿の下書きもやっていたが, そちらは最近 editaro を使っている
タスク管理
https://clickup.com/ こちらは個人利用は基本無料。無料でも十分だが, ヘビーユーザ向けの機能が50$/year ほどで使える.
今まで試したもの
自分が使う上で欲しかった機能
- クロスプラットフォーム対応
- kanban形式でのタスク管理
- 他サービスとのAPI連携
- time tracking
- pomodoro
- サブタスク作成
- タスクの繰り返し機能
使い方
論文紹介 - Managing Risk of Bidding in Display Advertising
社内勉強会で紹介したやつです。 数式埋め込みの都合で限定共有でQiitaに投稿しました。
論文紹介 - Managing Risk of Bidding in Display Advertising - Qiita
pure prompt で vcs の情報が出なかった問題
(発生した問題) zsh のプラグインとか設定周りを整理していたときに, いろいろやってから セッション再起動したら pure prompt のvcs情報が出なくなった。 以下と似た症状
(対応) 一応コミットはちゃんと整理していたので, checkout しながら 2分探索して問題のcommit を発見 こいつが悪さをしていた模様
+if type "bat" > /dev/null 2>&1; then + alias cat='bat' +fi
根本原因は特定できていないが, 削除して対応。後で原因は細かく調べる。
(余談)
2分探索はテスト用のscript を用意できるなら git bisectするのが良さそう。
Git - git-bisect Documentation
auto-ls をいい感じにする
esa と typora で個人wiki 的な感じのもの作って満足 して public なoutputをサボっていたので 小ネタを書く
auto-ls
cd したときに デフォルトで 自動的に ls と git status してくれるやつ, history が汚染されにくくなるし便利。
不満点
出力が冗長, scipy に適当にfile を追加してみる
~/gitrepos/github.com/scipy/scipy master* ❯ touch hoge && cd . appveyor.yml CONTRIBUTING.rst hoge MANIFEST.in README.rst setup.py tools benchmarks doc INSTALL.rst.txt pavement.py runtests.py site.cfg.example tox.ini codecov.yml HACKING.rst.txt LICENSE.txt pytest.ini scipy THANKS.txt On branch master Your branch is up to date with 'origin/master'. Untracked files: (use "git add <file>..." to include in what will be committed) hoge nothing added to commit but untracked files present (use "git add" to track)
対策
git status --short と exa を使う
exa について
better ls, rust製
zshrc に以下を追加
export AUTO_LS_COMMANDS=(exa git-status-short) auto-ls-exa () { if type "exa" > /dev/null 2>&1; then; exa fi } auto-ls-git-status-short () { if [[ $(git rev-parse --is-inside-work-tree 2> /dev/null) == true ]]; then git status --short fi }
結果
出力が簡潔になっていい感じ, コードべた張りなのでわかりにくいが, exa 使ってるので色分けもいい感じ。
~/gitrepos/github.com/scipy/scipy master* ❯ cd . appveyor.yml CONTRIBUTING.rst hoge MANIFEST.in README.rst setup.py tools benchmarks doc INSTALL.rst.txt pavement.py runtests.py site.cfg.example tox.ini codecov.yml HACKING.rst.txt LICENSE.txt pytest.ini scipy THANKS.txt ?? hoge
一言
Captio + slackでアイデアメモ
シャワー浴びてるときとか散歩してるときとかにいいアイデア思いついても, パッとメモ取れないのが微妙にストレスだったのでいい方法がないか少し調べて試してみた。
結局一旦captio + slackに落ち着いた。
昔は fastever とか使っていたんですが. 色々あってevernote使わなくなってしまったので。
slackで自分にmentionする方法も使っていたんだけど, 遷移するのが面倒。
Captio
fastever のメール版, どっかのpodcastで最初紹介されてて良さそうだと思ったけど, メールあまり見ないしなーと思って放置していたのだが, 最近以下の記事で言及があって存在を思い出した。
自分はメインのコミュニケーションツールはslackを使っているのでそちらと連携できないか, 少し調べてみた。
slackへのメール転送
普通に公式ドキュメント記載の手順で設定した。こちらの手順で転送用のメールアドレスを取得できるので Captioの送信先にそちらを指定する。
設定した感想
良かったところ
- Captio立ち上げ早いので, パッとかけて良い。これくらいならストレス感じない
- 情報がslackに集約される
微妙なところ
通知バーでは 件名を表示してくれない
slackbotから送られてくるのでmuteできない。
- keyword notificationくらいで十分
