再起関数の作り方
背景
全探索のコードを書く際に，再帰関数を使用する方法がある．再帰関数に関する解説記事は多いが，作り方について納得できる記事がなかった．そのときに，英語記事を読んで，再帰関数の作り方を理解したので共有したいと思う．
1. 再起関数とは
一言でいえば，関数の中に自分自身の呼び出しが含まれている関数．詳細は，他のサイトを参考にしてください．
2. 再起関数を作るフロー
以下のフローで再帰関数を作る.
- 再帰関数で解く問題を決める．
- 解く問題よりワンステップ簡単な問題を考える．
- ワンステップ簡単な問題に対して，自身がこれから作る関数によって解くことができると仮定する．ここで，その関数名をfunとする．
- funからワンステップ簡単な問題の解ができる．その解をsol1とする．
- sol1を用いて，解く問題の解(solとする)を表現する．
解く問題をn個の問題に関する問題とすると，ワンステップ簡単な問題はn-1個に関する問題のイメージ．前文での説明の意味を例題で具体的に示してみる．
※再帰関数をループするためには，一旦自身の関数から抜け出して自身の関数に戻る必要がある．そのため，自身の関数から出る必要があり，さらに，自己の関数内に自己の関数を含む必要がある．また，再起関数のループを終えるよう，例外処理を加える必要もある．
3 例題
問題：文字列を反転する．（ex:abc→cba）
それでは，上記のフローに従って再帰関数を作ってみよう．ある文字列(ex: abc)をstr1と名づける．
- 解く問題：文字列str1を反転する
- ワンステップ簡単な問題：「文字列stringから先頭の１文字を減らした文字列」(これをstr1_remとする)を反転する
- ワンステップ簡単な問題に対して，自身がこれから作る関数によって解くことができると仮定する．その関数名をreverse_stringとしよう．
- ワンステップ簡単な問題に対するreverse_string関数によって得られる解をsol1とする．すなわち，sol1=reverse_string(「文字列stringから先頭の１文字を減らした文字列」)である．
- sol1から，解く問題の解（sol）を表現する．「文字列stringの先頭の文字」をsol1の後ろにつけると，solとなる．数学的に表現すると，sol=sol1+「文字列stringの先頭の文字」 である．
上記をもとに，コードを書いてみる（「2. 再起関数を作るフロー」にある※も考慮してください）．
def reverse_string(str1): if len(str1)<2: return str1 #文字列stringから先頭の１文字を減らした文字列 str1_rem=str1[1:] #str1を反転 sol1=reverse_string(str1_before) #sol1からsolを表現 sol=sol1+str1[0] return sol
上記の結果となる． 短縮すると，
def reverse_string(str1): if len(str1)<2: return str1 return reverse_string(str1[1:])+str1[0]
となる．
3. 感想
日本語の記事がわかりにくい場合は，英語の記事に詳細が書かれていることが多いです．慣れないうちは，上記のフローを文章にしてからコーディングすることをお勧めします．最初は，簡単な例題で練習しましょう．例えば， 配列の要素をすべて表示する問題であったり．
追記
1. 2020/04/07 文章を修正
2. 2020/04/13 pythonのコードを挿入
尺取り法(英語名：Two Pointer Technique)
はじめに(Two Pointer Technique)
尺取り法(英語名：Two Pointer Technique)についての解説記事です．Atcoder ABC130Dの問題で，尺取り法を使わないとテストコードが時間内に終わりません．そこで，尺取り法について学んだので，その内容をシェアしたいと思います．尺取り法の学習には，こちらの英語Web記事を参考にしました．
尺取り法(Two Pointer Technique)とは
1つの配列内の要素同士を比較する際，配列内のある2個の要素を示す「2個のポインタ(Two Pointer)」を使って比較すること．ポインタを使うことで，「要素比較の2回ループ」を「2個のポインタを動かす1回ループ」にすることができ，計算量を減らすことができる．それでは，Atcoder ABC130Dを「2回ループを使用する方法」と「尺取り法」を使う方法で解きます．
例題1
Atcoder ABC130Dの問題 D - Enough Array | AtCoder Beginner Contest 130 | AtCoder
「2回ループを使用」
配列の要素2つをi,jで表現して，2回ループしています．
import java.util.*; public class Main{ public static void main(String[] arg){ Scanner scan =new Scanner(System.in); int n=scan.nextInt(); int k=scan.nextInt(); int[] A=new int[n]; for(int i=0;i<n;i++){ A[i]=scan.nextInt(); } long sum=0; long ans=0; for(int i=0;i<n;i++){ loop:for(int j=i;j<n;j++){ if(j==i) { sum=A[j]; } else{ sum=sum+A[j]; } if(sum>=k) { ans=ans+n-j; break loop; } } } System.out.print(ans); } }
「尺取り法」
条件を満足する最小の和を持つ部分配列の，左と右の要素をpoint1,2でそれぞれ表現しています．
import java.util.*; import java.lang.*; import java.io.*; public class ABC130D_2{ public static void main(String[] arg){ Scanner scan =new Scanner(System.in); int n=scan.nextInt(); long k=scan.nextLong(); long[] A=new long[n]; for(int i=0;i<n;i++){ A[i]=scan.nextLong(); } long sum=0; long ans=0; int point2=0; for(int point1=0;point1<n;point1++){ while(sum<k){ if(point2==n) break; else{ sum+=A[point2]; point2++; } } if(sum<k) break; ans+=n-point2+1; sum-=A[point1]; } System.out.print(ans); } }
おわりに
例題を追加していきたいと思います．
食生活改善例②
朝食
プロテイン20ｇ 72kcal
オートミール40g 145kcal
ココアパウダー6g 16kcal
豆乳200ml 108kcal
バナナ1本 77kcal
80%カカオチョコ2個 55kcal
計473kcal
昼食
オクラ4本 13kcal
プチトマト4個 12kcal
苦瓜2ピース 17kcal
人参4切れ 10kcal
卵2個 180kcal
鶏胸肉100g 100kcal
鯖缶orシャケ缶 220kcal
計552kcal
間食
プロテイン40g 144kcal
コーヒー３杯 24kcal
計168kcal
夕食
オクラ4本 13kcal
プチトマト4個 12kcal
苦瓜2ピース 17kcal
人参4切れ 10kcal
卵2個 180kcal
鶏胸肉100g 100kcal
鯖缶orシャケ缶 220kcal
納豆1個 100kcal
キムチ50g 23kcal
プロテイン20g 72kcal
計747kcal
1日摂取カロリー
1940kcal
食生活改善例①
朝食
- 鶏胸肉 200g 200kcal
- プチトマト 4個 12kal
- オクラ 4本 13kcal
- ブロッコリー 1/2房 33kcal
- 人参 1/4本 10kcal
- バナナ 1本 77kcal
- 牛乳 100ml 70kcal
計415kcal
昼食
- 鶏胸肉 200g 200kcal
- プチトマト 4個 12kal
- オクラ 4本 13kcal
- ブロッコリー 1/2房 33kcal
- 人参 1/4本 10kcal
- ゆで卵 1個 90kcal
- おにぎり 1個 200kcal
計558kcal
間食
- ゆで卵1個 90kcal
- プロテイン20g 3回 216kcal
計306kcal
夕食
自由に（700kcalをめど）
一日摂取カロリー1979kcal
ボストンキャリアフォーラムに行けなかった話
反省を込めて，記事にする．
タイトル通り，2018年のボスキャリに行けなかった．
原因は，USA渡航には中国パスポート（ビザ付き）の有効期限が６か月以上必要で，僕のパスポートの有効期限が足りなかったため．
空港に出向き，上記の理由で航空会社から搭乗拒否された．
空港会社と交渉（USA到着後に，自身でUSAイミグレと交渉するので飛行機に乗りたい旨）したものの，有効期限が足らないパスポートの人を乗せると航空会社にUSA政府から罰金・罰則があるため，搭乗できないとのこと．
以下，そのあとしたこと．
- ほかの航空会社で載せてくれるところを調査．→中国の航空会社だと載せてくれる可能性があることをネットで検索．問い合わせるも不可とのこと．
- 家に戻り，ボスキャリで面談予定だった会社にボスキャリに参加できない・日本での選考希望を連絡．
- 日本選考が可能との旨を受ける．
海外渡航には，事前の準備が必要であることを痛感．
ビザを持っていても，中国パスポートは有効期限にも注意しなければならない．
日本選考を可能にしてくれたか会社に感謝．
→国内選考の結果がわかりしだい，報告したい．
電気系の学生がサポーターズ「エンジニア学生1on1面談会」に参加してみた．
サポーターズ「エンジニア学生1on1面談会」に参加したので，その時の様子をまとめてみる．
はじめに
サポーターズ主催の「エンジニア学生1on1面談会」は主に情報系の学生向けの就活イベント．参加企業は，某ユニコーン会社やベンチャー企業などいろいろ．電気系の学生が参加したので感想を述べてみる．
概要
情報系の就活イベントで，学生が企業と1on1で面談．
以下が流れ，
各企業の紹介→企業の担当者と個人面談（1on1 or 1on2）25分を計8回→懇親会→企業による評価のフィードバック（メールで）
企業との個人面談では，学生が自分の制作物をプレゼンする．
準備
制作物を動かしながら説明したほうがわかりやすいという戦略のもとプレゼン作成．見せられるような制作物がなかったため，制作物（CPUとGPUの計算時間を比較するGUIベースのソフトウェア）を１から作成．「自己紹介（自己アピール）→今日の目的（インターンシップに参加したい）と企業に求めること→これまでの制作物の一覧（自分の能力を示せるように）→その中の一つの制作物を動かして説明（能力が本当であることを証明）→熱意をしめす」の流れでプレゼンを作成した（制作物をアップするかも）．
当日
自分のパソコンでプレゼン．１回の面談は２５分と長く，自分から企業に質問する時間があるので，企業の紹介の時に質問を考えたほうが吉．懇親会では，エンジニアの人に内情を教えてもらったり連絡先を交換した（最後までいるの大事）．
企業からのフィードバック
個人面談の数日後，メールで企業からの評価が来た．
以下8社からの評価結果（各会社が以下の４つからよかったのを１つ選ぶ），
技術力: 1
コミュニケーション: 1
思考力: 2
意志・意欲: 4
実際に制作物を動かす，熱意を見せることが企業にとってはよかったみたい．自分の研究と関係するGPUに関するソフトウェアを実演したが，web系の制作物を作ったほうが受けはもっとよい，制作物を公開せよとの指摘をもらった．
感想・反省点
学生からプレゼンしたほうが企業も評価しやすいはず．このような逆求人のイベントにまた参加したい．企業への質問では，難しい質問をしてしまったことは反省．プレゼンが得意な人，インターンシップを探している人に，このイベントを強く推奨する．
