問題 Aizu Online Judgepythonのシンプルさの虜になっています。都度intだの配列の宣言がないし、｛｝や；が必要ないだけで、こんなに楽だとは思いませんでした。 joinで配列を空白区切り表示できるのもとても良いです。 def bubbleSort(a,n): cnt=0 for i i…
問題 素数判定 | アルゴリズムとデータ構造 | Aizu Online Judge最近Pythonを始めました。言語に慣れようということで、相変わらずAOJを利用しています。 素数判定のプログラムを書いてみました。 import math def isPrime(x): for i in range(2,int(math.sq…
問題 Set Intersection | Aizu Online Judge積集合の実装です。考え方は和集合の時と同じです。 #include<stdio.h> #include<stdlib.h> #define MAX 200000 #define INF 2000000000 int compare_int(const void *a,const void *b){ return *(int*)a-*(int*)b; } int main(){ int</stdlib.h></stdio.h>…
問題 Set Union | Aizu Online JudgeITP2に問題が追加されていたので、解いてみました。 今回の問題は、与えられた二つの集合の和集合を求める問題です。 マージソートみたいな考え方でやってみました。それぞれをソートした後、要素を比較しながら表示して…
問題 二分探索木 削除 | アルゴリズムとデータ構造 | Aizu Online Judge平衡木であるAVL木の実装に挑戦しようと思い、その前に二分探索木おさらいしとくか～って軽い気持ちで解きなおしたらかなり苦労しました。 ポインタのポインタの理解が疎かになっていま…
問題 連鎖行列積 | アルゴリズムとデータ構造 | Aizu Online Judge行列の掛け算は、掛ける順番が異なると計算回数が変わります。 例えばA:10*5 B:5*8 C:8*20の行列があり、この積ABCを考えると (AB)C=10*5*8+10*8*20=2000(回) A(BC)=5*8*20+10*5*20=1800(回)…
問題 The Number of Windows | Sliding Window | Aizu Online Judge尺取り法の練習です。以下のページを参考にしました。 qiita.com アルゴリズムは割とスムーズにできたのですが、途中でWrongになってしまい困っていました。 よくよく見たら、途中のsumやan…
問題 The Smallest Window | Sliding Window | Aizu Online Judgesmallest windowを求める問題です。なんじゃそりゃって感じですね。 どうやら尺取り法というアルゴリズムが良いらしいです。初めましてのアルゴリズムだったので、調べました。 考え方はこち…
問題 Rooted Trees | Aizu Online Judge最近は相変わらずjavaをやっております。今回は木の実装です。 ノードというクラスを作り、その配列に情報を詰め込む、という感じです。 import java.util.Scanner; class Node { private int parent; private int dep…
問題 双方向連結リスト | アルゴリズムとデータ構造 | Aizu Online Judgejavaで双方向リストの実装に挑戦しました。以下のページを参考にしました。 プログラミング/11 - CourseWikiこの問題でjavaにおける参照について、なんとなく理解できた気がします。 …
問題 キュー | アルゴリズムとデータ構造 | Aizu Online Judgeキューを実装する問題です。今回は配列を用いて、リング状のキューを実装します。 イメージは問題ページのアルゴリズムの所に記載されています。javaのクラスを練習したいので、クラスを用いて実…
問題 深さ優先探索 | アルゴリズムとデータ構造 | Aizu Online Judge今日はALDSの復習です。深さ優先探索の実装です。超基本問題ですね。 深さ優先探索⇔スタック、幅優先探索⇔キューって対応しています。なのでスタックを用いて実装することも可能ですが、面…
問題 スタック | アルゴリズムとデータ構造 | Aizu Online Judgeスタックを利用した、逆ポーランド記法の式の計算を実装する問題です。 javaでクラスを勉強し始めたので、スタックをクラスで実装してみました。 import java.util.Scanner; class Stack { pri…
問題 文字のカウント | プログラミング入門 | Aizu Online Judgejavaの本を図書館で借りることができたので、再びjavaの勉強を始めました。 明解Java入門編という本なのですが、非常に分かり易いです。紙媒体は良いですね。今は文字列関連の問題ですが、C言…
問題 木の復元 | アルゴリズムとデータ構造 | Aizu Online Judgeある木について、preorderとinorderで得られた情報から木を構築し、postorderを求める問題です。 以下のページが分かり易かったです。 データ構造 巡回結果からの木の構築 Tree - Reconstructi…
問題 マージソート | アルゴリズムとデータ構造 | Aizu Online Judgeマージソートを実装する問題です。 マージソートとかクイックソートとか、分割統治法がすごい苦手なのですが、頑張ってみました。 アルゴリズムは問題のページに載っているのですが、自分…
問題 シェルソート | アルゴリズムとデータ構造 | Aizu Online JudgeALDSの問題を最初から解きなおしているのですが、この問題は解かずに放置していたので初めての取り組みです。 シェルソートとは挿入ソートを改良したものです。以下のページが分かり易かっ…
問題 最大流 | グラフ | Aizu Online Judge最大流の問題です。フォード・ファルカーソンのアルゴリズムにて実装しました。 アルゴリズム自体はなんとなーーーーく分かったのですが、実装は全く手が動きませんでした。 というわけで蟻本のコードをほぼそのま…
問題 Equal Range | Aizu Online Judgeitp2の6は二分探索に関する問題です。今回の問題は、与えられた値のlower boundとupper boundを求める問題です。 以前6-cのlower boundを求める問題を解いたのですが、ぐっちゃぐちゃなコードだったので、この問題を解…
問題 Set: Search | Aizu Online JudgeAOJに新しいコースが追加されていました。ITP2(Introduction to Programming 2)ということなのですが、 「Hello,World」から始まるITP1とは違って結構難しいです。なかなか解き終わりません。 多くはC++に標準実装され…
問題 | アルゴリズムとデータ構造 | Aizu Online JudgeAOJのALDSに新しい問題が追加されていました。Treapを実装する問題です。 TreapとはTree+Heapということで、二分木とヒープの組み合わせです。考えた人すごいっすね。自分で考えてもよく分からなかった…
問題 木の直径 | グラフ | Aizu Online Judge木の直径を求める問題です。 １．任意の点（ｓとする）から最遠の点（ｔとする）をdfsで求める ２．ｔから最遠の点（uとする）をdfsで求める。このとき、tとsの距離が木の直径となる。 アルゴリズムは簡潔なので…
問題 単一始点最短経路 | グラフ | Aizu Online Judge所謂、最短経路問題というやつです。以前解いた時はTLEだったので再挑戦。 ダイクストラ法で実装しました。 このアルゴリズムでは、コストが最小のノードを毎回ピックアップするので、コスト最小のノード…
問題 Range Add Query (RAQ) | Aizu Online JudgeRAQの問題です。RUQとほとんど変わらないので、簡単に実装できました。 今回はxとyが同じバケットだった場合とそうでない場合を、ifで場合分けしました。参考 kujira16.hateblo.jp 本当に分かり易いです。 #i…
問題 Range Update Query (RUQ) | Aizu Online JudgeRUQです。以前このDSLの問題を何問か解きましたが、その時に参考にしたサイトを再び参考にしました。 kujira16.hateblo.jp 分かり易すぎますね。独学者には非常にありがたいです。findは簡単に実装できた…
問題 0-1 Knapsack Problem II | Aizu Online Judge0-1ナップサック問題です。動的計画法の王道ですね。 ふつうは縦に品物、横に重さのdp表を埋めていくことで解けます。以下のページが分かり易かったです。 pieceofnostalgy.blogspot.jpしかし今回はN=100,W…
問題 Edit Distance (Levenshtein Distance) | Aizu Online Judge文字列の編集距離の問題です。動的計画法で解きます。以下のページが分かり易かったです。 d.hatena.ne.jp #include<stdio.h> #include<string.h> #include<stdlib.h> #define MIN(a, b) ((a) < (b) ? (a) : (b)) #define L</stdlib.h></string.h></stdio.h>…
問題 トポロジカルソート | グラフ | Aizu Online Judgeトポロジカルソートの問題です。名前は聞いたことがあったのですが、初挑戦。 こちらのページを参考にしました。 トポロジカルソート - ferinの競プロ帳１．各ノードに自分に向かう辺の数（入次数）を…
問題 有向グラフの閉路検知 | グラフ | Aizu Online Judge有効グラフの閉路の有無を検出する問題です。 各頂点からdfs→途中でスタートの頂点を通過したら閉路あり という感じで実装しました。頂点の数も少ないので、TLEせず一発okでした。 #include<stdio.h> #include<stdlib.h></stdlib.h></stdio.h>…
問題 グラフの連結成分 | アルゴリズムとデータ構造 | Aizu Online Judge連結生成分解の問題。GRL_3_Cの"強"連結生成分解の問題を解いたのですが、TLEとなってしまいました。 じゃあALDSの連結生成分解ならできるんじゃね？ってことで挑戦したら解けました。…
