はなたの日記

プログラミングとギターのコードについて書きます

C

ITP2_9_B Set Intersection

C

問題 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>…

ITP2_9_A Set Union

C

問題 Set Union | Aizu Online JudgeITP2に問題が追加されていたので、解いてみました。 今回の問題は、与えられた二つの集合の和集合を求める問題です。 マージソートみたいな考え方でやってみました。それぞれをソートした後、要素を比較しながら表示して…

ALDS1_8_C Binary Search Tree III

C

問題 二分探索木 削除 | アルゴリズムとデータ構造 | Aizu Online Judge平衡木であるAVL木の実装に挑戦しようと思い、その前に二分探索木おさらいしとくか~って軽い気持ちで解きなおしたらかなり苦労しました。 ポインタのポインタの理解が疎かになっていま…

DSL_3_C The Number of Windows

C

問題 The Number of Windows | Sliding Window | Aizu Online Judge尺取り法の練習です。以下のページを参考にしました。 qiita.com アルゴリズムは割とスムーズにできたのですが、途中でWrongになってしまい困っていました。 よくよく見たら、途中のsumやan…

DSL_3_A The Smallest Window I

C

問題 The Smallest Window | Sliding Window | Aizu Online Judgesmallest windowを求める問題です。なんじゃそりゃって感じですね。 どうやら尺取り法というアルゴリズムが良いらしいです。初めましてのアルゴリズムだったので、調べました。 考え方はこち…

ALDS_1_11_B Depth First Search

C

問題 深さ優先探索 | アルゴリズムとデータ構造 | Aizu Online Judge今日はALDSの復習です。深さ優先探索の実装です。超基本問題ですね。 深さ優先探索⇔スタック、幅優先探索⇔キューって対応しています。なのでスタックを用いて実装することも可能ですが、面…

ALDS1_7_D Reconstruction of a Tree

C

問題 木の復元 | アルゴリズムとデータ構造 | Aizu Online Judgeある木について、preorderとinorderで得られた情報から木を構築し、postorderを求める問題です。 以下のページが分かり易かったです。 データ構造 巡回結果からの木の構築 Tree - Reconstructi…

ALDS1_5_B Merge Sort

C

問題 マージソート | アルゴリズムとデータ構造 | Aizu Online Judgeマージソートを実装する問題です。 マージソートとかクイックソートとか、分割統治法がすごい苦手なのですが、頑張ってみました。 アルゴリズムは問題のページに載っているのですが、自分…

ALDS1_2_D Shell Sort

C

問題 シェルソート | アルゴリズムとデータ構造 | Aizu Online JudgeALDSの問題を最初から解きなおしているのですが、この問題は解かずに放置していたので初めての取り組みです。 シェルソートとは挿入ソートを改良したものです。以下のページが分かり易かっ…

GRL_6_A Maximum Flow

C

問題 最大流 | グラフ | Aizu Online Judge最大流の問題です。フォード・ファルカーソンのアルゴリズムにて実装しました。 アルゴリズム自体はなんとなーーーーく分かったのですが、実装は全く手が動きませんでした。 というわけで蟻本のコードをほぼそのま…

ITP2_6_D Equal Range

C

問題 Equal Range | Aizu Online Judgeitp2の6は二分探索に関する問題です。今回の問題は、与えられた値のlower boundとupper boundを求める問題です。 以前6-cのlower boundを求める問題を解いたのですが、ぐっちゃぐちゃなコードだったので、この問題を解…

ITP2_7_A Set: Search

C

問題 Set: Search | Aizu Online JudgeAOJに新しいコースが追加されていました。ITP2(Introduction to Programming 2)ということなのですが、 「Hello,World」から始まるITP1とは違って結構難しいです。なかなか解き終わりません。 多くはC++に標準実装され…

ALDS1_8_D Treap

C

問題 | アルゴリズムとデータ構造 | Aizu Online JudgeAOJのALDSに新しい問題が追加されていました。Treapを実装する問題です。 TreapとはTree+Heapということで、二分木とヒープの組み合わせです。考えた人すごいっすね。自分で考えてもよく分からなかった…

GRL_5_A Diameter of a Tree

C

問題 木の直径 | グラフ | Aizu Online Judge木の直径を求める問題です。 1.任意の点(sとする)から最遠の点(tとする)をdfsで求める 2.tから最遠の点(uとする)をdfsで求める。このとき、tとsの距離が木の直径となる。 アルゴリズムは簡潔なので…

GRL_1_A Single Source Shortest Path

C

問題 単一始点最短経路 | グラフ | Aizu Online Judge所謂、最短経路問題というやつです。以前解いた時はTLEだったので再挑戦。 ダイクストラ法で実装しました。 このアルゴリズムでは、コストが最小のノードを毎回ピックアップするので、コスト最小のノード…

DSL_2_E Range Add Query (RAQ)

C

問題 Range Add Query (RAQ) | Aizu Online JudgeRAQの問題です。RUQとほとんど変わらないので、簡単に実装できました。 今回はxとyが同じバケットだった場合とそうでない場合を、ifで場合分けしました。参考 kujira16.hateblo.jp 本当に分かり易いです。 #i…

DSL_2_D Range Update Query (RUQ)

C

問題 Range Update Query (RUQ) | Aizu Online JudgeRUQです。以前このDSLの問題を何問か解きましたが、その時に参考にしたサイトを再び参考にしました。 kujira16.hateblo.jp 分かり易すぎますね。独学者には非常にありがたいです。findは簡単に実装できた…

DPL_1_F 0-1 Knapsack Problem II

C

問題 0-1 Knapsack Problem II | Aizu Online Judge0-1ナップサック問題です。動的計画法の王道ですね。 ふつうは縦に品物、横に重さのdp表を埋めていくことで解けます。以下のページが分かり易かったです。 pieceofnostalgy.blogspot.jpしかし今回はN=100,W…

DPL_1_E Edit Distance (Levenshtein Distance)

C

問題 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>…

GRL_4_B Topological Sort

C

問題 トポロジカルソート | グラフ | Aizu Online Judgeトポロジカルソートの問題です。名前は聞いたことがあったのですが、初挑戦。 こちらのページを参考にしました。 トポロジカルソート - ferinの競プロ帳1.各ノードに自分に向かう辺の数(入次数)を…

GRL_4_A Cycle Detection for a Directed Graph

C

問題 有向グラフの閉路検知 | グラフ | Aizu Online Judge有効グラフの閉路の有無を検出する問題です。 各頂点からdfs→途中でスタートの頂点を通過したら閉路あり という感じで実装しました。頂点の数も少ないので、TLEせず一発okでした。 #include<stdio.h> #include<stdlib.h></stdlib.h></stdio.h>…

ALDS1_11_D Connected Components

C

問題 グラフの連結成分 | アルゴリズムとデータ構造 | Aizu Online Judge連結生成分解の問題。GRL_3_Cの"強"連結生成分解の問題を解いたのですが、TLEとなってしまいました。 じゃあALDSの連結生成分解ならできるんじゃね?ってことで挑戦したら解けました。…

GRL_2_A Minimum Spanning Tree

C

問題 最小全域木 | グラフ | Aizu Online Judge以前記事にした最小全域木の問題とほとんど同じです。頂点の数が以前のものより多く、隣接行列ではメモリ不足になるので、隣接リストを用いました。 アルゴリズム自体はプリムのやつです。 #include<stdio.h> #include<stdlib.h> #</stdlib.h></stdio.h>…

GRL_1_C All Pairs Shortest Path

C

問題 全点対間最短経路 | グラフ | Aizu Online Judge全ての点の最短経路を求める問題です。GRL_1_Bでやったベルマンフォード法をそのまま全点でやるコードを書いたのですが、ダメでした。 原因はGRL_1_Bで実装したベルマンフォード法が間違えてたっぽいです…

GRL_1_B Single Source Shortest Path (Negative Edges)

C

問題 単一始点最短経路 負の重み | グラフ | Aizu Online Judge負のコストを持つエッジを含んだグラフの、最短経路問題です。ダイクストラ法はコストが非負でないと利用できません。 この場合、ベルマンフォード法が有効だそうです。下記のページが分かり易…

GRL_1_A Single Source Shortest Path

C

問題 単一始点最短経路 | グラフ | Aizu Online Judge最短経路問題です。以前ALDSの方で解いたことはありましたが、すっかり解法を忘れていたので、再度調べました。 こちらのサイトが分かり易かったです。 ダイクストラ法(最短経路問題)ダイクストラ法で…

ALDS1_13_A 8 Queens Problem

C

問題 | アルゴリズムとデータ構造 | Aizu Online Judge8クイーン問題です。何度か挑戦したことはあったのですが、中々解けませんでした。 バックトラック法で実装。行けるとこまで行って、ダメだったら一手戻る…みたいなやつです。 #include<stdio.h> #define N 8 int</stdio.h>…

ALDS1_12_A Minimum Spanning Tree(プリムのアルゴリズム)

C

問題 最小全域木| アルゴリズムとデータ構造 | Aizu Online Judge前回と同じ問題です。今度はプリムのアルゴリズムで解いてみました。 やはりこちらのレジュメが分かり易かったです。 http://www.dais.is.tohoku.ac.jp/~shioura/teaching/ad09/ad09-10.pdfヒ…

ALDS1_12_A Minimum Spanning Tree

C

問題 最小全域木| アルゴリズムとデータ構造 | Aizu Online Judge最小全域木を求める問題です。クラスカルのアルゴリズムで実装してみました。 下記の東北大のレジュメが分かり易かったです。参考 http://www.dais.is.tohoku.ac.jp/~shioura/teaching/ad09/a…

Volume0-0030 Sum of Integers

C

問題 整数の和 | Aizu Online Judge与えられた整数sを、0~9の数字のうちn個の和で表す時の場合の数を求める問題です。 全探索すれば良いのですが、今まで全探索のプログラムを書いたことがなかったので、かなり苦戦しました。 #include<stdio.h> int A[11]={0,1,2,3,</stdio.h>…