ぺんぎんさんのおうち

日記です。たまに日記じゃないこともあります。

ドイツ生活125日目(01.07.2017)

Diary

5^3日目です. 2017年下半期が始まりました. 

この半年でどれだけ成長できるか, 頑張っていきたいと思います.

友人に吉報があったり, なんか色々と嬉しい報告が入って来てるので, それを糧に頑張れそうな気がします.

 

今日は久しぶりにAtCorder参加しました(Beginnerだけど).

CTFの方はKeine ahnungです.

 

そもそもドイツ生活[0-9]+日目って, その日勉強した内容とかを纏めるために始めてたはずなんですけど, いつの間にツイート貼り付けるだけの日記になったんでしょうかね.

学びがないからなのかもしれませんが..

 

はい. 今日も起床失敗.

起きた時にもう1日の半分が終わってた時の絶望感.

 

いました.

 

A

パパッとすぐに終わりました. 組み合わせ考えるよりも, 合計から一番大きい値引くだけの方が早いですね. (最初勘違いしてて最小値引いてた).

最近アルゴリズムの本で勉強してるのでCで書きました.

 

B

与えられた文字列を末尾消しながら前半部分と後半部分に分けて比較するだけなのでパパパパパっと終わりました(嘘). 

C言語の文字列いじるのにはあまり詳しくないのでPythonで書きました(意味がない)(勉強にならない)(スライス便利).

律儀に1文字ずつ消してたんですけど, 今考えれば文字数が偶数なのは自明なので2文字ずつでよかったですね. 

 

C

Cでどうやってやるんだっけ..って悩んだので(いちいち入れ替えてたらCだとしても時間かかりそうという気付きはあった), Pythonで安直にappendからのreverseしてました(アホ). 当然TLEですよ.

まあいいや！w と投げ出してDへ..

後から解説読んであぁ〜〜ってなってました.

配列を大きめに確保して, 真ん中あたりでleft, rightで領域指定は思い浮かびませんでした(本で読んだはず).

そのために要素数よりも大きい数字で配列確保するのか〜という知見がありました.

 

D

"組み合わせnCrで, 重複する数字が1つあるからその通り数?を引けばいい"

まではわかりましたがそれ以降がダメでした. 

数学弱者辛い.

 

 

6,70分くらいやって買い物行きました(逃げたわけではない).

雨降ってましたが, ずっと引きこもってるのも体に悪いので..

 

聞かれても変なのがいる..くらいにしか思われないので被害は小さいです.

 

新しく日本で発売されたの黄色でしたっけ.

この写真の色は多分まだ売ってないと思うのでお土産にします.

 

僕だけになりました. 食糧全部くれました.

消費できなくて困ってます.

 

 聞き間違いじゃなかったです.

Hamelnに行って来ます. 博物館はまた来週..

 

では.

ドイツ生活124日目(30.06.2017)

Diary

124日目です. いよいよ7月ですね.  もうすぐ帰ります.

 

今日も1日ニートでした. 本読んでました.

明日こそは出掛けたいのと, 今頭痛いので軽くまとめて終わりにします.

 

 

読んだ内容だけ..

クイックソートと計数ソートです.

 

クイックソートはある要素よりも小さい領域と大きい領域に分けて, 分かれた領域内のある要素より~~を続けるソートです.

ある要素をどこにするかが肝になってる(って習った覚えがある)ので, 単純に中央値にしてしまうと最悪計算量になってしまう可能性があります. (最悪計算量になる要因これじゃなかったような.)

要はパーティションの再帰ですね. パーティションは配列の最後の要素を基準に取ります. 実際にクイックソートを書いてるとパーティションの再帰で実装した方がシンプルに書けました. 

 

次に計数ソートは, ソートしたい配列のそれぞれの要素より小さい数字の個数をカウントし(カウンタ配列を作る), 出力する配列に後ろから順に配置していくだけです.

簡単な話, "10"より小さい数字が"4つ"あるなら, "10"は"5番目"に配置されるということです.

 

順に読み進めてると, やはりありました. C++でSTLとして既に実装されているソート関数.

Pythonもそうですが, 標準でソートが実装されてると楽なんですがどういう風に動いているのか知りたいならちゃんと勉強する必要がありますね.

sorted(dict.items(), key = lambda x : x[1]) 

みたいなのも知ってるとスマートですが, 自分で実装してみるのも楽しいです.

明日はAtcoderですよね..? 時間的に出先なので参加できませんが, どんどんやって行きたいと思います. せっかく勉強してるので.

 

では. 

 

 

ドイツ生活123日目(29.06.2017)

Diary

123日目です. キリがいいですね(いいのか?).

 

今日は一日中部屋で本読んでました.

アウトプットの為に最後にまとめます.

 

 

いつも通り, 起床失敗.

 

今日先行上映あったみたいですね. 帰国が楽しみです. ほんとに.

6巻もOVAも家に届いてるので早くNEW GAME!したい.

 

もう3年ほどですかね. Vimを使い続けてますよ(vimrcには拘ってません).

emacsが嫌いというわけではありませんが, "Ctrl + z" は死んで欲しいですね. 

死ね死ね死ね

 

そろそろ帰国日が迫って来た(n回目)ので色々と準備し始めました.

空港からのバスのチケットも取れました. 問題は飛行機の遅延がどうなるか.

 

実はもう公開してあるんですけど, 誰にも気づかれてないですね. HAHA

 

 

-以下まとめ-

何読んでるかは, 既読者ならわかるかもしれませんね.

今日読み進めたのは, 大きく分けると

  • 探索
  • データ構造
  • 再帰/分割統治法

です(順不同).

 

データ構造はstackとかqueueとかですね. 多少の知識はありますが, 本当の基礎からやってるのでじっくり読んでます.

C++のSTL使うとFIFOとか知ってれば使える(?)はずですが, 自分で実装するときどうするかみたいなのも知見として得られたのでよかったです.

スタックの場合は index-0 を 常に空けておくことで[head, tail]を[0, 1]にもどすだけで初期化できるとか, 

キューではリング構造にすることでオーダーをO(1)にする とかですかね.

配列の長さ以上になりそうな時に, 次の参照先を (tail + 1) % LEN にすることで if文を書かずに済むというのもおお〜という感じで.

今までの僕なら普通にif文で tail と LEN 比較でやってたと思うので.

 

探索は2分探索と線形探索です.

線形探索は順番に見ていくだけですが, 最後に番兵を置くことで比較を減らせるテクニックがあるということくらいでしょうか. while(1)でも必ず見つかることが保証されてるので, 見つかった値を返してそれを呼び出し元で比較すれば発見できたかどうかわかるわけで. 一回一回比較してたらアですからね.

 

2分探索はソートされていることが前提条件ですが, LinearSearchと比べて計算量が少ないのでいいですね.

2分探索そのものはそこまで難しくはないんですが, 実際にこれを適用してる問題にびっくりしました. この問題で2分探索使えるのか!? と.

 

最後に再帰ですが, ある関数が内部でその関数を呼び出すアレです.

例として階乗を計算する関数が挙げられてましたが(わかりやすいのかな), スタックに積まれる引数考えるとfor文で計算した方が現実的なんでしょうか.

スタックを考慮しないといけない数字になる前にオーバーフローしそうですけど.

 

ExhaustiveSearch(いわゆる全探索, 力任せ法?)は, 

ある数列を2つ与えて, 数列1の数字の組み合わせで数列2の数字はつくれるかどうか, という問題でした.

数字1つに対して含める含めないしかないので, 通り数は2^nになりますがこの問題ではnはそこまで大きな数字ではないので再帰で全探索するというわけですね.

この問題では作れるかどうかしか出力しないので, どの組み合わせになるかはわからないんですね. スタック使っての応用が期待できそうです.

 

もう1問の再帰は KochCurveと呼ばれるものを作成して, 各頂点の座標を出力するというもので, これ自体は再帰するだけですが, 座標の計算にベクトル計算が出てくるので久しぶりにやってました. それだけ.

 

余談ですが, 

"I'm exhausted"というとクソ疲れたみたいな意味になるんですが,

exhaustiedは消耗したとかそういう意味なんですね.

Exhaustiveは網羅的という意味でした(Google翻訳). 網羅的探索, つまり全探索ですね.

 

はい終わり.

明日はPanzer vorするぞ〜(頑張る)

ドイツ生活122日目(28.06.2017)

Diary

122日目です.

今日はロボカップの作業のために学校へ行きましたが, 不運なことにアレになってしまったので来週まで進捗を産むことができなくなりました.

 

 相変わらず起床失敗.

 

夏休みですからね. やはり帰る人も多いようで.

食べきれないから, と食糧たくさんくれたのは嬉しかったです. 食費が浮きますね..

 

かわいい.

 

やってるかもしれません.

 

問題に寄らず, 

gdb /lib/i386.*/

gdb $ p/x &write 

みたいな感じでいけるっぽい??

 

write-upで書かれてるのは大抵, 判ってて当たり前みたいになってたので初心者には辛い.

関係ないですが村人Bも頑張って進めてます.

 

友人と行って来ます. ルームメイトもそうですが, 僕はまだあと半年ドイツにいますが他の友人はもうあと数週間でお別れって考えると寂しく思えますね.

思い出作りの時間.

 

 

明日こそはパンツァーフォーしてきます.

では.

ドイツ生活121日目(27.06.2017)

Diary

121日目です.

11^2日ですよ. キリがいいですね.

 

今日も起床失敗.

 

冬は特に, 旅行の予定とか立てないと本当に暇になりそうです.

 

こっちで単位とってもあまり意味を為さないんですけどね.

 

教えてもらいました. この後早速使いました.

 

今日のタスク. 使いこなせないキーボードで慣れてないエディタは辛い.

 

 

やることリストみたいなものに追加されました.

が, 実際Dockerで何やるのってところで停滞するのでよくないですね.

 

 

帰国までのカウントダウン, もう既に1ヶ月切ってますからね..

では.