問題 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の連結生成分解ならできるんじゃね？ってことで挑戦したら解けました。…

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

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

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

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

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

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

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

問題 Print a Frame | Aizu Online Judge問題自体は大したことないのですが、一つ勉強になったことがあったので、ブログを書いています。 最初にコンパイルした際は、「ｊが宣言されてないよ」というエラーが発生しました。 そんな馬鹿なしっかり宣言してい…