GAFAコーディング面接こんな感じでした(システムデザイン編)

前回の続きです。今回はシステムデザイン編。

実体験にもとづいて、なるべく雰囲気を再現しようとしてますが
・問題はすべて自作
・人物、会話等はすべてフィクション
なのでよろしくお願いします。実際の会話はNDAにより公開できません。

同じくらいの難易度の問題を、こんなレベルでやり取りして、最終的にはお祈りされました。


~前回までのあらすじ~
GAFAのコーディング面接1回目を何とか乗り切ったyambe2002だが、休む間もなく次の面接が始まって辛い。


出題
ぼく「………」
面接官「あれ?yambe2002?大丈夫?」
ぼ「…はっ!ごめんちょっとボーっとしちゃった。大丈夫大丈夫。えーと、何だっけ?」
面「あー、分かる分かる!面接の連続で疲れるよねー!ぼくの時もそうだったよ」
ぼ「ははは…」
面「じゃもう一回言うね。ぼくからの問題はね、ミュージシャン名で検索すると、関係するコンサートの情報を表示するWebサイトをデザインしてほしいんだ。開始時間や料金なんかだね」
ぼ「コンサート情報を検索できるサイト…ミュージシャンで検索…」
面「うん」
ぼ「Webサイトのデザインか。えーとえーと、あー」(時間を稼ごうとしてる)
面「…」
ぼ「えー、あ、これはクラスをデザインするのかな。それともシステムデザインかな」
面「システムデザインだね。コードは書かなくてもいいよ」
ぼ「OK。じゃまずは、要件やユースケースを詰める必要があるけど」
面「うん」
ぼ「ちゃんとやるなら、それだけで何時間も使っちゃうよね…」
面「それはそうだよね。まあ部分部分はその都度、それっぽく仮定していいよ。この面談では、システム的な思考ができるかどうか、技術的な議論ができるかを見たいんだ。厳密なデザインは求めてないよ」
ぼ「了解。じゃまずは…」(ホワイトボードを拭きながら)


ユースケースと仮定
ぼ「Webサイトって言ってたね。これはインターネットに公開するサイト?」
面「そうだね」
ぼ「だとユーザーは世界中から訪れる。だれでも使えるの?それとも、ログインさせる?」
面「どうしようかな。簡単のため、誰でも使えるようにしようか」
ぼ「アーティスト名のほかにも音楽ジャンルやコンサート名とかでも検索できるのかな」
面「うーん、アーティスト名だけにしようか。ユーザーのブラウザには、アーティスト名の入力欄と、検索ボタンがあるだけ。検索すると、結果が表示される」
ぼ「結果はコンサート一覧だっけ」
面「そう」
ぼ「コンサート情報から、例えば購入サイトに飛んだり?」
面「本来はそうなるだろうけど、今回は単純にいこう。コンサート一覧が表示されるだけ」
ぼ「了解」
面「よさそう?」
ぼ「ここまでは。それで、コンサートやアーティストの情報は、どこから引っ張るの?だれが入力するの?」
面「そこはOut of scopeでいいよ」
ぼ「じゃWrite用のAPIやサービスは作らないよ。あとはえーとえーと」
面「…」
ぼ「あ、Read/Write比は?Readのほうがずいぶん多いだろうね」
面「うん。1000:1でReadが多いことにしよう」
ぼ「かなりRead Heavyなサービスだね。アクセス件数はどれくらいを想定してる?」
面「月に250万の検索リクエストということにするよ」
ぼ「だと……(筆算して)だいたい1秒に1件くらいか…DBへの書き込みはその1000分の1だからかなり少ないな…」
面「…」
ぼ「あとは何があるかな…Well…」(必死に教科書を思い出そうとしている)
面「……」
ぼ「そうだ!アクセスにはスパイクがあるよね」
面「スパイクというと?」
ぼ「ある時間帯にアクセスが集中したり、ある検索ワードだけリクエストが多かったり」
面「ああ、もちろんそうだね」
ぼ「それに、ヘビーユーザーからのアクセスが極端に多かったり」
面「それもあり得そうだね」
ぼ「そして多分、可用性(Availability)が大事なサービスだね」
面「そう考えていいよ」
ぼ「これくらいあれば次に進めそうかな…」
面「OK?」
ぼ「だと思う。まずハイレベルデザインを書くね。冗長化なんかは随時やるよ(ペンを取る)」


デザイン1
f:id:yambe2002:20200615065759p:plain
ぼ「シンプルにデザインするとこうかな」
面「ふむふむ」
ぼ「念のためもう一度いうけど、これは最低限のハイレベルデザインだよ。これが機能したら、ベンチマーク・ロードテスト・プロファイリングでボトルネックを特定して、Iterativeに改善していくのが良いプラクティスだと思うんだ(本の受け売り)」
面「なるほど。じゃあこのデザインを説明してくれる?」
ぼ「OK。まずはClient。これはエンドユーザーのWebブラウザだね」
面「うん」
ぼ「一応、DNSも書いておいたけど」
面「このサービスのIPアドレスを解決するために必要。それはそうだね」
ぼ「そしてユーザーはサービスを利用するため、Web Serverにアクセスする」
面「Web Serverは何をするの?」
ぼ「えっ?えーと、ユーザーが直接アクセスするサービスで…最終的なHTMLを供給するし…ええとあとはSSLの終端にもなったり…」
面「うん。内部サービスへのRoutingをしたりするのかな。ここにあるRead APIサービスとか」
ぼ「そう!」
面「Read APIを直接、ユーザーにOpenしたらダメなの?」
ぼ「へっ!?そ、それは良いプラクティスじゃないね。えーと、内部のサービスをOpenにするのはセキュリティリスクが高まるし…」
面「ふんふん?」
ぼ「サービスが増えたときに困るし……スケールするのも難しくなる」
面「なるほど。続けて?」
ぼ「う、うん(落ち着け…落ち着け…)。ふう。説明のために、情報の流れをちょっと書き込んでみるね!」


デザイン2
f:id:yambe2002:20200615065813p:plain
ぼ「こうかな。文法は省略してるよ」
面「なるほど。まずこのクゥールはユーザーからのReadリクエストを表してるんだね」
ぼ「く、クゥール?」
面「あれ?違う?ユーザーからのGETかと思ったけど」
ぼ「(クゥール…クゥール…あ、curlか!!)そうそう!」
面「だよね」
ぼ「アーティスト名をクエリにもったGETを表してるよ」
面「それをWebサーバーが受け取る」
ぼ「うん。そしてURLやクエリをもとに、対応するサービスへRoutingしてるね。ここでクエリのクリーンアップもしてる想定」
面「クリーンアップというと?」
ぼ「え、えーと、キーワードの大文字小文字を統一したり…とか」
面「なるほど」
ぼ「(ほっ)そして、この例ではアーティスト名でRead APIに問い合わせをしてる」
面「ふんふん」
ぼ「Read APIは受け取ったアーティスト名で、データベースにSQLで問い合わせてる。ここでは関係データベースを使ったよ」
面「関係データベースにした特別な理由はある?」
ぼ「えっ。えっとKey-ValueストアとかのNoSQLももちろん使えるけど…今回はたぶん…アーティストテーブルとコンサートテーブルみたいなのを持って、JOINして問い合わせするよね。実装が自然かなと思ったんだ」
面「なるほど」
ぼ「データ数も莫大じゃないし…えーと月250万件の、1000分の1だから…」
面「……」
ぼ「厳密に計算するならちゃんとテーブル設計しないといけないけど、アーティスト情報もコンサート情報も数百Kb程度と仮定すると…ええと…」
面「まあ大したことはなさそうだね。せいぜい月に数千件、多くてもGBオーダーも行かないくらい?」
ぼ「うん。もっとちゃんとスキーマ設計したほうがいい?それとも全体のデザインを議論する?」
面「全体の話をしよう。DBにはアーティストとコンサートテーブルがあって、必要な列が定義されてる仮定で」
ぼ「OK。えーと、で、何だっけ」
面「Read APIが関係データベースにクエリを投げたところだよ」
ぼ「そうだそうだ。そしてRead APIはクエリの結果をもとにコンサート一覧を取得し、Web Serverに返す」
面「このJSONだね」
ぼ「そう。そしてWeb Serverが最終的なHTMLを作り、Clientへ送る」
面「なるほど。良さそうだね」


デザイン3
ぼ「まあこれで一通り機能はしそうだけど、色々と問題がある」
面「どんな問題?」
ぼ「まず、冗長化がまったくされていないことだね。どのボックスも単一障害点になってしまってる」
面「そうだね。どうやって解決する?」
ぼ「基本は並列に稼働させることだね。たとえばWeb Serverならいくつかのサーバーを立ち上げる」
面「うんうん」
ぼ「まあ外部に面するWeb Serverが複数あるとDNS設定が面倒になりそうだから、その手前にロードバランサを置くかなぁ…こっちはMaster-slaveフェイルオーバーを使う(カキカキ)」
f:id:yambe2002:20200615065829p:plain
面「いいんじゃないかな。同じことがRead APIやデータベースにも言えそう?」
ぼ「そうだね。Read APIも複数稼働して、その前にロードバランサを置く。データベースは…ちょっと違うけど…」
面「こういった可用性パターン(Availability Pattern)で気を付けることは?」
ぼ「どのサービスも、なるべくステートレスに作ることかなあ。ステートを持つとスケールするのが難しくなるはず。たとえばWeb Serverなら、セッション情報を別のキャッシュに保存するとか」
面「いいね。データベースの可用性を上げるにはどうしたらいい?」
ぼ「たとえばレプリカが使えるね。Master-Slaveレプリカを採用して、Read APIはSlaveからデータを読むとか(カキカキカキカキ)」
f:id:yambe2002:20200615065842p:plain
面「Good!」


デザイン4
面「あ、あと5分もないや。じゃぼくから。さっき君はIterativeに改善するのが良いプラクティスって言ってたよね」
ぼ「う、うん。定期的にベンチマーク、プロファイラを走らせてボトルネックを見つけて改善だね」
面「じゃあそれで、そうだな、Read APIのレイテンシが大きい問題というが発見されたら、どんな解決がある?あ、描かなくていいよ」
ぼ「えーと、たとえばキャッシュを使うってデータベースへのアクセスを減らすとか」
面「具体的には?」
ぼ「そうだね。一例としては、クエリ文字列をKey、結果をValueにしたMapを持つ」
面「なるほど」
ぼ「データベースなら、あとはスキーマを見直すとか、SQLチューニングとか、Federationを導入するとか色々あるね。それこそNoSQLを考えるのもオプション」
面「なるほどなるほど。いいね」
ぼ「(よし、良い感じだ!)キャッシュはアクセスのスパイク対応にもなるし!」
面「OK。じゃ次。このシステムを監視するにはどんな方法が考えられる?」
ぼ「うぇっ!?(やばっ、ぜんぜん勉強してないぞ)えーっと、えーっと、まずその、考えられるのは人力での定期的なチェックだね。えーとSREの人たちが日常的に(だめだこの回答は…!考えろ考えろ…!)」
面「…」
ぼ「えーと、そうだログ!それぞれのサービスが、アクションのたびにログを出力するようにする」
面「そうだね。ログはいつでも有用だね」
ぼ「監視用のサービスを作ってもいい。まああんまり複雑にすると、そっちに手間がかかって本末転倒になりそうだけど」


そして次の面談へ
面「知ってると思うけど、うちの会社もクラウドサービスを展開してるんだ」
ぼ「もちろん知ってるよ!(使ったことないけど…)」
面「うちのクラウドサービスはね、さっき話した監視サービスやデータベースのレプリケーション、サービスの冗長化なんかを解決して…自動化で…AIが…うんぬんかんぬん~~」
面3「(唐突に)やあ!!」
面「やあジョン!紹介するよ、こちらはyambe2002。こちらはジョン。部署Cのプロジェクトマネージャだよ」
ぼ「ナイストゥミ―チュー!」
面3「やあyambe2002。会えて嬉しいよ!」
面「それじゃねyambe2002。Good luck!」
面3「さて、ぼくからは技術じゃなくてBehavioralなことを色々聴きたいんだ。過去のプロジェクトやリーダー経験なんかだね。まずはね…」
ぼ「」(すでに瀕死)


まだまだ続く

GAFAコーディング面接こんな感じでした

このあいだ、GAFA数社のコーディング面接を受けて全落ちしました。後続のため、オンサイト面接がこんな感じだったよ、というのをストーリー風に仕立てて公開します。問題と会話はダミーですが、雰囲気はかなり近くできたと思います。なお実際の会話はすべて英語で、バーチャルでの実施でした。

メイン問題はLeetCodeのNo.1472をもとに作成。
https://leetcode.com/contest/weekly-contest-192/problems/design-browser-history/

ちなみに「ぼく」はIQ+30くらいの設定です。それではどうぞ。


入室と自己紹介
面接官「やあ!わたしはシンディ。会えて嬉しいよ!」
ぼく「こんにちは、シンディ。ぼくはyambe2002。調子はどう?」
面「超いい感じだよ。きみは?」
ぼ「ぼくも超いい感じさ」
面「それはよかった。わたしは部署Aのソフトウェアエンジニアで3年目なんだ。社内ツールを作ってるよ。AI関係のツールで、超クールでExcitingなやつなんだ」
ぼ「それはクールだね」
面「簡単な自己紹介をお願いしていいかな?」
ぼ「うん。ぼくは経験豊富なソフトウェアエンジニアで…〇〇で貢献して…リーダー経験が……」
面「Cool(たぶん聴いてない)。じゃ、問題に入ろうか。わたしからの問題はね…」
ぼ「あ、はい」


出題と質疑
面「Webブラウザの履歴を管理するコードを書いて」
ぼ「Webブラウザの履歴…」
面「そう。Webブラウザってさ、『戻る』ボタンで前のページに戻っていけるでしょ?あれを実現するの。『進む』ボタンもあるから注意して」
ぼ「なるほど。えーと、それはChromeみたいな普通のブラウザだよね。えーとえーと」
面「…」
ぼ「えーと、そうだ、APIとか決まってる?」
面「決まってないよ。好きに決めていいよ」
ぼ「うーん。じゃあ履歴って何を保持したらいい?URLとサイト名、タイムスタンプ?」
面「いい質問だね。ここでは簡単のため、そうだね、サイト名だけにしようか」
ぼ「ならサイト名のリストを持つする感じかな」
面「多分そうだね」
ぼ「えーと、そして、『進む』の時に遷移するサイト名、『戻る』のときに遷移するサイト名を返すAPIが要る」
面「うん。あと新しいサイトに遷移したときも」
ぼ「そうだね。じゃあ内部的には、サイト名の履歴を文字列リストで持って、Indexで現在の位置を管理する感じかな…」
面「それで行けそう?」
ぼ「待って。それで、APIはVisit()、Back()、Forward()でいい?」
面「うん、そうだね。とりあえずAPIはそれで良いよ」
ぼ「OK。あ、Back()やForward()で次に行けないときは、どうする?」
面「それもいい質問だ。そうだね、今のサイト名を返すようにしようか」
ぼ「あと何かあるかな…」
面「…」
ぼ「ブラウザだと、履歴一覧を表示したり、そこからサイトにジャンプしたりできるけど…」
面「あとで必要になるかもね」
ぼ「だよね。速度は…当然すべてO(1)でやらないといけない」
面「速いほうがいいね」
ぼ「あとは、えーと、履歴クリアもあとで付けそうだな。まあこれは簡単か」
面「そうだね」
ぼ「まとめると、履歴は文字列のリストで持ち、現在位置をIndexで管理する。Back()、Forward()が呼ばれたら、Indexをデクリメントかインクリメントする。Visit()のときは、Indexをインクリメントして、そこに新しいサイト名を書き込む」
面「Visit()でリストの長さが足りなかったら?」
ぼ「そのときはリストにAdd()する。あ、リストって可変長の配列のことね」
面「それで良さそう?」
ぼ「うーん、多分…なにかあるかな…」
面「『戻る』を何度かしたあと、新しいサイトを訪れたらどうなる?」
ぼ「ん?……あ、だめだ!そうか、『戻る』『戻る』『訪ねる』『進む』で過去のサイトに飛んでしまう!つまり、Visit()が呼ばれたら、それより後ろの履歴はクリアしないと!」
面「そう!ならどうする?」
ぼ「うーん。変数MaxIndexを足せばいいかな。MaxIndexより大きなIndexは無効。Visit()が呼ばれたら更新する」
面「なるほど。大丈夫そうだね」
ぼ「あとはOKかな?…よし、じゃあコード書いてみるよ(マーカーを手に取る)」


コーディング
ぼ「まずクラス外観はこんな感じかな…(カキカキ)」

public class BrowserHistory {
    public void Visit(string name) { }    
    public string Back() { }    
    public string Forward() { }
}

面「ん?これ何の言語?」
ぼ「C#だよ。ぼくはC#使いなんだ(自己紹介で言ったけど…)」
面「Cool」
ぼ「そして、履歴は文字列のリストで持つよ。名前は_historyでいいか」
面「OK」
ぼ「それと現在位置を表す_indexと、有効な最大Indexを保持する_maxIndexが要るね」

public class BrowserHistory {
    int _index = -1;
    int _maxIndex = -1;
    List<string> _history = new List<string>();

    public void Visit(string name) { }    
    public string Back() { }    
    public string Forward() { }
}

面「なんで_indexを-1で初期化したの?」
ぼ「これは『いまの位置』だから。初めはどこのサイトも表示してないのを想定してる」
面「なるほど」

public class BrowserHistory {
    int _index = -1;
    int _maxIndex = -1;
    List<string> _history = new List<string>();

    public void Visit(string name) { 
        if(_index == _maxIndex)
            _history.Add("");
        _history[++_index] = name;
        _maxIndex = _index;
    }

    public string Back() { 
        if(_index == -1) return "";
        _index = Math.Max(0, _index-1);
        return _history[_index];
    }   

    public string Forward() { 
        if(_maxIndex == -1) return "";
        _index = Math.Min(_maxIndex, _index+1);
        return _history[_index];
    }
}

ぼ「Visit()、Back()、Forward()も書くとこんな感じかな…」
面「Back()、Foward()で履歴がないときはブランクを返すようにしたんだね」
ぼ「そう。ちょっと手動テストしてみるね…。えーと履歴が無いときのBack()、Forward()は大丈夫そうかな…。初回のVisit()で_historyのサイズが1になって…そのあとBack()したら…Forward()は……」
面「大丈夫そう?」
ぼ「うん…たぶん…」
面「じゃいくつか聞くよ」


コードについての質疑1
面「まず、それぞれの関数の計算量を教えて」
ぼ「えーと、Visit()、Back()、Forward()すべてO(1)だね」
面「本当に?」
ぼ「え?……あ!Visit()の最悪ケースがO(N)か!リストのAdd()がO(N)になる場合がある!」
面「そうだね。その場合の問題点は?」
ぼ「まれにVisit()の実行が遅い。しかも、履歴がたまるとどんどん遅くなる」
面「その通り」
ぼ「これは大問題だ…」
面「まあ、一般的な使い方なら大丈夫だろうけどね。これを解決するにはどうする?」
ぼ「うーん、データ構造を変えないとダメな気がする…Doubly Linked ListかDequeueあたりかな…」
面「どうして?」
ぼ「Linked ListもDequeueも追加がO(1)だから。リストじゃなくてこっちを使うべきだったか…」
面「まあ良し悪しだけどね。ところでDequeueだと『戻る』『進む』の実装に困らない?」
ぼ「いや、それは2つDequeueを使えば出来るかな。でもDoubly Linked Listのほうが素直に実装できそう」


コードについての質疑2
面「ところで、仕様追加をしたいんだけど」
ぼ「う、うん」
面「古い履歴は自動で捨てるようにしたい」
ぼ「えーと、古い、っていうのは時間で?それとも何回分前かで?」
面「そうだね。じゃ何回分前かでやろう」
ぼ「LRUキャッシュみたいに?」
面「お、そうそう。じゃ、ついでだから、LRUキャッシュについて説明してくれる?」
ぼ「LRUはLeast Recently Usedのことで、容量が閾値を超えたときに『いちばん訪れてない』キャッシュを捨てていくもの。LinkedListを使った実装が一般的」
面「そうだね。君の実装はリストだけど、それで実現できる?」
ぼ「難しいと思う。たとえば『最小の有効Index』を持てば見た目は実現するけど、これ結局メモリを解放してないので意味がない。メモリ解放するためにリストを作り直すと、こんどは実行時間が遅くなる」
面「わたしもそう思う」
ぼ「うーん、Linked Listで実装したほうがいい?」
面「きみがそうしたほうがいいと思うなら」
ぼ「了解(あ、あと15分しか無いじゃん!!急げ!)」

public class BrowserHistory {
    int THRES = 1000;
    LinkedListNode<string> _current;
    LinkedList<string> _history = new LinkedList<string>();

    public void Visit(string name) { 
        var node = new LinkedListNode<string>(name);
        if(_current?.Next == null)
            _history.AddLast(node);
        else
            _current.Next = node;
        _current = node;

        CheckSize();
    }

    void CheckSize(){
        while(_history.Count > THRES)
            _history.RemoveFirst();
    }

    public string Back() { 
        if(_current == null) return "";
        if(_current.Previous != null) 
            _current = _current.Previous;
        return _current.Value;
    }   

    public string Forward() { 
        if(_current == null) return "";
        if(_current.Next != null) 
            _current = _current.Next;
        return _current.Value;
    }
}

ぼ「で、できたよ…(ぜえぜえ)」
面「OK。ちょっと時間がないから、細かいチェックは省こうか」


コードについての質疑3
面「ああ、あと3分で次の面接が始まっちゃうね。じゃ最後にもう一個だけ聞こうか」
ぼ「」
面「このコードはLeast Recent Usedにしたけど、訪れた時間が古いもの、たとえば1日以上前のものを随時クリアする、ならどう実装する?」
ぼ「えーとえーと、サイト名と合わせて時間も保存して…」
面「うんうん」
ぼ「CheckSize()で、サイズの代わりに現在時との差をチェックすればいい…?」
面「それで問題ない?」
ぼ「……いや、ダメか。『戻る』があるから、古い順にソートされてるとは限らないね」
面「『戻る』『進む』で時間も更新するならそうだね」
ぼ「えーっと、あ、これはSortedDictionaryを使えばできる、かな?」
面「SortedDictionaryっていうのは?」
ぼ「Key-ValueのMapなんだけど、Keyがソートされてるんだ。キーの実装はたしかBalanced-BSTだったと思う。Javaで言うTreeMap」
面「ああ、なるほど」
ぼ「これに、更新時間をキー、値をLinkedListNodeで保存してあげれば。キーの小さいほうから、値を取り出して、1日以上前ならそのNodeを削除する。1日未満ならBreakかな」
面「行けそうだね。もしそうしたら、計算量はどうなる?」
ぼ「Back()、Forward()、Visit()がすべてO(LogN)になる。毎回BSTへの更新が発生するから」
面「それは確実?」
ぼ「…いや、古い履歴がたくさんあると、クリアに時間がかかる場合があるか。極端な話、全部が古いとO(NLogN)かかる」
面「一つ一つ消したらそうだろうね」
ぼ「うーん、キーのBalanced-BSTをうまく作れば二分探索で…いや、ちょっと分からないや」
面「難しいね。もしかしたら、完ぺきじゃないかもしれないけど、CheckSize()で単純にFirst()から日付をチェックするほうがベターかもしれないよ。実装も単純だしね」
ぼ「なるほど…」


次の面接へ
面「ああ、時間がなくなっちゃった。きみのほうから何か質問ある?」
ぼ「えーっとえーっと、(何かひねり出さないと…あれっ、この人名前なんだっけ?)あなたは社内ツールを作ってるんだっけ、AI関連の」
面「そうだよ!これはとてもチャレンジングな仕事で~~機械学習がうんぬんかんぬん~」
面2「(前触れなく)ハロー!」
面「やあマイク!紹介するよ、こちらはマイク。こちらはyambe2002」
面2「会えて嬉しいよyambe2002!僕は部署Bで働いてるバックエンドエンジニアだよ!」
ぼ「やあマイク!」
面2「それじゃ、ここからぼくが引き継ぐね。ありがとうシンディ!」
面「ありがとう。それじゃあねyambe2002。Good Luck!」
面2「じゃあ早速だけど、ぼくからの問題はこれ。ミュージシャン名で検索すると、コンサートや開始時間・料金なんかを表示するWebサイトをデザインしてほしいんだ!近くのコンサートを優先してね。細かい要件はね…」
ぼ「」(すでに疲労困憊)


こんな感じのが4~5連続

つづき

LeetCode Weekly 191 - D (組み合わせ数)

組み合わせ数(確率)を求める問題。苦戦したので解法メモを残しておく。
https://leetcode.com/problems/probability-of-a-two-boxes-having-the-same-number-of-distinct-balls/

色1~kで染められたボールが2n個ある。ランダムにn個ずつ2グループに分けたとき、それぞれのグループにある色の種類数が同じになる確率を求めよ。

1 <= k <= 8
1 <= 各色のボールの数 <= 6

たとえば次の場合、
色1: 2個
色2: 1個
色3: 1個
組み合わせは12通りになる。
[1,1 / 2,3], [1,1 / 3,2], [1,2 / 1,3], [1,2 / 3,1], [1,3 / 1,2], [1,3 / 2,1], [2,1 / 1,3], [2,1 / 3,1], [2,3 / 1,1], [3,1 / 1,2], [3,1 / 2,1], [3,2 / 1,1]
このうち8パターンで、各グループにある色の種類数が同じになる。
[1,2 / 1,3], [1,2 / 3,1], [1,3 / 1,2], [1,3 / 2,1], [2,1 / 1,3], [2,1 / 3,1], [3,1 / 1,2], [3,1 / 2,1]
よって確率は8/12=0.6667。

考え方
順番は無視できる。上の例だと
[1,1 / 2,3], [1,2 / 1,3], [1,3 / 1,2], [2,1 / 1,3], [2,3 / 1,1], [3,1 / 1,2],
[1,2 / 1,3], [1,3 / 1,2], [2,1 / 1,3], [3,1 / 1,2],
で4/6=0.6667。

まず分母は全組み合わせ数なのでnCkで求められる。

次にグループ名をA・Bとしたとき、dp[i, j, k, l]を
i: Aに入っているボールの数
j: Bに入っているボールの数
k: 箱Aの色種数
l: 箱Bの色種数
の組み合わせ数と定義する。

色cのボールがn個あるとすると、x: 0~nについて
dp[i + x, j + n - x, k + 1, l + 1] += dp[i, j, k, l] * nCk(n, x);
と更新していくことができる。

最後にdpテーブルから条件に合うものを合算し、分子が求まる。

コード例は配列ではなくDictionaryを使った。

public class Solution
{
    public double GetProbability(int[] balls)
    {
        var nCk = GetNcks();
        var sum = balls.Sum();

        // 分母。全ボールから半分選ぶパターン数
        var denominator = GetNck(sum, sum / 2);

        // i: 箱Aに入っているボールの数
        // j: 箱Bに入っているボールの数
        // k: 箱Aの色種数
        // l: 箱Bの色種数
        var dp = new Dictionary<(int i, int j, int k, int l), long>();
        dp[(0, 0, 0, 0)] = 1;

        // c: 色の種類
        for (int c = 0; c < balls.Length; c++)
        {
            var newDp = new Dictionary<(int i, int j, int k, int l), long>();

            var n = balls[c];
            for (int x = 0; x <= n; x++)
            {
                // ボールn個からx個、箱Aへ入れる

                foreach(var key in dp.Keys)
                {
                    if (x == 0)
                    {
                        if (!newDp.ContainsKey((key.i, key.j + n, key.k, key.l + 1))) newDp[(key.i, key.j + n, key.k, key.l + 1)] = 0;
                        newDp[(key.i, key.j + n, key.k, key.l + 1)] += dp[key] * nCk[(n, 0)];
                    }
                    else if (x == n)
                    {
                        if (!newDp.ContainsKey((key.i + n, key.j, key.k + 1, key.l))) newDp[(key.i + n, key.j, key.k + 1, key.l)] = 0;
                        newDp[(key.i + n, key.j, key.k + 1, key.l)] += dp[key] * nCk[(n, n)];
                    }
                    else
                    {
                        if (!newDp.ContainsKey((key.i + x, key.j + n - x, key.k + 1, key.l + 1))) newDp[(key.i + x, key.j + n - x, key.k + 1, key.l + 1)] = 0;

                        // 次の状態:箱Aにi+x個、箱Bにj+n-x個、箱Aにk+1種類、箱Bにl+1種類
                        // nからx選ぶパターン数nCxを掛けて足す
                        newDp[(key.i + x, key.j + n - x, key.k + 1, key.l + 1)] += dp[key] * nCk[(n, x)];
                    }
                }
            }
            dp = newDp;
        }

        // 分子。条件を満たす組み合わせを合算
        var numerator = 0L;
        foreach(var key in dp.Keys)
        {
            if (key.Item1 == key.Item2 && key.Item3 == key.Item4)
                numerator += dp[key];
        }

        return (double)numerator / denominator;
    }

    static Dictionary<(int, int), long> GetNcks()
    {
        var ret = new Dictionary<(int, int), long>();

        // max 6 balls in each color
        for(int i=1; i<=6; i++)
        {
            for(int j=0; j<=i; j++)
            {
                ret[(i, j)] = GetNck(i, j);
            }
        }
        return ret;
    }

    public static long GetNck(int n, int k)
    {
        long val;
        if (n < k) return 0;
        k = Math.Min(k, n - k);
        if (k == 0) val = 1;
        else val = GetNck(n - 1, k - 1) * n / k;
        return val;
    }
}

今年の抱負の振り返り

いつの間にか年末になってしまった…。途中で目標が変わってしまったのに抱負をアップデートしてないのは大失敗。

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

睡眠の達成率50~70%くらいか?来年はFitbitでも導入してちゃんとデータを取った方がいいと思われる。ご飯はOK。

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

これは100%の出来。完璧。

  • 筋トレ続ける

7月くらいまではまあまあやってたけど、それ以降がほぼゼロ。達成率は40%てところか。リングフィットを導入したので来年に期待!

  • 年収+10%

+2%の体たらくである

  • LeetCodeのWeeklyで3完安定

Weeklyの参加自体は遠のいているが、出たときで3完を切ることはまずないし、練習でもMedレベルでAC逃すことは無い。よって90%くらいとしよう。

  • Kaggleに浸かる

3月ころに一度浸かってみたのでOK。Kaggleはあんまり得意/好きではない、と分かったのが収穫だね。70%かな。

  • vocabulary.com を日常的にやる

ぜんぜんやっていません。20%。

抱負には上げなかったけど頑張ったこと。

  • 7月:Djangoを一通り勉強して、簡単なWebを作れるようになった
  • 8月以降:LeetCode/AtCoderが継続的に頑張れている
  • AtCoder500点を二周とか、EducationalDP見直しとか、CtCI/LeetCodeほぼ毎日とか

米国グリーンカード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 に続きます。