Aizu Online Judge
ITP2 AOJ のプログラミングのための基礎となる問題を解きました。最近、C++ の環境構築を行ったので、実践に向けて C++ で問題を解きました。 onlinejudge.u-aizu.ac.jp
問題 Union-Find木に関する問題です。 互いに素な集合 Union Find| データ構造ライブラリ | Aizu Online Judge
最短経路問題 GRL_1では最短経路問題を扱います。ダイクストラ法やベルマン–フォード法やワーシャルフロイド法について学びます。
問題 整数に関する問題のセットです。問題の中には今後、ライブラリ的に使うことがあると思います。 http://judge.u-aizu.ac.jp/onlinejudge/finder.jsp?course=NTL
重み付きグラフ 螺旋本の13章 重み付きグラフを読んでいきます。 この章では、グラフの変に重みがついたものを扱います。最小全域木や最短経路を学びます。
深さ優先探索 何度か取り上げたことがありますが、深さ優先探索の問題です。螺旋本の12.3 深さ優先探索の解説を読みました。 深さ優先探索 | アルゴリズムとデータ構造 | Aizu Online Judge
しゃくとり法 今回はしゃくとり法について勉強しました。 しゃくとり法は連続する区間に対するクエリを効率的に返します。
平方分割 セグメント木を勉強しようと思い解説記事を読んでいたんですが、いまいち理解できませんでした。調べている最中に平方分割という手法を知り、自分でも少し理解できそうだったのでそれを試すことにしました。
Aize Online Judge 競技プログラミングのサイトとして有名なAizu Online Judgeをまたやり始めました。
問題 二分木 | アルゴリズムとデータ構造 | Aizu Online Judge プログラミングコンテスト攻略のためのアルゴリズムとデータ構造の8.3 二分木の表現です。データ構造の一種でこれを利用できるようにしたいですね。 参考サイト programming-place.net
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 8.2 根付き木の表現 本当にA問題なのかと疑いたくなります。 根付き木はデータ構造の一部です。あまり理解できませんでしたが、頭に入れておきたいです。
問題 最小コストソート | アルゴリズムとデータ構造 | Aizu Online Judge なるほど、わからん。解説読んでも解答コード見てもわからん。 理解するのに一年位かかりそうです。理解したら追記しよう。
マージソートを利用した反転数の計算 プログラムコンテスト攻略のためのアルゴリズムとデータ構造7章6節 反転数をやっていきます。 反転数とは数列 ] において、 かつ である組 の個数を言います。バブルソートでも反転数がでてきますね。
クイックソート クイックソート | アルゴリズムとデータ構造 | Aizu Online Judge プログラミングコンテスト攻略のためのアルゴリズムとデータ構造の7章3節 クイックソートをやります。C言語の回答をJavaで書き直しているだけですが、 タイプミスやエラーが…
数値配列を基準値で分割する パーティション | アルゴリズムとデータ構造 | Aizu Online Judge プログラミングコンテスト攻略のためのアルゴリズムとデータ構造の7章2節のパーティションをやりました。パーティションは基準値を元に配列を整列させるアルゴリ…
全探索 プログラミングコンテスト攻略のためのアルゴリズムとデータ構造の6章2節では、全探索のアルゴリズムについてでした。 6章では、再帰・分割統治法を取り扱います。プログラムで再帰といえば、階乗を求めるプログラムが思い浮かびます。 分割統治は、…
二分法 二分探索はソート済の配列を探索するアルゴリズムとして有名ですが、数値計算で二分法というものがあります。 二分法は、解の範囲が既知のとき、範囲の中間値を解の候補として探索していく手法です。 高校数学まででは馴染みがないですが、入試でみか…
ハッシュ ハッシュとは、あるデータが与えられたときに、そのデータを代表する数値を得る操作です。その数値はハッシュ値と呼ばれ、直接データを比較するのではなく、ハッシュ値同士を比較することで、同じデータかどうかを判別可能になります。 異なるデー…
番兵法 プログラミングコンテスト攻略のためのアルゴリズムとデータ構造の5.2 線形探索の項目では、番兵法が取り上げられていました。 プログラミングコンテスト攻略のためのアルゴリズムとデータ構造作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力)出版社/メーカ…