2018-10-25

書類選考に通るレジュメの書き方（ソフトウェアエンジニア）

タイトルは誇大広告。

募集をかけるとレジュメが本当に大量に届きます。うちだとソフト屋（ぼく）が一次選考を頑張ってやっているのですが、届いたレジュメの30%が10秒、50%が30秒でゴミ箱行きです。この（ぼくの）10秒・30秒を突破する法則が出来てきたので、参考までここでシェアします。

ちなにアメリカにあるベンチャー（中小企業）のソフトウェアエンジニア職の話です。
※まともな人には自明のことばかりです

10秒のカベ

長い！
3ページ以上だと読む気が失せます。特に経験3年とかのくせズラズラ水増しするの最悪。コードもそう書くんでしょうか。

Word形式だったりする
お客さんへのレポートをWordで出すのか？という話です。PDFが無難だと思われ。

見てくれ
文字サイズやフォントの不一致、インデントのズレ、表記ゆれが多いと不安になります。コードもそう書くんでしょうか。

大事な情報がない
たまに名前のないレジュメがあるんですよ・・・。

大事な情報がない（２）
Skillの欄が空白とか。たぶん応募前に、募集要綱にあわせて埋めるつもりだったんでしょうね。

大事な情報がない（３）
メアドと電話番号を忘れずに。連絡できません。

スペルミス、文法ミスが多すぎ
あなたはコンパイルできないコードをコミットするのか。

超ミスマッチ
アドミンとかの方が、「今からコード書きたいです！」的にダメ元で応募しても無駄です。

30秒のカベ

ミスマッチ
C#er募集なのに「Pythonのスペシャリストです！C++/C#も可」みたいなやつ。じゃあPythonの会社行けよってなる。

コード書いてる雰囲気がしない
「チームをマネージしました」「仕様折衝しました」「テストしました」「ドキュメント作りました」・・・・「プログラミングしました」。最後にあるってことは、ほとんどコード書いてないね？

コード書いてるのか分からない
「何とかシステムを開発」「何とかシステムはこんなにスゴイ」「チームのコアメンバー」「チームリードがんばった」みたいな。

ぜんぶ書いちゃう
経験2年で「Python/Ruby/R/C#/Java/C/C++/Asssembler/Elixer/Lisp/JavaScript/HTML/CSS/Haskell」とか嘘松乙。気持ちは分かるが。

英語
ネイティブチェックしましょう。特に南米の方・・・！（インド英語の許容度は人によって異なる模様）

その他

致命傷じゃないけどボディーブローのように効いてきます。

いい人アピール
熱心だとか頑張り屋とかチームオリエンテッドだとか求めてないです。

ぜんぶ書いちゃう（２）
「OS:Windows2000/98/NT/95」とかノスタルジックなやつまで。

ぜんぶ書いちゃう（３）
去年までソフト屋でした。今はA社でセールスマンしてます！

ぜんぶ書いちゃう（４）
大学時代にバスケやっててセンターだったとか・・・。

LinkedInとの不整合
レジュメだと「Software Engineer」なのにLinkedInだと「Powertrain Technician」みたいな。

住んでるところ
居住地はあったほうが無難。外国ならなおさら（面接時の旅費とか、ビザとかあるしね）。

レターサイズじゃない
アメリカの企業に提出するなら、サイズはA4でなくレターにしましょう。プリントできなくてイラっとします。

個人ページへのリンク
学生時代に作ったような写真だけの一枚ページとか、無いほうがマシ。クリックしてがっかりしちゃう。

人事が一次チェックするような会社だと、また話が違うのかもしれませんが。

2018-06-12

Codechef June Challenge 2018 参加日記

155位/438人(Div1)だった。もう1問くらい解けそうだったが、期間中にゲームを買ってしまったのが原因でフェードアウト敗退した。

Vision

三次元の座標上に、２つの点PとQ、および球が与えられる。Pは動かないが、Qは一定の速度で動いてゆく。時間tの点Qの位置は次の式で表される(dはベクトル、Q(0)はQの初期位置)。
Q(t) = Q(0) + d*t
はじめ、点QはPから見えないことが保証されている。このとき、点QからPが見えるようになる最小の時間を求めよ。なお、PやQが球に重なることはない。

初期状態は点Qが見えなくて、ある時間tから点Pが見えるようになるのだから、二分探索を使えば求められる。「点Qから点Pが見えるかどうか」は、Q->Pベクトルが球に交差する、と言い換えればよい。あとは初等幾何の問題。
https://www.codechef.com/viewsolution/18726175

Two Flowers

n行m列のグリッドが与えれ、各セルにはタイプa[i,j]の花が咲いている。最大2種類の花を選び、その花のみ咲いている連続するセルを選択するとき、その最大面積を求めよ。上下左右のいずれかでセルが接するとき、その2セルは連続しているとする。
1 <= n, m <= 2000
1 <= a[i, j] <= 4x10^6

本番はむりやり通したが嘘解法。Editorialの貪欲解は、
１）あるセルと、そのセルの右または下のセルを選ぶ
２）その2つのセルにある色のみを選んでBFSしていく
を、すべてのセルに対して行っている。ただし、同じ集合が重複しないように、「現在のセルからある方向に遷移したことがあるか」をもって、もしあるならば無視するようにしている。これは自分の解とほぼ同じなのだが、重複を無視する部分が位置+色組み合わせでHashSetに入れて判断していたため、TLEになってしまっていた。方向だけなら配列で持てるので間に合う。
https://s3.amazonaws.com/codechef_shared/download/Solutions/JUNE18/editorialist/TWOFL.cpp
(Editorial解)

2018-05-23

Codechef May Challenge 2018 参加日記

久しぶりのプロコンは今回からDiv1/2に分かれたCodechef。Div1で344位/633人の結果だった。ていうかDiv2でいいのに・・・。

Dibs on Fibs

サイズMの配列A、Bと整数Nが与えられる。次の最終resultを、10^9+7でModして答えよ。
result := 0
for i := 1 to M
for j := 1 to M
array fib[1..max(2, N)]
fib[1] := A[i]
fib[2] := B[j]
for k := 3 to N
fib[k] := fib[k-1] + fib[k-2]
result := result + fib[N]
1 <= M <= 10^5
1 <= N <= 10^5

いくつか列挙するとパターンが見える。たとえば
A = [ a, b, c ]
B = [ d, e, f ]
だとすると、iが1のときは
a, d, (a+d), (a+2d), (2a+3d), (3a+5d), (5a+8d), ...
a, e, (a+e), (a+2e), (2a+3e), (3a+5e), (5a+ 8e), ...
a, f, (a+e), (a+2e), (2a+3e), (3a+5e), (5a+ 8e), ...
のようになる。つまりAの各要素xについて
x * fib(n-3) * m
が最終回答になり、同様にBの各要素yについては
y * fib(n-2) * m
が回答になる。これを足し合わせればよい。（N<=2のときは別途計算）
https://www.codechef.com/viewsolution/18432901

Fake Binary Search

要素がDistinctな整数列Aが与えられる。Aの要素Xがについて、次のサーチアルゴリズムで正しいXの位置が求められるようにするためには、最小で何回、要素を交換することが必要か。なお数列Aは１つのみだが、クエリはQ回問われる。
integer binary_search(array a, integer n, integer x):
integer low, high, mid
low := 1
high := n
while low ≤ high:
mid := (low + high) / 2
if a[mid] == x:
break
else if a[mid] is less than x:
low := mid+1
else:
high := mid-1
return mid

正しい二分探索経路上で、Xの左と右それぞれについて、
左：Xより大きいもの
右：Xより小さいもの
が交換しなけらばならない要素とわかる。まずこの左右から交換するべきなので、最終回答に左と右の差を加える。
その次に余ったもの（左もしくは右にあるもの）を、有効な要素と交換していけばよい。
有効な候補の有無は、あらかじめAをソートしておけばLowerBound/UpperBoundで効率よく探すことができる。
https://www.codechef.com/viewsolution/18435496

Change the Signs

整数列Aの任意の要素に-1を掛けることができるとき、連続する長さ2以上の部分列が、必ず合計1以上になるようにしたい。最終的な数列の要素の合計を最小化せよ。

本番ではDFS+枝刈りで部分点だった。
よく考えると、ある要素iに注目しているとき、条件が成立するのは
・i-2が正、i-1が正
・i-2が負、i-1が正
・i-2が正、i-1が負
のパターンしかない。上からそれぞれdp_a, dp_b, dp_cとすると
dp_a[i] = min (dp_a[i-1], dp_b[i-1]) + A[i]
dp_b[i] = dp_c[i - 1] + A[i] (A[i] > A[i-1]のとき)
dp_c[i] = min (dp_a[i-1], dp_b[i-1]) - A[i] (A[i-1] > A[i] + A[i-2]のとき）
dp_c[i] = dp_a[i-1] - A[i] (a[i] + a[i-2] >= A[i-1] > A[i] のとき)
と式を立てることができる。
※参考実装
https://www.codechef.com/viewsolution/18500660

2018-04-22

2018年の抱負（改２）

3月に妻が急病になり、ER搬送からの一週間入院という出来事があった（現在はもう問題なし）。それがきっかけで、自身の健康・キャリアついて色々考え直したので、今年の抱負も合わせて更新しておく。

2018年の抱負

一日7時間睡眠
必須科目。どんなに忙しくても6.5時間は寝る。健康は本当に大事

年収~~+15%~~ → +10%
無理しない額に下方修正。睡眠を削ってまで達成しようとしないこと。
糸井重里さんの『ちゃんとメシ食って、風呂入って、寝てる人にはかなわない』を座右の銘とする。
dot.asahi.com

プロコン再開
もともと今年は控えるつもりだったが、熟考の末、日常的な趣味に戻すことにした。理由は
・プロコンをしないと、仕事のプログラミングを家でやってしまうことがわかった。。。
・アルゴリズムが自分の強みらしいとわかった。自分程度でも田舎の普通のプログラマの中だと突出する
・プロコンがないと、トップレベルのコーダーと絡む機会がゼロになることに気づいた
・ABC/ARCへの定期参加にメドがついた
などなど。

2018-03-04

2018年の抱負（改）

2018年が2か月ほど過ぎたところで、今年の抱負を修正することにした。
まあ端的には、「ちゃんと寝る」と「年収増やす」が重すぎて、趣味にとても手が回らいことが判明しただけ。

2018年の抱負
一日7時間睡眠
強化科目。今のところ達成率が6割程度なので、せめて8割まで上げることにする。忙しい日も6時間は寝よう。

年収+15%
3月に昇給したので残り12%くらい。年末の定期昇給が去年と同じ8%と推定するなら、あと2回くらい特別昇給が必要な計算だ。

低レイヤ分野でレジュメにかけるレベルのアウトプットを何か
具体的には30日OS本と熱血アセンブラ本
これは上２つに比べると趣味的要素が強すぎるため、抱負からは外すことにした。

2018-01-22

HackerEarth December Circuits '17 参加日記

2017年最後のプロコン。57位/5713人で風邪を引いていた割には悪くない。長期型プロコンだと、二桁順位がたまに取れるくらいの実力にはなったようだ。

Two Arrays

同じ長さnの整数列X, Yについて、マッチング数を以下のように定義する。
・X[i] = Y[j], (1 <= i, j <= n)となるインデックス(i, j)のペアの数
整数Kと、長さNの整数列A、および長さMの整数列Bが与えられる。AとBから同じ長さの部分列を抜き出し、マッチング数がK以上になるパターン数を答えよ。
1 <= N, M <= 2000
1 <= A[i] <= 1000000000
1 <= B[i] <= 1000000000
1 <= K <= NM

次のような二次元配列を用意する。
table[i, j] = A[i] とB[j]が等しいなら1、それ以外なら0
すると、table[,]の正方形(i, j)～(k, l)は、A[i, k]とB[j, l]でマッチする組み合わせに等しくなる(1の部分がマッチするところ)。
よって、すべてのi,jの組み合わせについて、(i, j)を左上とした正方形をどんどん大きくしていって、中の1の数がK以上になったところから、限界までの正方形の数を足したものが答えとなる。これは累積和と二分探索で効率よく求めることができる。
https://www.hackerearth.com/submission/13789952/

Left or Right

国Xには、0からN-1で番号付けされるN個の都市があり、サイクルのようにつながれている(都市iは、都市(i + 1)%Nと都市(i - 1 + N)%Nとつながっている）。また、各都市にはタイプA[i]がある。次のQ個のクエリに答えよ。
タイプ１：都市YからタイプZの都市まで、左回りで移動したときの最小ステップ数
タイプ２：都市YからタイプZの都市まで、右回りで移動したときの最小ステップ数
たどり着けないときは-1を返すこと。
1 <= N <= 3000
1 <= Q <= 500000
0 <= Y < N
1 <= A[i], Z <= 200000

都市のタイプごとに、位置をリストでもてばよい。それぞれYの位置をLowerBound()で求め、その次または前のIndexとの差分を返す。
https://www.hackerearth.com/submission/13790214/

HP and Splitting of Array

数列Aについて、A[i] > A[j]かつi < jなら、そのペアはinversionである。すべてのinversionであるペアの合計をinversion countと呼ぶ。長さNの整数列Aが与えれたとき、Aを左にiだけローテーションしたときのinversion countを求めよ。iは1からNのすべての数である。
1 <= N <= 100000
1 <= A[i] <= 1000000
Aに重複する要素はない

ある状態Aのinversion countがすでに求められていたとする。Aを左に1つローテーションしたもののinversion countは、
現在の値 - (A[0]の順位 - 1) + (N + A[0]の順位)
となる(『A[0]の順位』はAを昇順ソートしたときの要素A[0]の位置）。
あとは、初期状態のinversion countを求めれば良い。これはBITを使って効率よく求められる。
https://www.hackerearth.com/submission/13828080/

Berland Programming Contests

N個の都市があり、それらをつなぐ道は全体でツリーを構成している。M種類のコンテストが各都市で開催される（１つのコンテストが複数の都市で開催されうる。ある都市では、あるコンテストが開催されないこともある）。ここで、
・連結したサブグラフを選び
・選んだサブセットで開催されるすべてのコンテストタイプに出場する
とする。この時、コンテストタイプの種類数kだけパスを購入しなければならない。
すべてのサブセットについてこのルールを適応したとき、パス数に対するサブセットの数を、すべてのkについて答えよ。
1 <= N <= 5000
1 <= M <= 10

解けそうで解けなかった問題。
dp[i, j] := 根をiとする木で、状態jになるサブグラフ数
と定義する。初期値を
dp[i, (開催されるコンテストマスク)] = 1
として、葉以外のノードについて、
$dp[i, j] = dp[i, j] + \sum_{k\&l=j}^{} dp[i, k] * dp[x, l] \: (xはノードiの直接の子)$
のようにマージしていけば求められる。
計算は次のテクニックを使ってスピードアップできるらしい。
http://codeforces.com/blog/entry/45223（整数列のすべてのサブセットに対して、その合計を効率的に求める方法）

Buggy Bot

ノード数nの有向グラフ上を、Botがk個のインストラクションにそって移動する。インストラクションは、「現在地がノードxならノードyに移動せよ」というものであり、始めBotはノード1にある。ただし、移動中1回のみ、ランダムに隣のノードへBotが移動してしまうことがある。これは、インストラクションの前後いずれでも起こり得る（1度も起こらないこともある）。
このとき、最終到達地点としてありえるノードを答えよ。
1 <= n <= 100000
1 <= m, k <= 100000

本番ではDFS+メモ化で部分点だった。
ランダム変化がない場合の、ステップごとの位置を最初に算出する。そして、「現在のステップで最終的に到達する場所」をノードごとに保持しながら、うしろから処理していく。
（実装は省略）

2018-01-04

2017年振り返りと2018年の抱負

2017の抱負と結果

~~SRMで黄になる~~ → LongContestで二桁安定 (30%)

Topcoderがアレなので途中で変更した抱負。二桁順位は30%くらいの確率なので達成率も30%。

熱で寝込まない (100%)

風邪は引いても寝込んではいない。すばらしい成果。

ちゃんと寝る (20%)

連続で5時間睡眠を何度かやってしまった。

2018年の抱負

一日7時間睡眠

いいかげん睡眠不足になっていい歳じゃない

年収+15%

去年は+8％だったのでかなりアグレッシブ

低レイヤ分野でレジュメにかけるレベルのアウトプットを何か

具体的には30日OS本と熱血アセンブラ本

プロコンはちょっと控えめにする予定。