放送大学の問題解決の数理で学んだアルゴリズムの覚書。 ダイクストラ法とは 計算量 処理概要 ソースコード 定式化 定式化例題 参考 ダイクストラ法とは 2頂点間の最短距離を求める。 重みがマイナスだと使えない。 計算量 O(頂点数2) （オリジナルの場合） …

座標圧縮とは ソースコード 例題 参考サイト 座標圧縮とは 値が何番目に小さいかをナンバリングする。 例えば、下記のX座標が何番目に小さいかを知りたい時に使う。 元の並び順を維持したままいける。 X = [8, 50, 33, 33, 33, 12, 1, 777]#1 4 3 3 3 2 0 5 …

まだ、初歩的な部分に触れただけなので追記したい。 動的計画法とは 自分の理解 例題 例題の解答コード 参考サイト 動的計画法とは 動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つ…

幅優先探索（BFS）とは 使い所 ソースコード 参考サイト 例題 幅優先探索（BFS）とは 幅優先探索とは、グラフや木構造を探索するためのアルゴリズムの一つで、探索を開始する頂点から近い順に探索する方式。 幅優先探索（BFS / 横型探索）とは - 意味をわか…

理解するのに苦労したので、忘れないようにメモ。 使い所 参考サイト Java Python 使い所 選択する or 選択しないの2択を組み合わせ全探索するとき。 参考サイト qiita.com algo-method.com Java 「1 << N」 は２のN乗。 「S & (1 << i))」は整数Sを2進数と…

グラフ問題の考察や解法でよく使いそうなものをメモ。 連結成分の個数を数える サンプルコード（無向グラフ） 例題 参考サイト 閉路検出 参考サイト 木構造 頂点の深さ計測 参考サイト 最短経路＆経路復元＆距離計測 連結成分の個数を数える 全ての頂点から…

C問題にめちゃくちゃ苦戦したのでメモ。 atcoder.jp 解法 解答コード 参考サイト 解法 約数列挙問題。 文字起こしがしんどいので、画像で許して。 とりあえず「ABの約数の個数×CDの約数の個数」が答え。 思考過程 解けたとき気持ちよかったｗ 解答コード # N…

約数の数を知りたいなあ、という時にすぐ使えるようにメモ。 ソースコード 参考サイト ソースコード # N の約数をすべて求める関数 def calc_divisors(N): # 答えを表す集合 res = [] # 各整数 i が N の約数かどうかを調べる for i in range(1, N + 1): # √…

AtCoderで試しにPythonを使ってみることにしたのでメモを。 主に競技プログラミングで必要になることを箇条書き。 標準出力 標準入力の受け取り 内包表記 演算子 データ型 listの操作一覧 dict型（連想配列）の操作 defaultdict set(集合）の操作 優先度付き…

itertoolsで全部いける！ Javaバージョン itertoolsで全部いける！ import itertools # 直積 ネストしたforループと同じ 0～3の数字の全通り。SQLで言うところのCROSS JOIN # repeat=for文のネスト数と同じ。つまり数列の桁数。3*3*3=27 for product in iter…

二分探索とは 理解のポイント 自力実装 条件を満たす最小の値を求める 条件を満たす最大の値を求める 参考サイト bisect関数 番兵の活用方法 例題 二分探索とは 二分探索とは、データ検索アルゴリズムの一つで、ソート（整列）済みのデータ群の探索範囲を半…

けっこうよく見るタイプなので、メモとして色々な解き方を書いておく。 ・問題文 1~Nまでの数字が３回出現する。 ２回目に出現するのが早い順に出力する問題。 例：1 3 3 3 2 2 1 1 2 ←１～３までの数字が３回ずつ出現。 atcoder.jp 解き方１：答えがわかっ…

放送大学の授業でユークリッドの互除法を見て、その後にちょうとAtCoderでユークリッドの互除法を使う問題に出会った。 ということで備忘録として。 atcoder.jp ユークリッドの互除法とは プログラム（引き算バージョン） プログラム２（余りバージョン） gc…

この問題が解けなかったので、再帰関数を勉強した。⇩ atcoder.jp 参考サイト 多重for文 再帰関数の使い所 全探索・順列全探索・組合せ全探索を再帰関数で書いてみた 処理の流れイメージ 再帰処理のスレッドとは？ ABC302-C Almost Equalの解答 組合せ全探索…

深さ優先探索を理解するために、写経したり実装したりしてみた。 参考サイト 深さ優先探索とは 自分なりの理解 計算量 使い所 グラフを隣接リスト表現で作ってみる 木構造を深さ優先探索する 再帰関数バージョン 入力値 再帰関数の面白いところ ノード0とノ…

記念すべき初rated参加。 コンテスト参加は2回めだけど前回はDDos攻撃でunratedになった。 A - Overall Winner B - Fill the Gaps 参考解答 C - AtCoder Cards atcoder.jp A - Overall Winner ・改善点 過半数勝利を先にどっちがするか判定 ⇨ 同点なら先に過…

自分の解答 自分の解答２ 模範解答 学んだこと int配列の中から出現数が最も多い要素をk個取り出す問題 自分の解答 /** 自分の解答 Accepted! * Map<数値, 出現数>に一旦格納してから * Map<出現数, 数値リスト>に格納し直す * 出現数でソートして高出現数順…

自分の解答 自分の解答２ 模範解答 学んだこと 自分の解答 int配列の中から2つを取り出し、足した値がTargetと同じになる組み合わせを探す問題。 ２重ループ。Accept public int[] twoSum(int[] nums, int target) { int[] answer = new int[2]; for(int i =…

自分の解答1 自分の解答2 模範解答 ちょっとずるいやつ 自分の解答1 2つの文字がアナグラムになっているかを判定する問題。 Accept public boolean isAnagram(String s, String t) { // 文字数が違う場合はfalse if (s.length() != t.length()) { return fal…

HashMapはキーと値のセットを要素として持つデータ構造。 参考 検索がO(1)になる理由 アドレス決定の例 参考 わかりやすいのでこっち見たほうが早い↓ JavaにおけるHashMapの仕組みを深堀り - Qiita 検索がO(1)になる理由 HashMapは要素を格納するメモリアド…

NeetCodeなるものの存在を知ってLeetCodeを始めました。 解説動画がわかりやすくてとても良いです。 英語なので大変ですが。。。 neetcode.io 自分の解答 模範解答 学び 学び２ 自分の解答 何も考えずに2重ループで重複チェック。 タイムオーバーでした。 //…

各コレクションの特徴 List Map Set コレクションの計算量 計算量の目安 各コレクションの特徴 ・参考 コレクションクラスの比較 - Javaちょこっとリファレンス xxxxxxxxxxx ArrayList LinkedList HashMap LinkedHashMap TreeMap HashSet TreeSet ｲﾝﾀﾌｪｰｽ Li…