2018-09-07

汎用コマンド探訪 2 - lsof

Command Tech

lsof - List Open Files

wikipediaより：

lsofとは、オープン中のファイルや、そのファイルをオープンしているプロセスのリストを出力するコマンドである。

これの便利なところは、

オープンされている全てのディスク上のファイル、パイプ、ネットワークソケット、デバイスドライバが含まれる。

といったところ。つまり、全ての開かれているファイルと、そのファイルを使用しているプロセス全体を調べるため、包括的な調査が可能になる。

例えば、-iオプションで、そのポートを使っているファイルを調べると、

lsof -i:port_number

f:id:hazuhi:20180907172134p:plain

のようになる。

ちなみにポートスキャンは、macならプリインストールの Network Utilityで簡単に行うことができる。

参考：

Captcha

このポートで実行中のプロセスはどれ？ lsofコマンドの使い方：ネットワーク管理の基本Tips - ＠IT

2018-09-03

DataloaderのExportとExport allの違い

Salesforce

下記の質問と回答より抜粋。

Data Loader - Export & Export All - Answers - Salesforce Trailblazer Community

Export

"It is used to export the Salesforce Data(excluding recycle bin's data) into your local system."

つまり、ゴミ箱のデータを除いた全レコードを吐き出す。

Export All

"It is used to export the Salesforce Data(including recycle bin's data) into your local system."

つまり、ゴミ箱のデータも含んだ全レコードを吐き出す。

2018-09-02

はてなMarkdownを書くときに参考にしたサイトまとめ

自分が改めてまとめるほどでもないほどたくさん記事があるので、とりあえず参考にした記事をメモしておく。

# Markdown

はてなで使えるMarkdown記法まとめ - 開発メモ

# 数式

普通にLatexの書式がわからないとき：

LaTeXコマンド集

記号を知りたいとき：

LaTeXƒRƒ}ƒ“ƒhƒV[ƒgˆê—— - ‚·‚×‚Ä‚Ì‹L†

はてなの数式の謎仕様について参考になる：

はてなブログで数式（Markdown） - エフアンダーバー

2018-09-02

AtCoder Beginner Contest 108 参加ログ

AtCoder

ABC108に参加しました

AtCoder Beginner Contest 108 | AtCoder

実力：緑色 / 現R: 916

ここ数回は、参加していたもののいずれも爆死。メンタルをやられてログを書いていませんでした。

今回もほぼ爆死ですが頑張って翌日に書いています。

A - Pair

いつも通り普通に解けばおk

B - Ruined Square

珍しくほぼ完全に図形の問題だったので、これで手こずった人も意外といそう（はい私です。

f:id:hazuhi:20180902145012j:plain

この問題は、図をあれこれ弄ることなく、回転行列を使って解く方が簡単だ。

$\displaystyle \begin{bmatrix} cos\theta & -sin\theta \\ sin\theta & cos\theta \end{bmatrix}$

で原点を中心に反時計回りに $\theta$ だけ回転するから、 1と2を入れ替えて、

$\displaystyle X_3 = \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix} (X_1 - X_2) - X_2$

$\displaystyle X_4 = \begin{bmatrix} 0 & 1 \\ -1 & 0 \end{bmatrix} (X_2 - X_1) - X_1$

C - Triangular Relationship

問題文の解釈

三角関係という甘美な響きの問題だが、3人の関係は（Kを法として）いつでも対等である。

問題文を解釈していこう。

Kで割った余りが等しい関係を $\equiv$ で表そう。

$0 \leq a', b', c' K$ かつ $a \equiv a', b \equiv b', c \equiv c'$

の $a', b', c'$ の関係は、

$a' + b' = 0 \ or \ K \\ b' + c' = 0 \ or \ K \\ c' + a' = 0 \ or \ K$

$a' + b' = 0$ の時、 $c' = 0$ が言えるので、 $a' = b' = c' = 0$
$a' + b' = K$ の時、

2.1. $a' = 0$ の時は、 $b' = K$ となるが、残りの式から矛盾が言える。

2.2. $a' \neq 0$ なら、 $c' + a' > 0$ 。よって $c' + a' = K$ なので、 $b' = c'$ 。同様にして $a' = b' = c'$ になる。

元の式と比べると、Kが2の倍数の時に限り、 $a' = b' = c' = K/2$ となる。

計算

あとはどうやって数え上げるかが問題になる。

$a' = b' = c' = 0$ の場合 a, b, cが全てKで割り切れる組み合わせを全て数えれば良いので、

(n//k)**3

となる。

$a' = b' = c' = K/2$ の場合

1.を除くために、全部 K/2の倍数で、かつKの倍数でないものを数え上げる。

((n - k//2)//k+1)**3)

で計算できた。

最終的にワンライナーで書けて、

print((n//k)**3 + (1-k%2)*((n - k//2)//k+1)**3)

となる。

D - All Your Paths are Different Lengths

所感

2進数をグラフで表現すれば良いことにはすぐ気がつくだろう。でも、実装力がないと解けない問題のようだった。

自分は時間が足らず解けなかった。

今回も本家解説を読んで、概要だけでも書いておきたい

作るべきグラフの形

結局、何を作ればいいのかは、次図を見ていただければわかりやすいかと思う。 f:id:hazuhi:20180902171508j:plain

これは、 $L = 150$ の時の一つの解なのだが、大きく分けて２種類のエッジがある。

一つは鎖状に繋がっているエッジで、これは1番ノードから終端ノードまで繋がっている（ここでは主鎖と呼ぼう）。
もう一つは、各ノードから最後のノードに直接橋渡しをしているものだ。

主鎖によって、2の累乗までの数字を全て表現できるようになる。主鎖のような構造が、最も単純に2進数を表すことのできるグラフだ。

問題で問われているのは、任意の数字 $L$ までの数字を漏れ・ダブりなく表すことであるから、この主鎖を応用して、数字の大きい方から順に埋めていけば良い。

主鎖のノード $i$ から取得できる数字は、[tex: 0 ~ 2ⁱ - 1]※ なので、ノード $i$ から取得できる最大の数字が、今足りていない最も大きな数字に合致するように、定数を足せば良い。

具体的に説明しよう。

図では、 $i = 2, 3, 5$ のノードから、終端ノードにエッジが伸びている。

これらはそれぞれ、0~1, 0~3, 0~15を表す数字を出力している。これらに定数を足して、

128~129, 130~133, 134~149を表すようにしている。

127までは、主鎖で表すことができるから、これで条件は満たされている。

二進数

ところで、主鎖は2進数を表すといった。

150を2進数で表すと、"10010110"になる。

ひっくり返すと、"01101001"になるが、これがちょうど上の鎖の構造と同じことが分かるだろうか。

つまり、2進数表記で右から $i$ 桁目のビットが1ならば、ノード $i$ から終端ノードにエッジを伸ばせば良い。その時の定数の大きさは、 [tex: n - 2ⁱ]※ となる。

※はてな Markdownの数式は()なので()です。

結果

R916 => R945 (Up)

頑張って早く青色コーダーになりたい

2018-09-01

■

Macの容量がなくなってしまった。

最近JetBrainsのIDEをたくさん入れてしまったので、ストレージが満杯になってしまった。開けるために何をしたかを書いておく。

ストレージの管理から、不要なファイルを削除
OmniDiskSweeperで不要そうなファイルを探して削除
duコマンドでも探してみる
homebrewのキャッシュを削除

一番効いたのは、homebrewのキャッシュだった。

1. ストレージの管理から、不要なファイルを削除

f:id:hazuhi:20180901195444p:plain

ここから。 Downloadsにあるファイルを消した（※図はすでに消した後）。

2. OmniDiskSweeperで不要そうなファイルを探して削除

起動して、ディスクを選択すると、容量の計算が始まる。 f:id:hazuhi:20180901195707p:plain

赤くなっている部分が計算中のフォルダで、紫が計算済みの様子。

よくフォルダを調べていくと、homebrewのキャッシュがかなり容量を食っていた。

消す（残 8.4 GB => 11.6 GB）。

3. duコマンドでも探してみる

sudo du -gx -d 5 | awk '$1>=5{print}'

f:id:hazuhi:20180901200206p:plain

5GB以上のフォルダをまとめて表示させる。

（duは容量を計算するコマンドで、awkは結果を整形・表示するコマンド）

duコマンドの計算は結構遅いようで、表示に時間がかなりかかっていた。

OmniDiskSweeperの方が良さそう。

4. homebrewのキャッシュを削除

結果的にこれが最も効果的だった（残 11.6 GB => 17.24 GB）。

brew cleanup -s

以上。

2018-07-24

Kaggle Titanicやってみる

Tech

Kaggle

Kaggleを知っているだろうか

Kaggle: Your Home for Data Science

最近流行りのデータサイエンスを、世界的な競技大会にしたwebサービスだ。

これに参加することにした。

チュートリアル

データサイエンスを全て自前で行うのは、かなり技術的ハードルが高い。というのも、

データ収集の方法
集めたデータを処理する技術
統計手法に関する知識と、それをデータに適用する技術
それらを実行する環境
その環境を用意する技術

最低限これらが必要になるからだ。

けれど、Kaggleに参加するだけなら、これを全部やる必要はない。

Kaggleがデータを持っているし、Kernelを使えば、4, 5が不要になる。

karaage.hatenadiary.jp

この記事に倣って、KernelからTitanicを解いてみる。

Kernel

Kaggleへの登録を済ませたら、Kernelは @karaage. 氏の記事を見れば簡単に使えると思う。

基本的にJupyter notebookと同じ使い方ができる。

Kernelを使う際に押さえておくべきポイントは、

1. 使える言語はR, Pythonだけ。

2. ワークスペースが与えられ、そこで作業が完結する。

3. 予測データの提出（"Submit to Competition"）はkernelを公開(publish)した後に行える（参考：Submitting From A Kernel | Kaggle）。

このくらいか。

写経とその結果

参考：【Kaggle初心者入門編】タイタニック号で生き残るのは誰？

上記記事を参考に、最も単純な決定木を実装する（titanic test | Kernel）。

全くチューニングなど行わずとも、約70%の正答率だった（なお 9876位 / 10556チーム中）。

こんな簡単に予測ができるのはやっぱり面白い。

次からは順位を（正解率を）どうやって上げていくのか考えてみよう。

2018-07-22

AtCoder Beginner Contest 103 参加ログ

AtCoder

ABC103に参加しました

AtCoder Beginner Contest 103 - AtCoder Beginner Contest 103 | AtCoder

実力：緑色（最高R: 1007, 現R: 964）

今回は概ね時間通りに参加。

A, B

いつも通り普通に解けばおk

今回はAが少し引っ掛けで、Bが少し考える問題だったか

C - Modulo Summation

今回はCでつまづいた。

C問題自体はそれほど難しくはなかった。

ai列の最小公倍数より1だけ小さい整数の時に、fが最大となることに気がつけば良い。

だがここに至るまでにも紆余曲折経た。次のような思考をして答えにたどり着いた。

1. 全ての剰余類についてfを計算して、最大を探せば良いのでは？

2. 次の例でn = 24までを調べてみると、値の変化が12周期である。つまり最小公倍数ごとに１周する。

3
3 4 6

3. ai≤105かつN≤3000なので、最小公倍数は最大で1015000。全部は計算できない。

4. 計算量が究極に少ないのは、決め打ちすることだよな

5. あれ、最小公倍数より１だけ小さい数字は、元のどの数も割り切らないぞ

つまづきポイント

「最大公約数(GCD)を計算するmath.gcdは、Python 3.5から追加」

コレだ。

Pythonで最大公約数と最小公倍数を算出・取得 | note.nkmk.me

最小公倍数(LCM)を計算するのに、GCDを計算しなければいけないが、それをそのままこのサイトから持ってきてしまった。

AtCoderはPython3.4.3なので、math.gcdは使えない。

反省点

AtCoder上でコードテストができるので、それを使ってまず試す。

また環境を3.4.3に合わせる。

D - Islands War

計算量をうまく減らすことができず、TLEのまま時間切れ。

（C問題を提出してすぐDを解き始めたので、CのREに気がつかず両方落とす結果に）

解説を読んで自分なりに解説してみたい

aでソートされた列を考える基点にしていると、うまく正解にたどり着かないのかもしれない。

元の配列をbで安定ソートすると、下のようになる。

f:id:hazuhi:20180722000959j:plain

○のうち、左側がa, 右側がbだ。

こうやって並べてみると、確かに上から処理していけば、右に部分問題が残るのでうまくやれそうに見える。

反省点

1. 問題を多角的に捉えられていない。

2. 特に部分問題に分ける意識が低かった（部分問題に分けようとすれば、自ずと並び替えにも至ったかもしれない）

結果

R964 => R919 (Down)

次はCまでは解けるようにしたい、、、