米国グリーンカードInterview-体験談

※2019/10/22追記: GC郵便で到着(親の分)
※2019/10/23追記: GC郵便で到着(子の分)


2019年9月上旬にGC面接を受けてきた。後続のためメモとしてインターネットに放流しておく。ネット上の記事にはお世話になったしね。

・背景
ソフトウェアエンジニア。雇用主であるローカルの中小企業をスポンサーとしてEB-3で出願。
文系なので、日本の前職からのLetter取り寄せて、学歴相当証明みたいなやつを手配したり(6年以上類似職についてたので可能)、Perm用の文言をひねり出したりするのに苦労した。弁護士は会社紹介の適当な人を使った。妻と子供の分も合わせて申請。
準備を始めたのが2015年、求人広告だのLaborCertificateだのを経て、I-140のSubmitが2016年秋、I-485のSubmitが2018年秋くらいだったかな。長い。

・面接の流れ
ミシガン・デトロイトのUSCISで朝8時からの指定。弁護士も同席してもらったので心強い(かな?)。ちなみに弁護士は15分遅刻し危うく入れないところだった。というか面接官も遅刻したので大丈夫だった。
面接自体は、8:20くらいから50分ほど。面接官は若めの男性だった。ちょっとだけ聴き取りづらい英語だった気もする。
まず最初に指紋と写真をとった。
次に右手を挙げて宣誓。ほんとのことだけ言うよね?と聞かれるので「Yes」と答える。
そしてI-485の項目を一つ一つ口頭で確認された。微妙に申請時と変わってる部分があるので、包み隠さず正直に答える。後半の、「犯罪歴ありますか」「国家転覆を企んでますか」みたいなNoを延々と繰り返す質問も、ちゃんと集中して聴いて答えたほうが良い。最後の一問だけ「Yes」で答える引っ掛け(?)だった。聞きなれない単語も多いので予習したほうが安心。妻も同じように一個一個聞かれた。
最後に追加書類をいろいろ提出。Job Offer Letter、健康診断(I-693)、パスポート写真、最近のPay Stub数回分、出生証明・婚姻証明。
パスポート写真はいちおう裏面に名前を書いておいた。
Job Offer Letterは面接直前に新しいものを作り、ボスにサインしてもらったやつ。
出生証明・婚姻証明は、戸籍抄本+領事館英訳を出したがNGだった。戸籍はフル英訳である必要があるらしい。領事館のやつは「Birth Certificate」等と戸籍の一部をピックアップ訳したやつなのでダメ。あとで再提出のレターが来ることに。
ちなみにTitleが色々な書類でバラバラだった(Software Engineer、Software Developer、Computer Systems Analyst...)。面接官に「これどれも実質一緒の仕事?」と聞かれて、「一緒です」と答えて問題なし。
終始和やかに終了。面接官によると、PriorityDateの関係上、1ヶ月くらいでカードが発行されるとか。9月から新会計年度なので、プロセスが一気に進むよ、と弁護士も面接官も言ってた。

・書類について

  • 健康診断、日本人はBCG打ったので結核が陽性になって要レントゲン…というのは古い情報のようだ。最新の血液検査だと擬陽性なのが分かるらしい。レントゲン受けずに済みました
  • 面接前にRFEが来て、I-485 Supplement Jなる追加書類を出している。要らない気がするのだが…。
  • 面接にはこれまで提出した全書類のコピーを念のため持参した

・その他

  • 子供にもレターが来たので連れて行ったが、12歳未満なので不要だったようだ
  • 長いしとても疲れる。英語つらい。聞きなれない単語も多い(『一夫多妻』とか)ので、通訳雇うのもアリだと思う。ここまでの労力を考えたら微々たる追加費用
  • 弁護士はお守り

今年の抱負の振り返り(1月分)

  • 一日7時間睡眠+ちゃんとメシ

メシはちゃんとバランス良く食えてる。睡眠時間はこんな感じ。
f:id:yambe2002:20190201144011p:plain
悪くないが、油断して6時間とかの日が結構ある。来月は気を付けたい。

  • 5時帰宅+土日は家族と

これは達成率100%。むしろ4:45とかに家に着いてる。

  • 筋トレ続ける

筋トレ5回、プール9回だった。できれば週2で筋トレしたいが、さすがにキツイか?

  • 年収+10%

まだ分からない。

  • LeetCodeのWeeklyで3完安定

LeetCodeは4完x3と2完x1だった。あとはオマケでPrampを一回やった。

  • Kaggleに浸かる

動画とテキストで、合計約17時間ほど過ごした。「浸かる」には程遠い。

  • vocabulary.com を日常的にやる

20分しかやらなかったようだ。反省。

AtCoderで始めるPythonプログラミング入門 - 1

これは、プログラミングコンテストを使ったPythonプログラミング入門です。よくある入門書とちがい、コンテストの問題をどんどん解いていき、必要になったらそのときに、足りない分を勉強する、というやり方をとっています。

プログラミングやPythonの知識がゼロの人、プログラミングは分かるけどコンテストはやったことない人、をターゲットにしています。日本で一番有名なコンテストサイト『AtCoder』と、人気プログラミング言語『Python』を使います。


プログラミングコンテストってなに?
プログラミングの力を競争(きょうそう)するコンテストです。問題が与えられるので、それを解くプログラムを書いて提出します。どれだけ多くの、ちゃんと動くプログラムが提出できたかで、順位が決まります。

いろいろなタイプのものがありますが、よくあるのが
・インターネットで参加する
・1~2週に一回
・1時間半くらい
・5問くらい
・順位やランクがリアルタイムで分かる
・レーティング(強さを表すスコア)がつく
といったものです。


問題1
さて、いきなりですが、実際にコンテストに出された問題を見てみましょう。

ある文章wが入力されます。これの最後に”s”をつけて、出力しなさい。
(AtCoder Beginner Contest 029-A 改)

問題の意味は難しくありませんね。文章wの最後に”s”をつけるプログラムを書けばいいようです。たとえば、wが”cat”なら、”cats”にしてあげればよいのです。しかし、『入力』『出力』とはどういうことでしょうか?これは、言葉で説明するよりも、図にしたほうが分かりやすいでしょう。

f:id:yambe2002:20181220133145p:plain

右の青い四角が、あなたが書くプログラムです。その四角に入ってくる矢印が「入力」(Cat)、その四角から出ていく矢印が「出力」(Cats)になります。ようするに、あなたのプログラムに文章wが入ってくるので、それに"s"を付けて返してよこしなさい、という意味になります。

このように、プログラムに入ってくるもの(データ)を「入力」、プログラムから出ていくもの(データ)を「出力」と呼びます。

ではさっそく、これをやってくれるプログラムを書いてみましょう。まだPythonは勉強していないので、とりあえず日本語でそれっぽく。

文章wが入力される

wの最後に"s"を付ける

wを出力する

できました。あとはこれをPythonに直してあげればよいのです。


Pythonを準備しよう
では次に、パソコンにPythonをインストールしましょう。書いたプログラムがちゃんと動くか確かめるのに必要ですから。

なお、すでにPythonがパソコンにインストールされていたら、この章は飛ばしてもらってかまいません。

※Windowsの場合

まず、ブラウザで https://www.python.org/ にアクセスします。英語のページですが、怖がることはありません。

上のほうにある「Downloads」メニューにマウスを移動させると、「Download for Windows」が出てくるので、それをクリックしてください。
f:id:yambe2002:20181220141608p:plain

「Python-x.x.x.exe」といった名前のファイルがダウンロードされたはずです。それをダブルクリックし、あとは「すべてのユーザー」を選択して「次へ」をクリックしていってください。自動的にPythonのインストールが開始します。もしかしたら、途中で管理者(かんりしゃ)パスワードが要求されるかもしれません。

インストールが終わったら、Windowsの「スタート」メニューに「Python 3.x」があることを確認してください。その中の「IDLE」が、この記事で使うエディタ(プログラムを書くために使うアプリケーション)になります。

※Macの場合

まず、ブラウザで https://www.python.org/ にアクセスします。英語のページですが、怖がることはありません。

上のほうにある「Downloads」メニューにマウスを移動させると、「Download for Mac」が出てくるので、それをクリックしてください。

「Python-x.x.x.mpkg」といった名前のファイルがダウンロードされたはずです。そのなかに、Pythonインストーラーである「Python.mpkg」があるはずなので、それをダブルクリックします。「次へ」をクリックしていくと、自動的にインストールが開始するはずです。

インストールが終わったら、「アプリケーション」フォルダに「Python」があることを確認してください。そこの「IDLE」が、この記事で使うエディタ(プログラムを書くために使うアプリケーション)になります。

※Linuxの場合

ディストリビューションによってインストールのやり方が違うので、ここでの説明は省略します。ごめんなさい。
たとえばUbuntuなら、「ソフトウェアセンター」で「Python」をサーチし、「IDLE(Python 3.x)」を選択してインストールすれば良いはずです。


Pythonで遊んでみよう
Pythonプログラムを書くために、この記事ではデフォルトで付いてくるIDLE(アイドル)というアプリケーションを使います。まずこのIDLEを起動してください。
f:id:yambe2002:20181223143241p:plain
こんな感じの画面が出てきたはずです(たぶん、メニューバーなどは日本語になってると思いますが)。
ここでもうPythonのコードを書くことができます。まずはためしに、Pythonに適当に足し算や引き算をやらせてみましょう。「>>>」の右側にカーソルがあることを確認して、以下のようにキーをたたいてみてください。

>>> 1 + 1 (リターンキー)
2
>>> 5 - 3 (リターンキー)
2
>>> 300 / 3 (リターンキー)
100

どうですか?計算結果が表示されましたか?とても単純ですが、これでも立派なPythonのプログラムコードです。「1+1」のあとにリターンキーを押すと、あなたのパソコンでPythonエンジンが動いて、「1+1」というPythonコードを読んで実行し、その結果が画面に表示されるのです。
なお、Pythonでは掛け算を表すのに「*」、割り算に「/」を使います。電卓がわりに、いろいろやってみてください。


Pythonで遊んでみよう(2)
問題に戻る前に、もう少しだけPythonをさわってみましょう。次のように入れてみてください。

>>> a = 150
>>> b = 200
>>> a + b
350

1行目で「aに150を入れる」、2行目で「bに200を入れる」、3行目で「a+bを計算して表示する」ということをやっています。このaとかbのことを『変数(へんすう)』といいます。
プログラミングは、①データをコンピュータ内のどこかに取っておいて、②それに何かの作業をする、のが基本です。この取っておいた場所のことを『変数(へんすう)』とよび、それの名前をここでは「a」や「b」とつけた、ということです。
また、変数にデータを入れることを、『代入(だいにゅう)する』といいます。

1行目をもっと細かく見ていってみましょう。Pythonエンジンはコードを一字ずつ読んでいって、

a

まで来た時に、『これは変数を作って、それにaと名前を付けるんだな』と理解します。
そして次の

= 150

を見て、『なるほど、それに数字の150を代入するのか』と考えるのです。イコール記号は、右にあるデータを左に代入する、という意味です。
つまり合わせて1行で

a = 150

『変数aを作り、それに数字の150を代入する』という意味になるのです。

もう少し、やってみましょう。

>>> c = 30
>>> d = 40
>>> e = 5
>>> (c + d) * e
350

難しくありませんね。変数cに30、変数dに40、変数eに5を代入して、『(c + d)×e』を計算しています(”*”は掛け算の記号でした)。

>>> g = 50
>>> h = 3
>>> i = g + h
>>> i
53

こんな風に、計算結果を変数に代入することもできます。3行目で、『g+h』の結果を変数iに入れてます。なお、ただ変数名だけをタイプしてリターンキーを押すとその中身が表示されます。

>>> j = 'cat'
>>> k = j + 's'
>>> k
'cats'

数ではないものを扱うこともできます。’で囲んだものは文章として扱われ、これを『文字列(もじれつ)』といいます。文字列と文字列を足すと、二つがつながったものができあがります。
1行目で変数jに文字列'cat'を代入、2行目では変数kに、jと文字列's'をつなげたものを入れてますね。結果は'cats'になっています。

>>> num = 100
>>> str = 'abcde'
>>> num + str
Traceback (most recent call last):
  File "<pyshell#8>", line 1, in <module>
    num + str
TypeError: unsupported operand type(s) for +: 'int' and 'str'

ちなみに数字と文字列と足そうとすると、こんな風にエラーになります。この例だと、numには数字(100)、strは文字列('abcde')を代入しています。三行目でこの2つを足そうとしていますが、当然それは無理なのでエラーになっています。


問題1はPythonでこうなる
さて、では問題1の日本語コードのPython版をお見せします。

# 文章wが入力される
w = input()

# wの最後に's'を付る
w = w + 's'

# wを出力する
print(w)

日本語で説明してあるので、何をやってるコードなのかは分かるでしょう。「問題1」の章で作った日本語のプログラムが、一行ずつそのままPythonのコードになっています。ちなみに「#」で始まっている行はコメントと呼ばれ、Pythonエンジンはこれを無視します。ようするに人間用のメモです。

次に、あなたのパソコンでこのコードを実行してみます。
まずはIDLEの「ファイル」メニューから、「新しいファイル」を選んでください。次のような画面が開いたはずです(日本語だと思いますが)。
f:id:yambe2002:20181223144914p:plain

この画面に、さっきのPythonコードをコピーしてください。
そうしたら「実行」メニューから、「モジュールを実行する」を選んでください。ファイルを保存するように言われるので、てきとうなファイル名を付けてどこかに保存します。すると、こんな画面が開くはずです。
f:id:yambe2002:20181223150318p:plain
分かりにくいですが、これは「wが入力されるのを待っている」状態なのです。ためしに、適当な単語(”cat”など)をタイプしてリターンキーを押してみてください。
f:id:yambe2002:20181223150824p:plain
無事に、"s"が足されて表示されましたね。もしよかったら、何度か実行してみて、どんな単語をいれてもちゃんと動くことを確認してみてください。


AtCoderに提出する
さて、この問題はAtCoderでじっさいに出されたものでした。AtCoderにはむかしの問題もジャッジ(コードが正しいかチェックすること)してくれるすごいサービスがあります。これを使って、このPythonコードが間違いないかジャッジしてもらいましょう。

まず、AtCoder の右上にある「新規登録(しんきとうろく)」からユーザー登録してください。そしてAtCoderにログインし、AtCoder Beginner Contest 029 - AtCoder を開いてください。

これはAtCoder Beginner Contestというビギナー向けコンテストの、第29回のページになります。「問題」をクリックすると、コンテストで出された問題が表示されます(AからDまでの4問)。ここにある「A - 複数形」が「問題1」のもともとの問題です。

「A - 複数形」に行き、下のほうへスクロールすると、「言語」タブと、その下にテキストブロックがあるのが分かると思います。「言語」タブで「Python3」を選択し、テキストブロックへ先ほどのPythonコードをコピーしてください。

f:id:yambe2002:20181223152551p:plain

そうしたら、その下の「提出」ボタンをクリックします。

f:id:yambe2002:20181223152658p:plain

すると、こんな感じの画面に切り替わります。この「WJ...」というのは、いま出したコードをもう少しでジャッジするから、少し待っててね、という意味です。しばらく待つと、結果が下のように「AC」に変るはずです。

f:id:yambe2002:20181223153025p:plain

この「AC」というのが、コードが正しかった、とAtCoderサイトにジャッジされたという意味になります。
(Acceptedの省略です。ほかに「WA」(Wrong Answer:不正解)、「RE」(Runtime Error:実行エラー)などがあります)


問題1のコードのくわしい説明
問題1のコメントを、もっと細かく書くとこうなります。

# 変数wをつくる。そしてユーザーが入力したデータをwに代入する
w = input()

# wの最後に's'を付け、それを変数wに代入する
w = w + 's'

# wを出力する
print(w)

1行目の、

input()

は、『ユーザーからの入力をもらう』という作業をやってくれるものです。
2行目、

w = w + 's'

は、変数wの中身に's'をつけて、さらにそれを同じ変数wに代入しています。
最後の、

print(w)

は、変数wを画面にプリント(表示)しなさい、ということです。画面への表示がプログラムの「出力」になるのは奇妙を思うかもしれませんが、まあそういうものなのだ、と思っておいてください。

これで問題1で学ぶ内容はすべてです。この調子で、どんどん問題を解いていきましょう。


問題2
次の問題はこれです。

大文字のアルファベットが1つ入力されます。このアルファベットは、”A”、”B”、”C"、”D"、”E"のどれかです。”A”から数えて何番目かを出力しなさい。
(AtCoder Beginner Contest 013-A 改)

入力されたアルファベットを、変数cに入れることにしましょう。つまり、
・cが”A”のときは1
・cが”B”のときは2
・cが”C”のときは3
・cが”D”のときは4
・cが”E”のときは5
を出力するプログラムを書けばいいようです。こんな感じでしょうか。

# アルファベットcを入力する
c = input()

cが'A'のとき
    #1を出力
    print (1) 

cが'B'のとき
    #2を出力
    print (2)

cが'C'のとき
    #3を出力
    print (3)

cが'D'のとき
    #4を出力
    print (4)

cが'E'のとき
    #5を出力
    print (5)

「cが〇〇のとき」さえPythonに直せれば大丈夫そうですね。こう書きます。

# cが’A'のとき
if c == 'A':
    #1を出力
    print (1)

「if」は、英語で「もし」という意味です。そのつぎは「c = ’A'」ではなく、「c == 'A'」と、イコール記号が2つになっていることに、注意してください。これで、『cと’A'が同じ』という意味になります。あわせて、『もしcが’A’と同じなら』です。

ぜんぶ書き直すとこうなります。

# アルファベットcを入力する
c = input()

# cが'A'のとき
if c == 'A':
    #1を出力
    print (1)

# cが'B'のとき
if c == 'B':
    #2を出力
    print (2)
    
# cが'C'のとき
if c == 'C':
    #3を出力
    print (3)

# cが'D'のとき
if c == 'D':
    #4を出力
    print (4)

# cが'E'のとき
if c == 'E':
    #5を出力
    print (5)

「問題1」のときと同じように、IDLEで実行してみてください。
(ファイル→新しいファイルに行って、上のコードを張り付けてから、「モジュールを実行」です)
f:id:yambe2002:20181227014439p:plain
うまくいきましたか?この例では「D」を入力しています。ちゃんと「4」が表示されていますね。

そうしたら、またAtCoderにジャッジをお願いしてみましょう。この問題は、AtCoder Beginner Contest 013で出されたものです。

AtCoder Beginner Contest 013 - AtCoder
(ログインを忘れないでください)

「問題」タブをクリックし、「A - A」を選んでください。これが、この問題のもともとの内容です。まえと同じように、「言語」タブから「Python3」を選び、ソースコードを張り付けて「提出」します。
ちゃんと「AC」になればOKです!


問題3
どんどんいきましょう。この問題でもifを使います。

いまの月が1~12で入力されます。来月が何月かを出力してください。
(AtCoder Beginner Contest 011-A 改)

入力された月をmとしましょう。つまり、こういうことでしょうか?

m = input()
print (m + 1)

ちょっと違います。よく考えると、これでは12月のときに、「13」と出力されてしまいますね。正しくはこうです。

m = input()

mが11以下なら
    print (m + 1)
それ以外なら
    print(1)

「mが11以下」というのは、Pythonでは「m <= 11」と書きます。日本語で入力できる「≦」は使えません。「それ以外なら」は「else:」です。ifも使って、合わせてみましょう。

m = input()

if m <= 11:
    print(m + 1)
else:
    print(1)

これで良さそうですかね?いつものように、IDLEで動かしてみましょう。
f:id:yambe2002:20181227042454p:plain
あれ、エラーになってしまいました。なぜでしょうか?

m = input()

じつは、このinput()はユーザーからの入力を「文字列として」扱うのです。そのため、変数mには数字ではなく、文字列(たとえばユーザーが5とタイプしたら文字列としての’5’)が入っています。そのため、次の

if m <= 11:

がエラーになるのです。文字列の’5’と数字の11は比べることができませんからね。このエラーを直したコードがこれです。

m = input()  # mには文字列が入る
m = int(m)   # mを数字(整数)に変かんして、mに入れる

if m <= 11:
    print(m + 1)
else:
    print(1)

このように変数には、数字や文字列などの『タイプ』があります。このタイプを変数の型(かた)といいます。上のコードだと、input()からもらったばかりのデータは「文字列型」で、そのあとにint()したあとのデータは「整数型(せいすうがた。小数点のつかない数)」です。

IDLEで問題なく動くことをチェックしたら、AtCoderにも出してみてください。もともとの問題はこれです。
A - 来月は何月?


問題4

歳が入力されます。七五三でお祝いされる歳なら”YES"、そうでないなら”NO"と出力してください。
(AtCoder Beginner Contest 114-A 改)

入力をaとしましょうか。七五三でお祝いされるのは、7才、5才、3才のときですね。

a = input()
a = int(a)

if a == 7 or a == 5 or a == 3:
    print('YES')
else:
    print('NO')

こうなります。2行目では、前の問題と同じように、入力された文字列データを整数型に変かんしています。

if a == 7 or a == 5 or a == 3:

これで「もしaが7か、aが5か、aが3なら」になります。「or」は英語で「または」という意味ですよ。

IDLEでのチェックと、AtCoderへの提出もやってみてください。こちらです。
A - 753


練習問題
ここまでの知識で解ける問題を集めました。どんどん練習するのが上達のコツです。ぜひ、やってみてください。

日付Dが入力されます。
Dが25なら”Christmas”、Dが24なら”Christmas Eve”、Dが23なら”Christmas Eve Eve”、Dが22なら”Christmas Eve Eve Eve”と出力してください
(AtCoder Beginner Contest 115-A 改)


もともとの問題はこちら:A - Christmas Eve Eve Eve

今日は12月30日です。今の時間Mが入力されたとき、年が明けるまであと何時間あるかを出力してください。
(AtCoder Beginner Contest 094-A 改)
(例1)Mが21のとき→27を出力
12月30日が残り3時間で、12月31日は24時間あります。なので、3+24=27を出力します。
(例2)Mが12のとき→36を出力
12月30日が残り12時間で、12月31日は24時間あります。なので、12+24=36を出力します。


もともとの問題はこちら:A - New Year

AtCoderで始めるPythonプログラミング入門 - 2 に続きます。

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

まず去年の抱負の振り返り。

  • 一日7時間睡眠

達成率70%くらい。9月くらいからはメシにも気を付けていい感じ。

  • 年収+10%

達成率140%!!天才だと思われる。

  • プロコン再開

まあLeetCode毎週でてるし、Long Challengeも参加多いので、再開したといってよい。


2019年の抱負はこちら。なお生活系がキャリア系に優先するものとする。

生活系

  • 一日7時間睡眠+ちゃんとメシ

体を壊すと家族が困る。死守。

  • 5時帰宅+土日は家族と

過去4年ずっと維持してるけど、だいじなので明言しておく。

  • 筋トレ続ける

いまの生活を続ければよいけど、これも明言する。体だいじ。

キャリア系

  • 年収+10%

プロジェクトがアレしてアレすれば+20%も夢ではないはず。

  • LeetCodeのWeeklyで3完安定

ほぼ出来てるが挙げておく。業務・ホワイトボードコーディングではこれで十分でしょ。

  • Kaggleに浸かる

やっと沼に堕ちることを決意しました。具体的なランク的な目標は3月くらいまでに決めます。

  • 英語

就活で足を(あんまり)引っ張らないくらいに英語を伸ばす。具体的には vocabulary.com を日常的にやる。


「Kaggleに浸かる」以外は「日常生活を続ける」に等しいが気にしない。

C#で競技プロするときの部品集

Competitive Programming (2) Advent Calendar 2018の12/25分の記事です。

C#は良い言語なのですが、競技プログラミングには少し(というか色々)足りないものがあります。ここでは、その不足分を埋める個人ライブラリを紹介します。

この記事にあるコードはすべて自由にご利用くださってかまいません。ただ、不具合等があったら報告をいただけると幸いです。

なお、ほとんどが蟻本を参考にして実装されています。

優先キュー

public class PriorityQueue<T> where T : IComparable
{
    private IComparer<T> _comparer = null;
    private int _type = 0;

    private T[] _heap;
    private int _sz = 0;

    private int _count = 0;

    /// <summary>
    /// Priority Queue with custom comparer
    /// </summary>
    public PriorityQueue(IComparer<T> comparer)
    {
        _heap = new T[128];
        _comparer = comparer;
    }

    /// <summary>
    /// Priority queue
    /// </summary>
    /// <param name="type">0: asc, 1:desc</param>
    public PriorityQueue(int type = 0)
    {
        _heap = new T[128];
        _type = type;
    }

    private int Compare(T x, T y)
    {
        if (_comparer != null) return _comparer.Compare(x, y);
        return _type == 0 ? x.CompareTo(y) : y.CompareTo(x);
    }

    public void Push(T x)
    {
        _count++;
        if (_count > _heap.Length)
        {
            var newheap = new T[_heap.Length * 2];
            for (int n = 0; n < _heap.Length; n++) newheap[n] = _heap[n];
            _heap = newheap;
        }

        //node number
        var i = _sz++;

        while (i > 0)
        {
            //parent node number
            var p = (i - 1) / 2;

            if (Compare(_heap[p], x) <= 0) break;

            _heap[i] = _heap[p];
            i = p;
        }

        _heap[i] = x;
    }

    public T Pop()
    {
        _count--;

        T ret = _heap[0];
        T x = _heap[--_sz];

        int i = 0;
        while (i * 2 + 1 < _sz)
        {
            //children
            int a = i * 2 + 1;
            int b = i * 2 + 2;

            if (b < _sz && Compare(_heap[b], _heap[a]) < 0) a = b;

            if (Compare(_heap[a], x) >= 0) break;

            _heap[i] = _heap[a];
            i = a;
        }

        _heap[i] = x;

        return ret;
    }

    public int Count()
    {
        return _count;
    }

    public T Peek()
    {
        return _heap[0];
    }

    public bool Contains(T x)
    {
        for (int i = 0; i < _sz; i++) if (x.Equals(_heap[i])) return true;
        return false;
    }

    public void Clear()
    {
        while (this.Count() > 0) this.Pop();
    }

    public IEnumerator<T> GetEnumerator()
    {
        var ret = new List<T>();

        while (this.Count() > 0)
        {
            ret.Add(this.Pop());
        }

        foreach (var r in ret)
        {
            this.Push(r);
            yield return r;
        }
    }

    public T[] ToArray()
    {
        T[] array = new T[_sz];
        int i = 0;

        foreach (var r in this)
        {
            array[i++] = r;
        }

        return array;
    }
}

まずは定番の優先キュー(ヒープ)です。C#を競プロで使うときの最大の不満がこれといっても過言ではありません。コンストラクタにIComparerを渡したり、最小/最大のどちらで動かすか設定できたりします。Push()、Pop()のほかに、Peek()、Count()、Contains()、Clear()、ToArray()といった便利メソッドも足してあります。

UnionFind

public class UnionFind
{
    private class Node
    {
        public Node Parent { get; set; }
        public int Rank { get; set; }
    }

    private Dictionary<object, Node> _dict = new Dictionary<object, Node>();

    private Node Root(object data)
    {
        if (!_dict.ContainsKey(data))
        {
            var node = new Node();
            _dict.Add(data, node);
            return node;
        }
        else
        {
            var node = _dict[data];
            return Find(node);
        }
    }

    private Node Find(Node node)
    {
        if (node.Parent == null) return node;
        return node.Parent = Find(node.Parent);
    }

    public void Unite(IComparable x, IComparable y)
    {
        var xRoot = Root(x);
        var yRoot = Root(y);
        if (xRoot == yRoot) return;

        if (xRoot.Rank < yRoot.Rank)
        {
            xRoot.Parent = yRoot;
        }
        else
        {
            yRoot.Parent = xRoot;
            if (xRoot.Rank == yRoot.Rank) yRoot.Rank++;
        }
    }

    public bool IsSameGroup(IComparable x, IComparable y)
    {
        return Root(x) == Root(y);
    }
}

つぎはこれも定番のUnionFind。多少速度は犠牲にしていますが、なるべく汎用的に使えるようにIComparableなら何でも受け付けるようにしてます。Unite()のほかに、IsSameGroup()も用意してます。

比較できるタプル(ペア)

public class ComparablePair<T, U> : IComparable where T : IComparable<T>
{
    public readonly T Item1;
    public readonly U Item2;

    public int CompareTo(object obj)
    {
        ComparablePair<T, U> castedObj = (ComparablePair<T, U>)obj;
        return this.Item1.CompareTo(castedObj.Item1);
    }

    public ComparablePair(T t, U u)
    {
        Item1 = t;
        Item2 = u;
    }
}

C#のTupleは比較できないので。まあたまに便利です。

平衡二分探索木

// <summary>
// Self-Balancing Binary Search Tree
// (using Randamized BST)
// </summary>
public class SB_BinarySearchTree<T> where T : IComparable
{
    public class Node
    {
        public T Value;
        public Node LChild;
        public Node RChild;
        public int Count;     //size of the sub tree
                                //            public int Sum;       //sum of the value of the sub tree

        public Node(T v)
        {
            Value = v;
            Count = 1;
            //                Sum = v;
        }
    }

    static Random _rnd = new Random();

    public static int Count(Node t)
    {
        return t == null ? 0 : t.Count;
    }

    //public static int Sum(Node t)
    //{
    //    return t == null ? 0 : t.Sum;
    //}

    static Node Update(Node t)
    {
        t.Count = Count(t.LChild) + Count(t.RChild) + 1;
        //            t.Sum = Sum(t.LChild) + Sum(t.RChild) + t.Value;
        return t;
    }

    public static Node Merge(Node l, Node r)
    {
        if (l == null || r == null) return l == null ? r : l;

        if ((double)Count(l) / (double)(Count(l) + Count(r)) > _rnd.NextDouble())
        //            if ((double)Count(l) / (double)(Count(l) + Count(r)) > 0.5)   //debug
        {
            l.RChild = Merge(l.RChild, r);
            return Update(l);
        }
        else
        {
            r.LChild = Merge(l, r.LChild);
            return Update(r);
        }
    }

    /// <summary>
    /// split as [0, k), [k, n)
    /// </summary>
    public static Tuple<Node, Node> Split(Node t, int k)
    {
        if (t == null) return new Tuple<Node, Node>(null, null);
        if (k <= Count(t.LChild))
        {
            var s = Split(t.LChild, k);
            t.LChild = s.Item2;
            return new Tuple<Node, Node>(s.Item1, Update(t));
        }
        else
        {
            var s = Split(t.RChild, k - Count(t.LChild) - 1);
            t.RChild = s.Item1;
            return new Tuple<Node, Node>(Update(t), s.Item2);
        }
    }

    public static Node Remove(Node t, T v)
    {
        if (Find(t, v) == null) return t;
        return RemoveAt(t, LowerBound(t, v));
    }

    public static Node RemoveAt(Node t, int k)
    {
        var s = Split(t, k);
        var s2 = Split(s.Item2, 1);
        return Merge(s.Item1, s2.Item2);
    }

    public static bool Contains(Node t, T v)
    {
        return Find(t, v) != null;
    }

    public static Node Find(Node t, T v)
    {
        while (t != null)
        {
            var cmp = t.Value.CompareTo(v);
            if (cmp > 0) t = t.LChild;
            else if (cmp < 0) t = t.RChild;
            else break;
        }
        return t;
    }

    public static Node FindByIndex(Node t, int idx)
    {
        if (t == null) return null;

        var currentIdx = Count(t) - Count(t.RChild) - 1;
        while (t != null)
        {
            if (currentIdx == idx) return t;
            if (currentIdx > idx)
            {
                t = t.LChild;
                currentIdx -= (Count(t == null ? null : t.RChild) + 1);
            }
            else
            {
                t = t.RChild;
                currentIdx += (Count(t == null ? null : t.LChild) + 1);
            }
        }

        return null;
    }

    public static int UpperBound(Node t, T v)
    {
        var torg = t;
        if (t == null) return -1;

        var ret = Int32.MaxValue;
        var idx = Count(t) - Count(t.RChild) - 1;
        while (t != null)
        {
            var cmp = t.Value.CompareTo(v);

            if (cmp > 0)
            {
                ret = Math.Min(ret, idx);
                t = t.LChild;
                idx -= (Count(t == null ? null : t.RChild) + 1);
            }
            else if (cmp <= 0)
            {
                t = t.RChild;
                idx += (Count(t == null ? null : t.LChild) + 1);
            }
        }
        return ret == Int32.MaxValue ? Count(torg) : ret;
    }

    public static int LowerBound(Node t, T v)
    {
        var torg = t;
        if (t == null) return -1;

        var idx = Count(t) - Count(t.RChild) - 1;
        var ret = Int32.MaxValue;
        while (t != null)
        {
            var cmp = t.Value.CompareTo(v);
            if (cmp >= 0)
            {
                if (cmp == 0) ret = Math.Min(ret, idx);
                t = t.LChild;
                if (t == null) ret = Math.Min(ret, idx);
                idx -= t == null ? 0 : (Count(t.RChild) + 1);
            }
            else if (cmp < 0)
            {
                t = t.RChild;
                idx += (Count(t == null ? null : t.LChild) + 1);
                if (t == null) return idx;
            }
        }
        return ret == Int32.MaxValue ? Count(torg) : ret;
    }

    public static Node Insert(Node t, T v)
    {
        var ub = LowerBound(t, v);
        return InsertByIdx(t, ub, v);
    }

    static Node InsertByIdx(Node t, int k, T v)
    {
        var s = Split(t, k);
        return Merge(Merge(s.Item1, new Node(v)), s.Item2);
    }

    public static IEnumerable<T> Enumerate(Node t)
    {
        var ret = new List<T>();
        Enumerate(t, ret);
        return ret;
    }

    static void Enumerate(Node t, List<T> ret)
    {
        if (t == null) return;
        Enumerate(t.LChild, ret);
        ret.Add(t.Value);
        Enumerate(t.RChild, ret);
    }

    // debug
    public static int GetDepth(Node t)
    {
        return t == null ? 0 : Math.Max(GetDepth(t.LChild), GetDepth(t.RChild)) + 1;
    }
}

Randomized BSTを使って自動バランスするようにがんばりました。平衡二分探索木です。Insert()のほかに、Remove()、RemoveAt()、Contains()、Find()、UpperBound()、LowerBound()などがあります。
これ単体だとあんまり便利ではないかもしれませんが、次のSetとMultiSetの実装に必要です。

C言語ぽいSetとMultiSet

public class Set<T> where T : IComparable
{
    protected SB_BinarySearchTree<T>.Node _root;

    public T this[int idx] { get { return ElementAt(idx); } }

    public int Count()
    {
        return SB_BinarySearchTree<T>.Count(_root);
    }

    public virtual void Insert(T v)
    {
        if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
        else
        {
            if (SB_BinarySearchTree<T>.Find(_root, v) != null) return;
            _root = SB_BinarySearchTree<T>.Insert(_root, v);
        }
    }

    public void Clear()
    {
        _root = null;
    }

    public void Remove(T v)
    {
        _root = SB_BinarySearchTree<T>.Remove(_root, v);
    }

    public bool Contains(T v)
    {
        return SB_BinarySearchTree<T>.Contains(_root, v);
    }

    public T ElementAt(int k)
    {
        var node = SB_BinarySearchTree<T>.FindByIndex(_root, k);
        if (node == null) throw new IndexOutOfRangeException();
        return node.Value;
    }

    public int Count(T v)
    {
        return SB_BinarySearchTree<T>.UpperBound(_root, v) - SB_BinarySearchTree<T>.LowerBound(_root, v);
    }

    public int LowerBound(T v)
    {
        return SB_BinarySearchTree<T>.LowerBound(_root, v);
    }

    public int UpperBound(T v)
    {
        return SB_BinarySearchTree<T>.UpperBound(_root, v);
    }

    public Tuple<int, int> EqualRange(T v)
    {
        if (!Contains(v)) return new Tuple<int, int>(-1, -1);
        return new Tuple<int, int>(SB_BinarySearchTree<T>.LowerBound(_root, v), SB_BinarySearchTree<T>.UpperBound(_root, v) - 1);
    }

    public List<T> ToList()
    {
        return new List<T>(SB_BinarySearchTree<T>.Enumerate(_root));
    }
}

public class MultiSet<T> : Set<T> where T : IComparable
{
    public override void Insert(T v)
    {
        if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
        else _root = SB_BinarySearchTree<T>.Insert(_root, v);
    }
}

平衡二分探索木を使ったSetとMultiSetです。LowerBound()とUpperBound()があるのが強み(というかそのために作った)。

Deque

public class Deque<T>
{
    T[] buf;
    int offset, count, capacity;
    public int Count { get { return count; } }
    public Deque(int cap) { buf = new T[capacity = cap]; }
    public Deque() { buf = new T[capacity = 16]; }

    // for debug
    public T[] Items
    {
        get
        {
            var a = new T[count];
            for (int i = 0; i < count; i++)
            {
                a[i] = this[i];
            }
            return a;
        }
    }

    public void Init()
    {
        count = 0;
    }

    public T this[int index]
    {
        get { return buf[getIndex(index)]; }
        set { buf[getIndex(index)] = value; }
    }
    private int getIndex(int index)
    {
        if (index >= capacity)
            throw new IndexOutOfRangeException("out of range");
        var ret = index + offset;
        if (ret >= capacity)
            ret -= capacity;
        return ret;
    }
    public void PushFront(T item)
    {
        if (count == capacity) Extend();
        if (--offset < 0) offset += buf.Length;
        buf[offset] = item;
        ++count;
    }
    public T PopFront()
    {
        if (count == 0)
            throw new InvalidOperationException("collection is empty");
        --count;
        var ret = buf[offset++];
        if (offset >= capacity) offset -= capacity;
        return ret;
    }
    public void PushBack(T item)
    {
        if (count == capacity) Extend();
        var id = count++ + offset;
        if (id >= capacity) id -= capacity;
        buf[id] = item;
    }
    public T PopBack()
    {
        if (count == 0)
            throw new InvalidOperationException("collection is empty");
        return buf[getIndex(--count)];
    }
    public void Insert(int index, T item)
    {
        if (index > count) throw new IndexOutOfRangeException();
        this.PushFront(item);
        for (int i = 0; i < index; i++)
            this[i] = this[i + 1];
        this[index] = item;
    }
    public T RemoveAt(int index)
    {
        if (index < 0 || index >= count) throw new IndexOutOfRangeException();
        var ret = this[index];
        for (int i = index; i > 0; i--)
            this[i] = this[i - 1];
        this.PopFront();
        return ret;
    }
    private void Extend()
    {
        T[] newBuffer = new T[capacity << 1];
        if (offset > capacity - count)
        {
            var len = buf.Length - offset;
            Array.Copy(buf, offset, newBuffer, 0, len);
            Array.Copy(buf, 0, newBuffer, len, count - len);
        }
        else Array.Copy(buf, offset, newBuffer, 0, count);
        buf = newBuffer;
        offset = 0;
        capacity <<= 1;
    }
}

ないと稀によく困るデックです。PushFront()、PushBack()、PopFront()、PosBack()、Insert()、RemoveAt()を用意してます。

GCD、ExtGCD

public static Int64 Gcd(Int64 a, Int64 b)
{
    if (a < b)
    {
        var tmp = a;
        a = b;
        b = tmp;
    }
    if (b == 0) return a;
    var p = a > b ? a : b;
    return Gcd(b, p % b);
}

public static Int64 ExtGcd(Int64 a, Int64 b, ref Int64 x, ref Int64 y)
{
    Int64 d = a;
    if (b != 0)
    {
        d = ExtGcd(b, a % b, ref y, ref x);
        y -= (a / b) * x;
    }
    else
    {
        x = 1;
        y = 0;
    }
    return d;
}

これは定番ですね。C#ではなくとも、みんな自前ライブラリで持ってると思われます。

組み合わせ系

// m種類から重複なくn個を選ぶ組み合わせ
public static Int64 GetMcn(int m, int n)
{
    Int64 val;
    if (m < n) return 0;
    n = Math.Min(n, m - n);
    if (n == 0) val = 1;
    else val = GetMcn(m - 1, n - 1) * m / n;
    return val;
}

// m種類から重複なくn個を選んで並べる組み合わせ
public static Int64 GetMpn(int m, int n)
{
    if (n > m) return 0L;
    Int64 ret = m;
    for (int i = 0; i < n - 1; i++)
    {
        ret *= (m - i - 1);
    }
    return ret;
}

// m種類から重複を許してn個を選ぶ組み合わせ(順番は無視)
public static Int64 GetMhn(int m, int n)
{
    return GetMcn(m + n - 1, n);
}

static Int64[] fact = new Int64[500005];
static Int64[] inv = new Int64[500005];

/// <summary>
/// FOR TEST - mCn % p (p should be prime number)
/// </summary>
public static Int64 GetMcn_p_Simple(Int64 m, Int64 n, Int64 p)
{
    // m! / ( n! ( m - n )! )
    return fact[m] * inv[m - n] % p * inv[n] % p;
}

/// <summary>
///  mCn % p (p should be prime number)
///  use Lucas's theorem
///   - need pre-calculation using the mod
/// </summary>
public static Int64 GetMcn_p(Int64 m, Int64 n, Int64 p)
{
    if (!(0 <= n && n <= m)) return 0;
    Int64 ret = 1;
    for (; n > 0; m /= p, n /= p)
    {
        Int64 n0 = m % p, k0 = n % p;
        if (n0 < k0) return 0;
        ret = ret * GetMcn_p_Simple(n0, k0, p);
        ret %= p;
    }
    return ret;
}

/// <summary>
///  mCn % p (p should be prime number)
///  use Lucas's theorem (No pre-calculation needed)
/// </summary>
public static Int64 GetMcn_p_NoPrecalc(int m, int n, int p)
{
    if (p < 2) return GetMcn(m, n);

    var dm1 = m / p;
    var dm2 = m % p;
    var dn1 = n / p;
    var dn2 = n % p;

    if ((dm2 < dn2) || (dm1 < dn1)) return 0;

    return GetMcn(dm1, dn1) * GetMcn(dm2, dn2) % p;
}

public static Int64 ModInv(Int64 a, Int64 m)
{
    Int64 x = 0, y = 0;
    ExtGcd(a, m, ref x, ref y);
    if (x < 0) x += m; //modInv will never be negative
    return x;
}

public static void Precal_FactAndInv(Int64 mod)
{
    fact[0] = 1;
    inv[0] = ModInv(1, mod);

    for (Int64 i = 1; i < 500005; i++)
    {
        fact[i] = (fact[i - 1] * i) % mod;
        inv[i] = ModInv(fact[i], mod);
    }
}

組み合わせ系のライブラリ。これらも、C#でなくともみんな自前で用意してます。いくつかの関数は、Precal_FactAndInv()を呼んでから使ってください。

CodeChef December Challenge 2018 参加日記

ひさびさのロングチャレンジは2完で460位/786人(Div1)。Div1は問題が難しすぎて楽しくない…。

Max and Electrical Panel

ある電子パネルは、xボルト以上の電源につなぐと壊れてしまう。1000コイン与えられるので、次の2オペレーションを使ってxを特定せよ。
・yボルトの電源につなぐ(1コイン)
・壊れたパネルを治す(cコイン)
1 <= x <= 150,000
1 <= c <= 150

二分探索をするだけだが、素直に[l,r)の中央を取っていくと、cが大きい場合に修理費が嵩みコインが足りなくなる。中央ではなく、l+(r-l)/4などの下限に近い値を使えば問題ない。
https://www.codechef.com/viewsolution/21784719


Chef and Interactive XOR

隠れた整数列[a1, a2, ... an]がある。XOR(ai, aj, ak)を何度か問い合わせることで、要素すべての値を確定させよ。ただし、各Indexに対して、3回までしか問い合わせは実行できない。
8 <= n <= 5 x 10^4

要素1からイテレートしていく。
残り要素数が4または8以上のとき、
one = a[i] ^ a[i+1] ^ a[i+2]
two = a[i+1] ^ a[i+2] ^ a[i+3]
three = a[i] ^ a[i+1] ^ a[i+2]
four = a[i] ^ a[i+2] ^ a[i+3]
を取得し、
a[i] = one ^ three ^ four
a[i+1] = one ^ two ^ three
a[i + 2] = one ^ two ^ four
a[i + 3] = two ^ three ^ four
を得ることができる。
残り要素数が5,6,7の場合も同様にパターンを見つけ出す。特に残り7の場合は手作業では難く、別にスクリプトを書いて導出した。
https://www.codechef.com/viewsolution/21865422


Directing Edges

無向グラフを、すべての頂点の入次数が偶数になるように有向グラフ化せよ。
・1 <= N(頂点数), M(辺数) <= 10^5
・グラフは連結している
・重複辺や自己ループは存在しない

まず自明なこととして、条件を満たす有向グラフを作るのは、辺が奇数のときは不可能、辺が偶数のときは必ず可能である。また、もし木であれば、葉からどんどん消していけばよいので簡単である(葉Aからその親B、Bの親からBに方向づける)。
よって、次のようにグラフを木に変換してしまえばよい。
・適当な全域木をつくる
・この木で使われなかった辺を、ダミーノード(葉)を作って繋げてしまう
(実装は省略)
言われてしまえば簡単な問題で、これが解けなかったのは悔しい。

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

タイトルは誇大広告。

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

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

10秒のカベ

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

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

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

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

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

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

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

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

30秒のカベ

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

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

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

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

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

その他

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

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

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

ぜんぶ書いちゃう(3)
去年までソフト屋でした。今はA社でセールスマンしてます!

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

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

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

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

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



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