DPとは何ぞや / 就活の予定について

昨日twitterのつぶやき並みの薄さの記事を書いてしまったので、いまからカルピスの水割りぐらいは目指していきます。

先に就活について、

自分はまだ大学を卒業するまでに2年あるので、2回はgoogleを受けることができる。

一回落ちると、だいたい一年開けて再挑戦祖いてねと言われるみたい。

実力的にまだわからないが、8月くらいに受けてみたいと考えてる。

受けるためにはプログラミングのスキルが評価されるようなES(エントリーシート)を書かなければならない。日本の企業に提出するものとは全然違って、応募する仕事に直接関係するプロジェクトや、実績を列挙する感じらしい。

つまり、アプリを作ったり、ウェブサイトを作ったり、大会で結果を出したりしなければならない。これにまだ手を付けてないから何のめども立ってない。まず情報収集をしないといけないからそこから進めていこう。

他にやってること

インターンにも参加しようと思う。Googleとかのインターンに行きたいけどいまいちわからない。なんかSTEPってのをやってるらしいけど、ほぼ、てかみたところ全員女性だった。男やから参加できるかわからない。誰か知ってたら教えてください。

googleのソフトウェアエンジニアになりたいんだが、何を勉強すればいいのかはっきりわかっていない。こういうことは調べるよりも働いてる人に聞くのが確実かと思い、9日後の近くでやってる企業のインターンに申し込んだ。あまり考えずにぽちっと申し込んだ。

春休みと夏休みは長期インターンに行けたらかなりいい経験ができると思ってるので絶対に行きたい。海外でもオッケー。大手ITのインターンって給料が月50万とか普通にあるらしいね。すごい。

あまりまとまってないけど就活はそんな感じ、行ったら感想書きます。

今日はAtcoder を紹介してくれた友達と問題演習をした。

ABCの138C問題、148のD,Eを解いた。どれもそんなに難しくなかった。

149のD問題について話してると、「DPで解けるやん」って言われたけど、なんじゃそれってなったので教えてもらった。

まだ自分で一回もそれで問題を解いてないしうまく説明できるほどは理解できてないのでわかりやすそうなリンクを載せておく。

qiita.com

このqiitaというサイトには大変お世話になりそう。

動的計画法とかよく思いつくね、考えた人はすごい。

 あと、148のE問題で少し問題が起きた。

atcoder.jp

問題文

$0$ 以上の整数 $n$ に対し、 $f\left(n\right)$ を次のように定義します。

• $f\left(n\right)=1$ ($n<2$ のとき)
• $f\left(n\right)=nf(n-2)$ ($n\ge 2$ のとき)

整数 $N$ が与えられます。$f\left(N\right)$ を $10$ 進法で表記した時に末尾に何個の $0$ が続くかを求めてください。

制約

• $0\le N\le {10}^{18}$

例を見ると簡単やねんけど、N=12やったら、12*10*8*...*2って感じ。

f(12)＝１ですね。

つまり５の数を数えたらいいと思って、こんな感じにした。

え、なんで画像なんって？ほかの人みたいに見えやすい書き方がわからないから。勉強します。

まあ簡単に説明すると、因数分解したとき５が何回出てくるかで考えた。

50で初めて2回出てくる、250で3回出てくるみたいな感じで区切ると、

50までで5+1回、250までで(5+1)＊5+1回とパターンが見えてくる。

あとはNに近い2*5＾nで引き算していくだけ。

うん。もっと単純な解き方もあるよ。でもこれでも全然制限時間内で計算はできる。

しかし！！forループのi=25を24,23,22にすると全部違う答えが出てくる。謎やねー。

E問題でもこのレベルもあるんやな。初めてばかりに人はAtcoder problemsで問題の難易度を見てチャレンジするといいと思うよ。問題の横の円をクリックするとレートが出てくるよ。

あと数問この後に解こうと思ってる。

明日の目標もA10問B10問！！！