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

問題 A / B 問題 | プログラミング入門 | Aizu Online Judgeしばらくブログをサボっていました。というよりは、あまりプログラミングに触れられませんでした。 ですが最近、javaを始めました。という訳で、AOJの初心者向けの内容をやっています。 import jav…

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

問題 双方向連結リスト | アルゴリズムとデータ構造 | Aizu Online Judge双方向連結リストを実装する問題です。 まだポインタの理解があやふやだった頃に解きましたが、今だったらスムーズに書けるかなと思い、再びやってみました。 #include<stdio.h> #include<stdlib.h> #incl</stdlib.h></stdio.h>…

問題 模式断面図の面積 | アルゴリズムとデータ構造 | Aizu Online Judge全く分からず放置していました。なんとなくスタックを使いそう、って思ってから一歩も進みませんでした。 こちらの方が丁寧に説明してくれています。 mtdtx9.hatenablog.comインデック…

問題 逆ポーランド記法 | Aizu Online Judge逆ポーランド記法を実装する問題です。アルゴリズム自体は何の捻りもありません。スタックを使うやつですね。 #include<stdio.h> #include<string.h> #include<ctype.h> #include<stdlib.h> void push(double S[],int *top,double x){ S[(*top)]=x; (*top</stdlib.h></ctype.h></string.h></stdio.h>…

問題 最大連続部分和 | Aizu Online Judge配列の最大連続部分和を求める問題です。 動的計画法で出来ないかな～と考えましたが、僕の脳みそでは全探索しか思いつきません。 色々と調べると、何やら参考になりそうなものを発見。 qiita.com一番最後に書かれて…

問題 ワカサギ釣り | Aizu Online Judgeイベントが入力される都度、最大値を求めるという問題。以前解いたRMQと似ているなと思い、RMQと同じ平方分割で実装してみました。１．各人のワカサギの量を入れる配列Aと、√n人のワカサギの最大値を入れるバケット配…

問題 最小の素数と最大の素数 | Aizu Online Judge入力された数付近の素数を求めるという問題です。 苦しむことなく実装できました。 #include<stdio.h> #include<math.h> int GetPrime(int n){ int i; for(i=2;i<=sqrt(n);i++) if(n % i ==0)return 0; printf("%d",n); retur</math.h></stdio.h>…

問題 国家予算 | Aizu Online Judge多倍長整数の足し算を実装する問題です。 基本情報技術者試験の午後問題で解いたことがあり、今回はそのアルゴリズムを参考に実装しました。参考 基本情報技術者過去問題 平成21年秋期 午後問9｜基本情報技術者試験.com簡…

問題 シーザー暗号 | Aizu Online Judgeシーザー暗号の復元の問題。思いつくままに実装。 1. i文字ずらす 2. 復号できてるかチェック を繰り返すという単純なもの。ifがめっちゃ入れ子になっている部分は非常に恥ずかしい。 #include<stdio.h> #include<string.h> #include<ctype.h> #def</ctype.h></string.h></stdio.h>…

問題 天秤 | Aizu Online Judge与えられた自然数を2のn乗の和で表す問題。以前学んだが、こういうのはビット演算を利用すると良いらしい。参考 ビット演算子 - 演算子 - C言語 入門てなわけで実装。 #include<stdio.h> int main(){ int w; int hundou; while(scanf("%</stdio.h>…

問題 平行判定 | Aizu Online Judge二つの直線が平行かどうか判定する、という問題。 単純に傾きを求めて、比較すればよいのだが、wrongと表示されてしまった。 座標をdoubleではなく、floatにしたらacceptされた。 #include<stdio.h> typedef struct point{ float x;</stdio.h>…

問題 Range Sum Query | データ構造ライブラリ | Aizu Online Judge前回のRMQとほぼ同じ感じで解けそうだったので、すぐに取り掛かってみました。kujira16.hateblo.jp #include<stdio.h> #include<math.h> #define MAX 100000 int min(int a,int b){ if(a < b)return a; retur</math.h></stdio.h>…

問題 Range Minimum Query (RMQ) | データ構造ライブラリ | Aizu Online Judge一度解いたことがあるのですが、その時はめっちゃふつーにやって解けてしまった気がする。 今回は平方分割？というやり方でやってみた。参考にしたのは前回のと同じ。 プログラミ…

問題 互いに素な集合 Union Find| データ構造ライブラリ | Aizu Online Judgeテキトーに配列で実装したら、案の定時間切れ。 調べてみると、こんな解法があるらしい。 プログラミングコンテストでのデータ構造 from Takuya Akiba www.slideshare.net先人の知…