日記(2022/05/18)
Tabnineの紹介.
Ⅰ.はじめに-皆様,プログラミングは好きですか？この大学にいると様々な場面でコードを書く機会があると思います.その中でエラーがとれず苦しんだ事も多いでしょう.プログラム言語は複雑です.自分もよく間違います.
そんなミスを減らすかもしれないソフトウェアを紹介します.Tabnineです.これはたくさんコードを書く人にとって,とても魅力的な道具となります.本日はTabnineの紹介を致します.
Ⅱ.情報源
Tabnine(https://tabnineblog.wpengine.com/)
Ⅲ.トピックの内容
A.特徴
1.コード補完
Tabnineの大きな特徴は,自分の書いているコードを読み取り,その人がその後にどういったものを書くのかを予測して表示することです.いってしまえばGoogleやYahooといった検索エンジンの予測に近い事をコーディング中にしてくれます.
2.深層学習
入力補完というのは他のソフトウェアにもありました.Tabnineの異なる点はこれをAIによる深層学習で行う点です.200万以上のGitHub上のファイルをベースとして学習しており,その中でよくみられるコードの形を提示してくれます.
3.対応言語
Tabnineは対応する言語が非常に多いです.C/C++,Python,Java,JavaScript,Ruby,Rustなどに対応します.上にあるように多数のケースの深層学習を用いている事で多数の言語への対応を可能としています.授業毎に複数の言語を扱う必要のある電通大生には非常に魅力的でしょう.
B.用途
ここまで書いたらもう言うまでもないでしょう.このソフトウェアは当然,コードを補完するためにあります.
ところでこれはどうして"Tabnine"という名称なのでしょうか？考えてみてください.答えは簡単です.Tabキーを押す事で機能するからです.
画像を見て下さい.このように次に何を打つかを表示してくれます.ここでTabを押す事で,この予測を自動で入力してくれます.
Ⅳ.選ばれた理由
1.コードを速く書きたかった
恥ずかしながら自分はコードを書くのがあまり速くありません.どう書けばいいか,これは正しいのか,様々な部分で悩んでしまいます.それを解消するために環境構築に拘りました.
その中でどういったらエラーを減らせるのかをずっと考えています.タイピングミス,型のミス(char→intにしたりね！),未定義の文字を使う,エラーの原因は様々です.Tabnineを使うと(全てではないものの)これらのエラーの多くを事前に解消できます.深層学習しているコードは,もちろんエラーを吐かないものがそのほとんどである,つまり「正解」を学習しているため,そこから出される予測変換の精度も高いものとなります.実際自分はTabnineを使いだしてから,エラーが大きく減少しています.
2.無料である
通常,Tabnineは月に約15＄払う必要があります.しかし,学生であればこれが無料になります.これが非常に大きいです.無料でコードの補完を管理するソフトウェアはなかなか存在せず,その点で非常にありがたいです.
以上でTabnineの紹介を終了します.これを読んだあなたのコーディング生活に幸あれ！
日記(2022/05/17)
「いい睡眠」とはなんだろうか？2時間寝ただけで元気いっぱい動ける事？それともいつでもどこでも寝られる事？
私は「いい睡眠」とはきちんと程よく長い時間を寝て,身体を休める事にあると考える.理由は3つだ.
まず第一に睡眠時間が短い事は,健康にリスクを与える.例えば,睡眠時間が5時間の群は7時間のそれと比べて,死亡リスクが約1.5倍に増加する事が知られている.これを聞くと,「寝れば寝るほど健康的である.」と考える人がいるかもしれないがそうではない.日常的に9時間以上の睡眠を行った群と5時間の群とでは死亡リスクがどちらも同じくらい高い.世間では過眠よりも不眠の割合が多く,あまり眠れていない人がいるからこそ,寝れば寝るほど良いと思われがちだ.実際はそうではなく,適切な時間寝る事が必要なのだ.
また,睡眠不足,および睡眠過多は思考にも影響を与える.5時間以下及び10時間以上の睡眠とテスト(数学・英語)の結果には負の相関がある事が多数の調査から知られている.この面でも適切な時間寝る事が重要である.
また,いつでもどこでも寝られるというのもいただけない.眠りとはレム睡眠とノンレム睡眠に二分されており,正常な眠りとはレム睡眠を経てノンレム睡眠に移行する.夢とはこのレム睡眠の間に脳が思考を整理している最中に見るものとされている.
ではどこでも寝られるのはなぜであろうか？答えは単純だ.脳が常に睡眠に近い状態となっているからだ.自分では起きていると感じているが,実はそれはレム睡眠の脳内に近い状態となっている.だから目を瞑ると一瞬でノンレム睡眠に移行してしまうのだ.これを「起きている」というのだろうか？
以上をもってきちんと寝る事の重要性を述べた.最近,時間の効率化が随所で叫ばれ,「ショートスリーパー」がもてはやされている.しかしそれは本当に良い事なのだろうか.目先の事にしか注視出来ておらず,長期的な利を失っているのではないか.よく考え,計画性をもって動いてほしいものだ.休む事も大事な行動である.
AtCoder Beginner Contest 038_D_プレゼント
青色の問題.Atcoder版蟻本に掲載されているやつです.何重のマトリョーシカを作れるか.
問題の説明
箱が個あり,それらを入れ子にします.ある箱が,それより縦・横ともに大きいサイズの箱にのみ入れられるとしたとき,最大で何重の入れ子が作成可能か答えよ.
条件
- 縦の長さ
- 横の長さ
考えた事
まず,弱い制約の場合の解法を紹介しよう.の場合,これは分かりやすいDPで実装できる.
={i番目の箱をもっとも外側に入れたときの入れ子の大きさ}]
とすれば,
=max(dp[j]+1)(ただし,j番目の箱はi番目より内側にある)]
として二重ループを書けばよい.計算量はである.
計算量の話から分かるように,この解き方をするとの制約では間に合わない.どうしようか.
話は戻るが,箱Aが箱Bより内側にあるとはどういう状態だろうか.問題の説明にある通り,Aの縦と横の長さがどちらもBより短いという事だ.ではどれがどれかの内側に入るかを一々具に調べあげるべきか.答えはノーだろう.
これがもし1次元,つまり縦の長さの大きい順だけで入れ子を作るならばすごく簡単な問題となるだろう.配列をsortすればいいだけである.*1
今回もそこから発想を膨らませていく.「どちらも」必要なのであるから,まず1つ,絶対に満たされていないといけない条件を潰していく.入れ子に使えそうなものを小さい順に決めてみよう.
まず縦(横でもいい)の長さでsortをかけ,並べていくのが自然であろう.少なくとも縦の長さが逆転する事はあってはならないので,このようにsortをかけて小さい順に並べておく.こうする事で箱をどの順に並べればいいかの指針がつく.
そして横の長さはどうすればいいだろうか.縦に絞って考えれば,sortをした事によって全ての条件を尽くして入れ子が完成している.ここから横の条件を入れて,入れ子にならない箱を取り除いていく.ここでLISの考え方が活きていく.
LISについては蟻本や,
を参照してもらいたい.今回の場合では縦の長さでsortした事によって配列の順番は確定しているのだから,入れ子となる横の長さは増加列となっていればよいと分かるだろう.
つまり,これは縦にsortをかけて配列の順番を固定しておき,そこから横の長さだけ抜き出してLIS問題を解けばいいとなる.
図にするとだいぶ分かりやすいだろう.まず縦で入れ子になるとした場合の順番を決め,次に横でLISを解けばいい.もちろんLISを解くときに箱の順番は入れ替わらないため,縦の条件も崩れない.LISは二分探索で解けるため,計算量はとなり,間に合う.
これで終わりだろうか.残念ながらこれだと上手くいかない時がある.
入力が
5
2 1
3 2
3 7
4 3
5 4
となっているとき,先ほどの方法だと入れ子は3個(2, 1)→(3, 2)→(3, 7)であるが,実際最大となるのは(2,1)→(3, 2)→(4, 3)→(5, 4)の4個である.どうやら縦の長さが同じであるとき,横の長さでLISをしただけでは上手くいかない事が分かる.なぜか.
答えは簡単である.例えば今までと同様に小さい順に入れ子を決めていくとき,
4
2 5
3 3
4 5
6 6
はどの順に入れ子にすればいいか明確であった.第一の優先順位として縦の長さがあるからだ.(2, 5)よりも内側に(3, 3)が来ることがあり得ない事は誰でも分かる.
一方で先程の例だと判断が難しくなる.2つ前の例に加えて(6, 10)があったとしたとき,序列としては(3, 2)が(3, 7)より優先されそうだが,どちらも(6, 10)の内側に来てしまう.入れ子の確定が難しくなる.
これをどう解消しよう.イメージとしては(3, 2)と(3, 7)のどちらも入れられる場合,とりあえず(3, 2)を入れた方が楽に感じるだろう.実はそれが正解なのだ.
つまり,縦の長さが同じであるとき,この問題は区間スケジューリング問題を解く事になる.
選べるもののうち,横の長さが最も小さいものを選んでいけばよいとなる.いわれてみれば当たり前の話で,縦の長さ3で入れられる箱は高々1個しかなく,横の長さでLISを行っているならば,なるだけ小さいものを入れる方が最善であるのは当たり前であろう.縦も同様であったからsortされているのだ.(2, 4)より(4, 4)を優先するケースはほとんどないだろう.
まとめよう.この問題はまず,縦の長さでsortをかけて,全ての縦の長さが異なっているとき,縦の長さを昇順で固定しながら横の長さを用いたLIS問題.縦の長さが同じものが含まれているときは+区間スケジューリング問題となる.理屈の部分の説明はこれで終わりである.
さて,これを実装しよう.ここからもなかなかタフである.縦の長さが同じであるものがないとき,これはLISであるから二分探索を用いて実装する事は上でも説明した.dpテーブルをINFで初期化し,
=長さi+1である,増加部分列の最終要素の最小値]
として,二分探索を用いて更新していけばよい.
vll dp(N + 1, INF);
rep(i, wh.size()) {
*lower_bound(ALL(dp), wh.at(i).second) = wh.at(i).second;
}
問題となるのは区間スケジューリング問題をどのように組み込むかである.ここが大きなポイントである.
最初,自分は縦の長さが同じもののうち,横の長さが最小のものを残せばいいと誤解し,mapを用いて縦と横の長さを管理していた.縦の長さが同じであるとき,CHMINを行い,より小さい方を残す寸法だ.
もちろんこれでは上手くいかない.
6
2 4
3 2
3 6
3 9
4 7
5 12
とあったとき,今の方法では(2, 4)→(4, 7)→(5, 12)の3個となってしまう.また,単純に横の長さでLISしても(3, 2)→(3, 6)→(3, 9)→(5, 12)となり誤った解答である.正解は(2, 4)→(3, 6)→(4, 7)→(5, 12)の順である.
なぜいけないか.区間スケジューリング問題の肝は「選べるもののうち」である.どちらも「選べるもののうち」という条件を無視している.ただいたずらに横の長さが小さいものを使えばいいわけではない.
では「選べるもののうち」はどこで決まるか.結局前の数字で決まってしまう.前に選ばれた箱の数字より大きい横の長さで一番小さいものだ.ではそれを一々探索していっては計算量は恐ろしい事になりそうである.*2
どうしようか.なるべく今までのギミックに組み込んで計算量を落としたい.
ここでLISの動きを見てもらおう.
線めっちゃ歪んでますね.
ともかく,LISを求めるためのdpは上のように動く.ここで大事なのは赤字で書かれた部分.dpの定数の長さを変えずに先端の数字をより小さいものに更新している.これを活かす.
6
2 4
3 2
3 6
3 9
4 7
5 12
と入力されていたとき,(3, 9)→(3, 6)→(3, 2)の順にみれば,横のDPテーブルのINFを消さずに横の長さで「選べるもののうち」,最も小さいものを選べるだろう.
こうする事でDPテーブルが適切なものとなる.「いやいやそれだとDPテーブルが選んだ順に並ばずおかしくならないか？」と気付いた人もいるかもしれない
確かに上だと横の長さでのDPテーブルの遷移は
となり,実際にどの順に入れ子になっているかの復元は不可能となる.しかし,ここで見てもらいたいのは最前の数字である.結局,LISの長さを求める場合において,増加部分列の最先端以外はどうでもいいのである.最先端が正確で,できる限り小さければ,LISの長さは求められる.途中が差し替えられていても構わないのだ.
これが成立する理由はもちろん,縦の長さが同じであるときは横の長さを降順に見ているからである.ここを降順で見る事で,lower_boundによるLISの最先端の要素を出来るだけ小さくするように狙う.
ここまで書けば実装の仕方も想像がつくだろう.縦,横の長さのペアを用意した配列を用意し,縦の長さを昇順に並べたのち,横の長さを降順とすればいい.
縦の長さを昇順に並べる実装にはもちろんsort函数を用いるのだが,これをそのまま使うと(2, 4)→(2, 7)→(2, 11)のように横の長さが短い順,つまり横も昇順となってしまう.
これを解消するテクニックとして,横の長さに-1を予めかけておくというものがある.そうすると,(2, -11)→(2, -7)→(2, -4)となるから,後はもう一度横の長さに-1をかけて,
(2, 11)→(2, 7)→(2, 4)の順にsortする事が出来る.自分はこれが中々思いつかず,30分くらいを費やしました.頭の片隅にでも入れておくといいかと思います.
長くなりましたがここまでお読みいただきありがとうございました.
プログラム
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<long long, long long>;
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
#define ALL(n) begin(n), end(n)
int main() {
ll N;
cin >> N;
vpll wh(N);
rep(i, N) {
cin >> wh.at(i).first >> wh.at(i).second;
wh.at(i).second *= -1;
}
sort(ALL(wh));
rep(i, N) { wh.at(i).second *= -1; }
vll dp(N + 1, INF);
rep(i, wh.size()) {
*lower_bound(ALL(dp), wh.at(i).second) = wh.at(i).second;
}
cout << lower_bound(ALL(dp), INF) - dp.begin() << endl;
}
nikki(2022/05/09)
私はある年代以上の人は家族と暮らすよりも一人暮らしをした方がいいと考えます.理由は3つあります.
まず,住む場所を選べる事です.学校や職場に近い場所,最寄り駅から5分の場所,渋谷の目の前,はたまた少し落ち着いた郊外.あなたは自分のライフスタイルに合わせて好きなように生活できます.もし家族がいたなら,この決断はより難しくなることでしょう.
次に一人暮らしはあなたの自律を助けます.料理,洗濯,掃除,金銭管理,やらなきゃいけない事はいっぱいです.しかし,否が応でもそれらをこなす事は,あなたのタスク管理の能力を上げ,一人で生き抜く力が身につく事でしょう.
加えて,一人暮らしは自由です.これが一番重要でしょう.自由というのはたしかに苦しいものです.しかし,自由を手に入れる事であなたは新しい様々な事にチャレンジできるでしょう.この大学の人ではあまり多くはないかもしれませんが,夜遊びや酒の席で失敗する事もいい経験です.失敗は人を成長させます.家族と暮らしていると,こういった事は止められる事が多く,失敗こそしないものの成長には繋がらない事でしょう.
以上から,私は一人暮らしを推奨します.最初は難しかったりつらかったり人恋しくなる事も多いでしょう.しかし,それらを経験したあなたは,必ず立派な存在となっています.私は一人暮らしを応援しております.頑張って！
日記(2022/05/09)
かつて生物学の分野では群淘汰説が広く用いられてきた.これは生物は種の保存を最優先とし、種の利益となるように動くとされるモデルであった.これは直感的にはそれっぽく聞こえるが複数の問題があった.
まず第一に種の保存で示される種の概念が極めて曖昧である事だ.ここにおける種が群れ全体を指すのか,その生命体全てを指すのかが文脈によって異なっていた.例えばサルについて考えた時,種とはサルの群れの事なのか,サルという生き物全体の事なのかが明瞭でなかった.
また,群淘汰説において自然選択,自然淘汰は種や群れにおいて強く働くとされており,これを上の仮説と合わせると「利他的」な振る舞いを行う個体が多い方が存続しやすいとされている.ここにも誤りがみられる.
「利他的」な集団において,周りを利用して自己の存続だけを目的とする,種の利益でなく個体の利益を優先する「利己的」なものがいたとしよう.当然のことであるが,適応度は後者の方が高い.「利己的」な方が後世に生き残る可能性が高いのである.
とすると自然淘汰によって種の利益のために自己犠牲を行う「利他的」な遺伝子は絶滅する.
仮に集団全てが「利他的」な行動をとる集団であったとしても,上の説明から分かるように,もし"1体"でも「利己的」な行動を取る個体がその集団に移住して来たら,いずれ自然淘汰によって「利他的」な行動をとる遺伝子は滅んでしまう.そして,自然や野生の中で,ある特定の集団を,他の遺伝的形質をもった他の集団から隔離する事はほぼ不可能であり,また仮に出来たとしても,突然変異によって「利己的」行動を取る個体が発生することを排する事が出来ない.
以上の2つの理由から群淘汰説は非現実的なものであり,進化の単位は種ではないという事が広く普及している.事実,多くの動物で種の利益となる「利他的」行動といわれていたものは実際には異なっていた事が知られている.レミングは集団自殺を行わないのだ.
現在,進化の単位として広く普及している説は遺伝子とされている.我々は安易に「種の保存」として人間の行動を説明しようとすると,道を踏み外したり差別に繋がる恐れがある.優生学は正にこの群淘汰からきている.ナチス・ドイツにおいて,ゲルマン人は高潔な存在であったからその"種"の保存のために他の存在(ユダヤ人やロマ)は断種を強いられた.その面においても進化を理解する事は非常に重要である.
