山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

Aizu Online Judge

[Aizu Online Judge] Graph Algorithms 1 (GRL_1)

最短経路問題 GRL_1では最短経路問題を扱います。ダイクストラ法やベルフォードマン法やワーシャルフロイド法について学びます。

[Aizu Online Judge] Number Theory

問題 整数に関する問題のセットです。問題の中には今後、ライブラリ的に使うことがあると思います。 http://judge.u-aizu.ac.jp/onlinejudge/finder.jsp?course=NTL

[Aize Online Judge] ALDS1_12

重み付きグラフ 螺旋本の13章 重み付きグラフを読んでいきます。 この章では、グラフの変に重みがついたものを扱います。最小全域木や最短経路を学びます。

[Aizu Online Judge] ALDS1_11_B: Graph I - Depth First Search

深さ優先探索 何度か取り上げたことがありますが、深さ優先探索の問題です。螺旋本の12.3 深さ優先探索の解説を読みました。 深さ優先探索 | アルゴリズムとデータ構造 | Aizu Online Judge

[Aizu Online Judge] Data Sets and Queries 3、しゃくとり法 [DSL3]

しゃくとり法 今回はしゃくとり法について勉強しました。 しゃくとり法は連続する区間に対するクエリを効率的に返します。

[Aizu Online Judge] 平方分割に関する問題 [DSL1A: Range Minimum Query, DSL1B: Range Sum Query]

平方分割 セグメント木を勉強しようと思い解説記事を読んでいたんですが、いまいち理解できませんでした。調べている最中に平方分割という手法を知り、自分でも少し理解できそうだったのでそれを試すことにしました。

Aizu Online Judge Introduction to Programming I の感想

Aize Online Judge 競技プログラミングのサイトとして有名なAizu Online Judgeをまたやり始めました。

[Aizu Online Judge] Rooted Trees (ALDS1_7_B: Binary Tree)

問題 二分木 | アルゴリズムとデータ構造 | Aizu Online Judge プログラミングコンテスト攻略のためのアルゴリズムとデータ構造の8.3 二分木の表現です。データ構造の一種でこれを利用できるようにしたいですね。 参考サイト programming-place.net

[Aizu Online Judge] Rooted Trees (ALDS1_7_A: Rooted Trees)

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 8.2 根付き木の表現 本当にA問題なのかと疑いたくなります。 根付き木はデータ構造の一部です。あまり理解できませんでしたが、頭に入れておきたいです。

[Aizu Online Judge] 最小コストソース (ALDS1_6_D: Minimum Cost Sort)

問題 最小コストソート | アルゴリズムとデータ構造 | Aizu Online Judge なるほど、わからん。解説読んでも解答コード見てもわからん。 理解するのに一年位かかりそうです。理解したら追記しよう。

[ALDS1_5_D] The Number of Inversions

マージソートを利用した反転数の計算 プログラムコンテスト攻略のためのアルゴリズムとデータ構造7章6節 反転数をやっていきます。 反転数とは数列 ] において、 かつ である組 の個数を言います。バブルソートでも反転数がでてきますね。

[Aizu Online Judge] クイックソート (ALDS1_6_C: Quick Sort)

クイックソート クイックソート | アルゴリズムとデータ構造 | Aizu Online Judge プログラミングコンテスト攻略のためのアルゴリズムとデータ構造の7章3節 クイックソートをやります。C言語の回答をJavaで書き直しているだけですが、 タイプミスやエラーが…

[Aizu Online Judge] パーティション (ALDS1_6_B: Partition)

数値配列を基準値で分割する パーティション | アルゴリズムとデータ構造 | Aizu Online Judge プログラミングコンテスト攻略のためのアルゴリズムとデータ構造の7章2節のパーティションをやりました。パーティションは基準値を元に配列を整列させるアルゴリ…

[Aizu Online Judge]全探索 (ALDS1_5_A: Exhausive Search)

全探索 プログラミングコンテスト攻略のためのアルゴリズムとデータ構造の6章2節では、全探索のアルゴリズムについてでした。 6章では、再帰・分割統治法を取り扱います。プログラムで再帰といえば、階乗を求めるプログラムが思い浮かびます。 分割統治は、…

[Aizu Online Judge] 二分法を利用した最適解の計算 (ALDS1_4_D: Allocation)

二分法 二分探索はソート済の配列を探索するアルゴリズムとして有名ですが、数値計算で二分法というものがあります。 二分法は、解の範囲が既知のとき、範囲の中間値を解の候補として探索していく手法です。 高校数学まででは馴染みがないですが、入試でみか…

[Aizu Online Judge] ハッシュを使った辞書の実装 (ALDS_1_4_C: Dictionary)

ハッシュ ハッシュとは、あるデータが与えられたときに、そのデータを代表する数値を得る操作です。その数値はハッシュ値と呼ばれ、直接データを比較するのではなく、ハッシュ値同士を比較することで、同じデータかどうかを判別可能になります。 異なるデー…

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 その1

番兵法 プログラミングコンテスト攻略のためのアルゴリズムとデータ構造の5.2 線形探索の項目では、番兵法が取り上げられていました。 プログラミングコンテスト攻略のためのアルゴリズムとデータ構造作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力)出版社/メーカ…