リポジトリ Circles Intersection(AOJ No.0023) circumfence 中心(xa,ya)、半径raの円Aと、中心(xb,yb)、半径rbの円Bが与えられたとき、 B が A の中にあるとき 2、 A が B の中にあるとき -2、 A の円周と B の円周が交わっている場合 1、 A と B が重なっ…

リポジトリ Maximum Sum Sequence(AOJ No.0022) contiguous が与えられたときの、最大の連続部分和を求める。 制約 アルゴリズム 初期化 について、 で部分和を計算していって、毎回で更新。 コード import java.util.*; public class aoj0022 { static fina…

リポジトリ Caesar Cipher(AOJ No.0017) Caesar Cipher シーザー暗号、カエサル暗号、シフト暗号 cipher cryptography encryption 80文字以下のCaesar Cipherで暗号化された文が与えられる。 Caesar Cipherは、アルファベットを辞書順にn文字シフトする暗号…

リポジトリ Treasure Hunt(AOJ No.0016) come across stand facing equivalent crammed 初めは、座標0,0で、北(90°)を向いている。 整数のペア(r,t)が与えられて、r前進し、時計方向にt度回転する。 これを繰り返し、(0,0)が入力された時の座標の整数部を出…

Switching Railroad Cars(AOJ No.0013) 1,2,...,10の番号が振られた電車があり、0以上10以下の整数列が与えられる。 1以上10以下の数字は電車の LIFOの構造への挿入を表し、 0は電車の取り出しを意味する。 取り出された順に電車の番号列を出力するスタック…

リポジトリ A Point in a Triangle(AOJ No.0012) 点P(xp, yp)が点A(x1, y1), B(x2, y2), C(x3, y3)で構成される三角形の内側にある場合はYES, そうでない場合はNOと答える。 アルゴリズム1 とする(反時計回りなら正そうでないなら負)。 点Pが△ABCの内側にあ…

Drawing Lots(AOJ No.0011) w本の縦線とn本の横線からなるあみだくじがあり、左から1,2,....,nと番号が振られている。 横線はという形式で与えられて、とのくじを結ぶ。 くじをした結果、ゴール左側からスタート位置を順に出力する。横線が隣り合う位置に接…

リポジトリ Circumscribed Circle of a Triangle(AOJ No.0010) circumscribed circle central coordinate 頂点がが与えられたときの外接円の中心座標(外心)とその半径を求める アルゴリズム 外心の性質 △ＡＢＣの辺ＢＣ，ＣＡ，ＡＢの垂直二等分線は，外心で…

Ohgas' Fortune(PKU No.2683) ただの読解問題http://www.deqnotes.net/acmicpc/2683/jaに日本語版がある。 預金して最終残高が最大になるようなオペレーションを選んだときの最終残高を求める。 fortune prestigious deposit operation company commit inter…

リポジトリ Reverse Sequence(AOJ No.0006) タイトルの通り import java.util.*; public class aoj0006 { static final Scanner stdin = new Scanner(System.in); public static void main(String[] args) { System.out.println( new StringBuilder(stdin.ne…

リポジトリ 参考になりそうなページ 再帰アルゴリズムによるユークリッド互除法 最大公約数(GCD;Greatest Common Divisor) 2つ以上の整数の最大公約数はの最大の公約数 Euclidの互除法(Euclidean algorithm, Euclid's algorithm) について、が成立することを…

リポジトリ Is it a Right Triangle?(AOJ No.0003) 3辺の長さが与えられたとき直角三角形(right triangle)になっているかどうかを判定する アルゴリズム が成り立つか調べる ※かつ コード はじめ、right triangleを"正しい三角形"と読んで、三角不等式が成り…

個数制限なしナップザック問題(プログラミングコンテストチャレンジブック p58) 重さと価値がそれぞれであるような個の品物がある。 これらの中から重さの総和がを超えないように選んだ時の価値の総和の最大値を求める。 ただし、同じ品物をいくつでも選んで…

最長共通部分列問題(LCS; Longest Common Subsequence) 二つの値の列が与えられて，最長の共通部分列を見つける問題。 部分列は連続している必要はないが，順序は変更してはい。 LCSは一般的に複数ある。 Common Subsequence(PKU No.1458) 二つの文字列とが…

01ナップザック問題(プログラミングコンテストチャレンジブック p34) 重さと価値がそれぞれであるような個の品物がある。 これらの中から重さの総和がを超えないように選んだ時の価値の総和の最大値を求める。 制約 アルゴリズム1 i番目以降の品物から重さの…

Hanafuda Shuffle(PKJ No.1978) n枚のカードが与えられて、下から1,2,...,nの番号が振られている。 が与えられて、 上の枚とその下の枚を入れ替えるカットという操作をr回繰り返した後の一番上のカードの数字を求める。 制約 アルゴリズム ただシミュレート…

載せる意味あんのかwwww 問題はほぼ題名の通り リポジトリ QQ(AOJ No.0000) public class aoj0000 { public static void main(String[] args) { for(int i=1; i<=9; ++i) for(int j=1; j<=9; ++j) System.out.println(i+"x"+j+"="+i*j); } } List of Top 3 H…

4 Values whose Sum is 0(PKU No.2785) 要素数nの整数のリストA,B,C,Dが与えられたとき、各リストから１つずつ取り出したときの和が0となるような組み合わせの個数を求めよ。ただし、１つのリストに同じ値が重複している場合、それらは異なるものとして扱い…

Physics Experiment(PKU No.3684) N個の半径R(cm)のボールで実験を行う。 上空H(m)のところに、筒を立てに設置し、ボールを入れる(下からi番目([tex: 0\leq i アルゴリズム R=0とすれば、Ants(PKU No.1852)と同じように、ボールがすり抜けたものとして考えら…

久しぶりにやったお。 問題A. アンテナ修復 エレメント(線分)の個数Kとエレメントの長さE1〜EKが与えられる。・すべてのエレメントが同一平面上にある ・すべてのエレメントの + 極が同じ位置にある。これを接続点と呼ぶ ・エレメント同士が重なるのは接続点…

Fence Repair(PKU No.3253) 長さの板を長さの板から切り出す。板を切断するとき、その板の長さの分だけコストがかかる。例えば、長さ21の板から長さ5,8,8の3つの板を切り出すとき、21の板を長さ13と8の板に切断すると21のコストがかかり、13の板をさらに5と8…

Saruman's Army(PKU No.3069) N個の点が直線状にある。点iの位置は。N個のうちいくつかの点を選び、それらの点に印をつける。N個の全ての点について、距離がＲ以内の場所に印をつけられた点がなければならない。条件を満たす、印をつけた点の最小の個数を求…

Best Cow Line(PKU No.3617) N文字の文字列Ｓが与えられ、Ｎ文字の文字列Ｔを作る。はじめはＴは長さ0の文字列で、次のいずれかの操作が行える。 ・Ｓの先頭を1文字削除し、Ｔの末尾に追加する。 ・Ｓの末尾を1文字削除し、Ｔの末尾に追加する。 辞書順比較…

区間スケジューリング問題(プログラミングコンテストチャレンジブック p43) N個の仕事がある。各仕事は、時間に始まり、時間[t_i]に終わる。仕事に参加するなら、その仕事のはじめから終わりまで参加しなければならない。参加する仕事の時間帯が重なってはい…

硬貨の問題(プログラミングコンテストチャレンジブック p42) 1円玉、5円玉、10円玉、100円玉、500円玉が、それぞれ枚ずつある。できるだけ少ない枚数の硬貨でＡ円を支払うとき、何枚の硬貨を出す必要があるか。 制約 アルゴリズム なので、大きい硬貨から優…

部分和問題(プログラミングコンテストチャレンジブック p34の設定) 整数の中からいくつか選び、その和をちょうどkにすることができるならYes、できないならNoを出力。 制約 アルゴリズム 部分和問題(プログラミングコンテストチャレンジブック p34にあるよう…

くじびき(プログラミングコンテストチャレンジブックp8) 数字が書かれたn枚の紙切れが袋に入っている。紙切れに書かれた数字をとする。この袋から紙切れを取り出し、数字を見て袋に戻すということを4回行い、4回の紙切れの数字の和がmになる取り出し方が存在…

三角形(プログラミングコンテストチャレンジブックp21) n本の棒があり、棒iの長さは。それらの棒から3本を選んでできるだけ周長の長い三角形を作ろうと考えている。最大の周囲はいくら？ただし、三角形が作れない場合は、0と答える。 制約 アルゴリズム 三角…

Ants (PKU No. 1852) 長さLcmの竿の上をn匹のありが毎秒1cmのスピードで歩いている。アリが竿の端に到達すると竿の下に落ちていく。また、竿の上は狭くてすれ違えないので、2匹のアリが出会うと、それぞれ反対を向いて戻っていく。各アリについて、現在の竿…

プログラミングコンテストチャレンジブックを買ってみた。問題を解く形式のプログラミングコンテストの攻略本的なもの。一通りのアルゴリズムが載っている。プログラミングコンテストに興味がなくても、どういう問題に対して、どのようなアルゴリズムを適応…