ryo’s blog

日々学んだことをまとめています.

2022年4月振り返り

42 Tokyoで取り組んだこと C++のSTLコンテナ再実装 github.com C++リファレンスを読み漁る日々に別れを告げました。 vectorやmapなど、データ構造の内部実装が知れて面白い課題でした。 内容が濃かったので、気が向いたら別途記事を書こうかなと思います。 …

2022年3月振り返り

42 Tokyoでの取り組み C++のSTLコンテナ再実装 mapの実装をAVL木で実装しました。 これで必須パートのvector、stack、mapの実装が終わったことになります。 残りは細かい仕様の確認と実行速度の改善など行っていく予定です。 4月中旬には完成させたいですね…

2022年2月振り返り

42 Tokyoでの取り組み ターミナル上に回転する3dモデルを表示する課題 github.com ペア課題でターミナル上に3dモデルを表示するプログラムを作成しました。 お互い空いた時間に進めようと話していましたが、ペアの方がめちゃめちゃコミットしてくれたので、…

Rails チュートリアルを完走した

はじめに 今月からRailsを用いた開発に携わることになったので、かの有名なRails チュートリアルに取り組んでみました。 大体かかった期間は1ヶ月です。 内容 TwitterのようなSNSアプリケーションの開発を通して学びます。 MVCモデルとはなんぞやというとこ…

2022年1月振り返り

はじめに 活動を振り返ることで、自分の現在地や次のステップが見えてくるという噂を耳にしたので、今年から毎月振り返り記事を書きます。(いつまで続けるかは不明) 主に42 Tokyoでの取り組みが中心になりそうですが、さっそく振り返っていきます。 42 Tokyo…

2021年振り返り

軽い自己紹介 25歳ソムリエの Ryo です。以前はミシュラン2つ星レストランやワインバーに勤めていました。 現在はエンジニア転職を目指して、42TokyoでC言語を中心にコンピュータの基礎から学習しています。 はじめに 2021年を一言で表すと 「42」 これにつき…

モンテカルロ法を用いた四目並べAIを作ってみた

制作物 github.com はじめに C++で立体四目並べのプログラムを作成しました。 ただ交互にコマを置いていくだけだと、おもしろくない(そもそも戦う相手がいない)ので、敵を作ることにします。 なるべく強キャラにするため、モンテカルロ法というアルゴリズム…

nba_apiを使って1996年ドラフトNo.1プレイヤーを決めてみた

はじめに スター選手が多いことから伝説とされる1996年ドラフトで 誰がNo.1なのかnba_apiを使って決めてみました。 方法としては、各スタッツの合計値をもとにグラフで表示し確認しています。 言語はPythonです。 制作物 github.com まずはnba_apiを使って、…

第12章 並行プログラミング

プロセス スレッド セマフォによるスレッドの同期 並行性の問題 感想 12章について この章では、並行プログラミングを書くための基本的なメカニズムについて説明されていました。 プロセス、スレッド、マルチプレクシングと異なる手法を用いた実装方法をはじ…

第11章 ネットワーク・プログラミング

ネットワーク グローバルIPインターネット IPアドレス インターネット・コネクション ウェブの基本の話 感想 11章について この章では、これまで学んできたことを結びつけてネットワークの概念について説明してありました。 最終的にシンプルなWebサーバーの…

第10章 システム・レベルI/O

ファイルあれこれ カーネルのファイル管理 標準I/O 感想 10章について この章では、ファイルやディレクトリプタといったUNIX I/Oの基本的なコンセプトについて説明されていました。 Webサーバの実装や並行プログラミングにつながる章となっています。 以下ま…

第9章 仮想メモリ

仮想メモリの特徴 キャッシュの構成 ページ・テーブル アドレス変換 Linux の仮想メモリ・システム 共有オブジェクト コピー・オン・ライト 動的メモリ・アロケータ 断片化(フラグメンテーション) ガーベジコレクション 感想 9章について この章では、メモリマッ…

第8章 例外的な制御フロー

例外的な制御フローって? 例外 プロセス 平行と並列 コンテクスト・スイッチ システム・コールにおけるエラー・ハンドリング プロセスの生成と終了 シグナル 非局所的ジャンプ 感想 8章について この章では、制御フローについて学んでいきます。 例外的な制御…

第7章 リンク

リンクとは? 静的リンク オブジェクト・ファイル シンボル マングリング ライブラリが必要な理由 再配置 共有ライブラリって? ポジション非依存コード(PIC) インターポジショニング 感想 7章について この章では、そもそもリンクとはなんだろう?ということ…

植山類さん講演会 (並行プログラミング)

先週に引き続き、リンカlldのオリジナル作者かつ現メンテナで、Cコンパイラ8ccの作者である植村類さんの講演会に参加しました。 今回は並行プログラミングを主題として、効率化の仕組みや類さんが自作されているリンカmoldについても教えていただきました。 …

第6章 メモリ階層

メモリ階層 ストレージの技術 DRAMの種類 メイン・メモリへのアクセス ディスク・ストレージ 半導体ディスク (SSD) 局所性 キャッシュ ライトに関する問題 キャッシュ・パラメタの性能への影響 感想 6章について この章では、メモリ階層ごとの特性や回転ディス…

競プロ典型90問 050(★3) DP

050 - Stair Jump(★3) 問題 N 段の階段 があり、一歩で 1 段か L 段上がれる。 0 段目からN 段目までたどり着く移動方法何通りか、109 + 7 で割った余りを求める。 解法 そこまでに行ける通り数をDPで下から計算する。 答えは大きくなるので常にmodを取り…

競プロ典型90問 048(★3) 貪欲法

048 - I will not drop out(★3) 問題 N 問, K 分間, 満点 A 点, 部分点 B 点(部分点は満点未満, 半分より大きい) つまり を満たす。 1分で部分点, 2分で満点が取れる。 K 分間で得られる最大得点を求める。 解法 得点方法は2パターン。 B 点取る or B 点取…

植山類さん講演会

植山類さんの講演会に参加してきました。 植山さんは、高速なリンカlldのオリジナル作者かつ現メンテナで、Cコンパイラ8ccの作者でもあります。 そのため今回は特にリンカについて詳しく教えていただきました。 リンカの役割から動的リンクの仕組みまで前提…

第5章 プログラム性能の最適化

プログラムの最適化 最適化コンパイラ コードレベルの最適化 スーパースカラ 投機実行 レジスタ関連 ループ・アンローリング 条件付き移動 write/read依存 性能向上の4つのテクニック 感想 5章について この章では、コードの性能を向上させる数多くのテクニッ…

競プロ典型90問 046(★3) 組合せの問題

046 - I Love 46(★3) 問題 3つの長さ N の数列 A, B, C が与えられる。 が46の倍数となるの選び方の総数を求める。 解法 3つの数列が最大105と制約が厳しいため全探索ではTLEになってしまう。 そのため、最初にmodを取ることで、0〜45の46種類に絞る。 463…

第4章 プロセッサ・アーキテクチャ

ISA(命令セット・アーキテクチャ) プログラマ・ビジブルって? ハードウェア設計 レジスタファイル シーケンシャルなプロセッサ(SEQ) 処理ステージの説明 パイプライン処理 効率低下の要因 パイプライン・ハザードとは? 例外処理 感想 4章について この章では…

競プロ典型90問 038(★3) オーバーフロー

038 - Large LCM(★3) 問題 A, Bの最小公倍数を求める。 を超える場合は Large と出力する。 解法 最小公倍数は で表される。 そのまま計算すると でオーバーフローすることがあるので、式を変換する。 であれば が成り立つので正しく答えが求まる。 ちなみ…

第3章 プログラムのマシン・レベルの表現

高水準言語と低水準言語 マシン・レベル・コード 符号拡張 データ移動 ジャンプ命令 データ転送と制御転送 プロシージャ ポインタ演算 配列の格納 構造体と共用体 アラインメント制約 バッファ・オーバーフロー セキュリティ対策 感想 3章について この章では、…

競プロ典型90問 032(★3) 順列全探索

032 - AtCoder Ekiden(★3) 問題 N人の駅伝選手。 コースは 1からN区まであり、選手 i が j 区までかかる時間は M 個のルールがあり、 と はたすきの受け渡しができない。 ゴールまでにかかる時間の最小値を求める。 解法 制約が N ≤ 10 と小さいため最大で…

競プロ典型90問 020(★3) 浮動小数点の誤差

020 - Log Inequality(★3) 問題 < が成り立つか。 解法 愚直に log() を使って求めると誤差が出てしまう。 そのため全て整数で処理をする必要がある。 対数 log は 底が同じ値の場合、log が外せるので、 は と表せる。 そして累乗の場合は、 が成り立つ。…

競プロ典型90問 018(★3) 三角関数

018 - Statue of Chokudai(★3) 問題 平面 x = 0 上に、高さ L の T 分で一周する観覧車がある。 xy 平面が水平で z が垂直。 0 分後の座標は 分後の座標は 分後の座標は 分後の座標は 銅像が にある。 以下の形式の質問が Q 個与えられるので順に求める。 …

競プロ典型90問 016(★3) 全探索

016 - Minimum Coins(★3) 問題 A円、B円、C円と硬貨が3種類ある。 それぞれ0枚以上使ってちょうどN円を支払うとき、使う硬貨の枚数の最小値を求める。 解法 そのまま全探索すると になり、TLEする。 そのためループを3重から2重へと減らす必要がある。 xと…

競プロ典型90問 014(★3) 貪欲法

014 - We Used to Sing a Song Together(★3) 問題 N人。家は にある。 学校は N校あり、 にある。 全員別の学校に通わせる。 学生 i の家から学校までの距離 , 不便さは距離の総和 である。 位置 u から位置 vまでの距離は 不便さの最小値を求める。 解法 …

競プロ典型90問 007(★3) 二分探索

007 - CP Classes(★3) 問題 N個のクラス、Q人の生徒。 クラスのレーティングは , 生徒のレーティングは と表す。 不満度は対象レーティングと自分のレーティングの差の絶対値。 各生徒の不満度の最小値を求める。 解法 Aをソートして 以上と未満の値の2つ…