ユークリッドの互除法
はじめに
競プロをやってると、2つの自然数の最大公約数を求める問題が出てくる。
その時に使うのがユークリッドの互除法という手法。
ユークリッドの互除法がなぜ成り立つのか考えたのをまとめる。
（厳密な証明ではなく、ユークリッドの互除法がなぜ成立するかがなんとなく分かることを目標に書いているので証明が知りたい方はブラウザバックを推奨します）
ユークリッドの互除法とは
自然数 があるとき、
（式1）
（式2）
（式3）
という処理を余りが0になるまで繰り返した時の最後の商が最大公約数というものである。
例
(問題) 1071 と 1029 の最大公約数を求める。
1071 を 1029 で割った余りは 42
1029 を 42 で割った余りは 21
42 を 21 で割った余りは 0
よって、最大公約数は21である。
考察
式1において考える。
の最大公約数を
とすると、式1は
と変換できる（これは自明）。
すなわち、全ての項は の倍数である。
上記の式1つ1つを1ステップとすると、 1ステップ毎に割る数と割られる数（式1におけるbとa）を小さくしてくと 最終的に余りが0になり、最小公倍数が求められる。
（考察の部分がかなりざっくりなのであとでちゃんと調べます。）
「未来と芸術展」に行ってきた
はじめに
2020/2/8に森美術館で開催されていた「未来と芸術展」に行ってきました。
学び・感想を書き残しておきます。
学び・感想
この展示会は未来の生活のあり方を提案した作品が展示されていて、ワクワクするものから理解が難しいものまでありました。
箇条書きで書きます。
感想は「🤔」マークをつけます
間違い・解釈の齟齬などがあったら指摘してほしいです。
AI美空ひばり
- 🤔実写だと言われても信じるレベルのクオリティだった
- 🤔声や動きが自然すぎる
OCEANIX CITY
- 一ヶ所で生活の全て（衣食住、仕事、娯楽、エネルギー）が賄えることが持続可能な都市に必要
- シンガポールで構想を練って実験などを行っている
- 🤔分散型社会（村や町）→集中型社会（国）→分散型社会 （OCEANIX CITY）というように回帰している
- 🤔実現できたらどこにでもこのシステムを作って暮らせそう
ポロシティ
- 現代の建物は閉鎖的
- 開かれた空間を作るにはどうしたら良いか
- 自然に委ねる
- そのための建物の形をレゴで模索
- 🤔自然と調和した建物を作ろうとしているという解釈
ティンバーインターフェース
- 変化に柔軟に対応するためにルーズな仕組みが必要
- 軽くて動かしやすい紙や木材で建築を行う
- 🤔今のままでは強度などの問題で難しそう
湿度によって曲がる素材
- 雨の日は閉まって晴れの日は開くとかできる
- エネルギー要らず
- 曲がりやすさも調整できる
- 🤔この素材を使って発電とかできないかな（大した量にはならなさそう）
トップダウンではなくボトムアップの建築
- 住人の隠れた要望を解析
- そのための機械が必要
- 🤔建築後も感情によって柔軟に形を変えることができたら良さそう
その他
- 未来都市で重要なのは造形ではなくシステム
- コンピュータに計算させて建築
- ドローンが建築
- 先の道が見える車
- 菌糸類を型に入れて家具の形にする
- 勝手に増えるからコスパが良い
- スムーズな義足で機械と身体の境界があいまいになる
- 微生物のDNAに音楽を保存する
- 看取りロボット
- 親が3人以上いる子供
終わりに
RIGOLETTOのハンバーガー美味しかった
Pythonでint型から特定のbitを取り出す
はじめに
このような問題で、スイッチのON/OFFの組み合わせを全探索する時にint型から一つのbitの値を取り出したい。
前提
例
- ON = 1
- OFF = 0
スイッチが3つあるとする
は
である。
これをスイッチの状態に見立てると上位bit（左）から、（ON, OFF, ON）として使用できる。
これに対して条件が通っているか判定する関数を書き、for文で0~7を回せば全通りのスイッチの状態を調べることができる
実装
の桁を取り出したい場合
>>> bin(5) '0b101' # 2進数表記 >>> 5 & 1 << 2 4 # 欲しいbit取り出せた >>> 5 & 1 << 2 == 1 << 2 True # 取り出したbitが1だったらTrue, そうでなければFalse >>> int(5 & 1 << 2 == 1 << 2) 1 # int型に変換
for文で回す場合（右側が上位bitになっているので注意）
>>> n=3 >>> for k in range(2**n): ... s = [] ... for i in range(n): ... s.append( int(k & 1<<i == 1<<i) ) ... print(s) ... [0, 0, 0] [1, 0, 0] [0, 1, 0] [1, 1, 0] [0, 0, 1] [1, 0, 1] [0, 1, 1] [1, 1, 1]
おわりに
できた
これで競プロが捗る
pythonで二次元配列を初期化するときの注意
はじめに
最近pythonで競技プログラミングをやっていて、2次元配列の挙動で注意しておかないといけないことを見つけたのでメモ。
環境
説明
>>>はインタラクティブモードのアレです
1次元配列
pythonでは以下のように配列を初期化できる
>>> d = [0] * 3 >>> d [0, 0, 0]
要素の変更も容易にできる
>>> d[0] = 1 >>> d [1, 0, 0]
2次元配列
しかし、二次元配列となると話が変わってくる
内側の配列の要素を一つだけ変えようとすると他の配列の要素も変わってしまう
>>> l = [[0]*2]*3 >>> l [[0, 0], [0, 0], [0, 0]] >>> l[0][1] = 1 >>> l [[0, 1], [0, 1], [0, 1]]
id関数でオブジェクトのIDを見てみると、内側の配列のIDが同じことが分かる。
つまり、内側の配列のオブジェクトは全て同じ場所を参照しているので、どれかを変更すると他の配列も変更されてしまう。
>>> id(l[0]) 4319671496 >>> id(l[1]) 4319671496
対策
これを防ぐには、内包表記で初期化するのが良いだろう
>>> l = [[0]*2 for _ in range(3)] >>> l [[0, 0], [0, 0], [0, 0]] >>> l[0][0] = 1 >>> l [[1, 0], [0, 0], [0, 0]]
内側の配列のIDが違うことも確認できる
>>> id(l[0]) 4320008648 >>> id(l[1]) 4320008392
終わりに
pythonで二次元配列を初期化するときは気をつけよう。
EFSに付いているセキュリティグループを列挙する
タイトルの通り。
もうちょっと短く書きたい。
aws efs describe-file-systems --query FileSystems[].[Name,FileSystemId] --output text | awk '{print $2}' | while read fsid; do aws efs describe-mount-targets --file-system-id $fsid --query MountTargets[].[FileSystemId,MountTargetId] --output text | awk '{print $2}' | while read mtid; do aws efs describe-mount-target-security-groups --mount-target-id $mtid --query SecurityGroups[] --output text; done; done
ゴッホ展に行ってきた
はじめに
2020/01/12に上野の森美術館で開催されていたゴッホ展に行ってきました。
熱が冷めぬうちに学び・感想を書いておきます。
学び・感想
箇条書きで書きます。
感想は「🤔」マークをつけます
間違いがあったら指摘してほしいです。
- 19世紀後半の画家（1853~1890)
- オランダ生まれ
- 父は牧師
- 最初は聖職者を目指してた
- 27才で画家になる決心をし、37才で自殺
- 🤔有名な画家は小さい頃から画家を目指しているものだと思っていた
- 🤔10年しか画家活動をしていない、短い
- ハーグ派->印象派->新印象派 の順で画風が変わっていく
- 油彩画だと立体感が生まれる
- 🤔『糸杉』から一般に知られているゴッホの絵っぽくなった
- 🤔ゴッホは色弱だった説があるけど、印象派時代は普通の色合いを使っているように感じた
- 音楽家と画家は交流があった
- 🤔クラシックと絵画の親和性が高いと感じる理由？
- 🤔音声ガイドでドビュッシーの『月と光』を使っていてとても良かった
- 3Dプリンタでコピーされた絵が販売されていた
- 🤔絵画の複製が楽になり、単価が安くなり、絵画が一般家庭に広まりやすくなるかも
- パリに来てからは画家仲間ができてゴッホは明るくなった
- 🤔仲間大事
- 🤔絵の横の文字より音声ガイドの方が記憶に残っている
- 🤔音声ガイドをケチるべきではない
終わりに
初めてちゃんと美術観賞をしました。
自分が行った時は入場80分待ちで諦めかけましたが、非常に実りのある展覧会でした。
今後もいろんな展示会に行こうと思います。
2020年の目標
はじめに
今年はちゃんと目標を決めてそれをやり切る人になろうと思います。
目標を決めることによって以下のメリットを享受できるかと思っています。
- モチベーション維持
- 達成した時に自信になる
- (後で追記)
目標
定量的な目標にしました。 その方が分かりやすく、モチベーション維持になりやすいと思ったので。
状況によって後で追記・変更する可能性はありますが、方向性としてはこんな感じです。
また、定期的に達成状況を確認することでモチベージョンを維持しやすいらしいので、適宜達成状況を更新していきます。
目標一覧
秘密な目標に関してはリアルで会って聞いてくれたら答えます。
1. AtCoder 水色以上
AtCoder（プログラミングコンテストを開催しているWebサービス）のランクを水色まで上げたいと思ってます。
レーティング機能があり、レートによってランクが決まります。
灰、茶、緑、水、青、黄、橙、赤の順でランクが上がっていきます。
AtCoder社長のchokudaiさんによると水色のレベルは、
半数以上のIT企業において、アルゴリズム能力についてはカンストと言えるでしょう。特にアルゴリズム的な能力を必要としない会社であれば、ここから上はレートを上げても実務に役立つ部分はほとんどありません。
らしいです。
プログラミング歴7年になる年なのでこれくらいはいきたいと思ってます。
まだ水色がどれくらいのすごさなのか分かってないので、ふざけた目標になってたら笑ってください。
進捗
茶色です。（3/3現在)
10回参加してようやく色が変わりました。
だんだん順位やパフォーマンスが上がっているので、水色も射程県内だと思っています。
2. TOEIC 860点以上
将来的に海外で働きたいという思いがあるので英語も目標を立てようと思いました。
とりあえずよく知ってるTOEICを選びました。IELTSとかTOEFLの方が良かったかもですが、ハードルの高さはモチベーションの高さに反比例すると思ってるのでひとまずTOEICで行きます。
ただ、TOEICのための学習というよりは英語自体の学習をして結果的にTOEICの点数が高くなれば良いなと思っています。
進捗
3年くらい前に600点を取ってから受けてないので現在はもう少し高いと思います（願望）。
ある程度の点数を知りたいので、まずは現在のTOEICの点数を測れる模試を買ってやってみようと思います。
4月12日のTOEICを申し込みました。まずはこれで何点取れるか試してみたいです。
3. Webサービスを2つ以上リリース
単にWebサービスを作って運営したいという思いと、スキルアップのためにこの目標を立てました。
ユーザー数などは特に考えず、自分が使いたいものを2つ作れたらクリアとします。
進捗
アイディア出しをこれからします。
4. 月1で美術館に行き、毎回人と議論する
『インプット大全』によると、美術観賞を行うことには以下の5つの利点があるそうです。
- 学力が上がる
- AI時代を生き抜く創造性が養われる
- 脳が活性化する
- 癒し効果
- ビジネススキルがアップする
進捗
- ✅1月
- ✅2月
5. 週1ブログ更新
アウトプットの習慣をつけるために週1でブログを更新します。
『インプット大全』によると、アウトプットを前提としたインプットをするとインプットの効率が上がるそうです。これもブログ更新を続けたい理由の一つです。
続けるのが重要なのでジャンルはなんでもありにします。
進捗
- ✅ 1月6日の週
- ✅ 1月13日の週
- ✅ 1月20日の週
- ✅ 1月27日の週
- ✅ 2月3日の週
- ❌ 2月10日の週
- ❌ 2月17日の週
- ✅ 2月24日の週
6. 週1運動
健康維持のため、週1以上の運動を行います。
運動の負荷、時間等は問いません。 ただし、移動の際の徒歩は運動に含めないことにします。
進捗
- ❌ 1月6日の週
- ✅ 1月13日の週
- ✅ 1月20日の週
- ❌ 1月27日の週
- ✅ 2月3日の週
- ❌ 2月10日の週
- ❌ 2月17日の週
- ❌ 2月24日の週
終わりに
暖かく見守ってください。
