[競技プログラミング][C言語][AOJ0009]Prime Number

AIZU ONLINE JUDGE http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0009&lang=jp

Prime Number

6 桁以下の正の整数 n を入力し、n 以下の素数がいくつあるかを出力するプログラムを作成して下さい。
ただし、素数とは 1 と自分自身でしか割り切れない正の整数のうち 1 をのぞいたものをいいます。
例えば 10 以下の素数は、2, 3, 5, 7 です。

Input

複数のデータセットが与えられます。各データセットに n が１行に与えられます。入力の最後まで処理して下さい。

Output

各データセットごとに、n 以下の素数の個数を１行に出力して下さい。

回答：AOJ/vol0/AOJ0009.cpp at master · wada811/AOJ
与えられた整数まで自前で素数判定してカウントすると頑張って高速化しても通らない悲劇…。
どうやら素数判定にはエラストテネスのふるいというものを使うらしい。
これを知らずに自力で頑張って上手くいかなくて半日潰れて泣いた。素数もうやだ…。
そしてこれからのAOJの問題が知ってるかどうかになってきたので萎えてきた。
いい加減C言語でやり続けるのも辛いし、
AOJをひたすら解き続けるのも面白くないのでココで一旦AOJは止めます。

同じ競技プログラミングのAtCoderは2週間に一回くらいなので続けるつもり。
言語は多分C言語ではなくなると思う。
Javascriptを学びたいけど直近の課題としてPHPがあるのでPHPでゴニョゴニョしてるかも。

[競技プログラミング][C言語][AOJ0008]Sum of 4 Integers

AIZU ONLINE JUDGE http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0008&lang=jp

Sum of 4 Integers

50 以下の正の整数 n を入力し、0 ～ 9 の範囲の整数 a, b, c, d の組で

a + b + c + d = n

を満たすものの組み合わせ数を出力するプログラムを作成して下さい。

例えば、n が 35 のとき、(a, b, c, d) は
(8,9,9,9)、(9,8,9,9)、(9,9,8,9)、(9,9,9,8) の 4 通りですので、答えは 4 となります。

Input

複数のデータセットが与えられます。
各データセットに n が１行に与えられます。入力の最後まで処理して下さい。

Output

各データセットごとに、a, b, c, d の組み合わせ個数を１行に出力して下さい。

回答：AOJ/vol0/AOJ0008.cpp at master · wada811/AOJ
超手抜き4重ループ。
コンピュータの計算が速いからやり方は気にしなくてもなんとかなるという…。

それではまた明日。

[競技プログラミング][C言語][AOJ0007]Debt Hell

AIZU ONLINE JUDGE http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0007&lang=jp

Debt Hell

某国に住んでいる友達がお金に困って、
あるヤミ金融業者から 10 万円の借金をしたまま、全く返済していないといいます。
この業者は、一週間ごとに 5% の利子を借金に加え、さらに借金の 1,000 円未満を切り上げます。

n を入力したとき、n 週間後の借金の残高を出力し終了するプログラムを作成して下さい。n は 100 以下とします。

Input

整数 n

Output

n 週間後の返済額

回答：AOJ/vol0/AOJ0007.cpp at master · wada811/AOJ
借金地獄ということで複利計算を行えば良い。
利率をかけ続けながら切り上げる。
切り上げするなら天井関数(ceil関数)使っても良かったかも。

[競技プログラミング][C言語][AOJ0006]Reverse Sequence

AIZU ONLINE JUDGE http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0006&lang=jp

Reverse Sequence

文字列 str を入力したとき、その文字列を逆順に出力するプログラムを作成して下さい。
文字は半角英数字のみで、20 文字以内とします。

Input

文字列 str

Output

str の逆順

回答：AOJ/vol0/AOJ0006.cpp at master · wada811/AOJ
一文字ずつ配列に突っ込んで逆順に取り出すだけー

それではまた明日。

[競技プログラミング][C言語][AOJ0005]GCD and LCM

AIZU ONLINE JUDGE http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0005&lang=jp

GCD and LCM

２０億以下の正の整数 a, b を入力したとき、
a と b の最大公約数と最小公倍数を出力して終了するプログラムを作成して下さい。
ただし、a と b の最小公倍数は 20 億を超えないものとします。

Input

複数のデータセットが与えられます。
各データセットは１行に a と b が１つのスペースで区切られて与えられます。
入力の最後まで処理して下さい。

Output

各データセットに対して、最大公約数と最小公倍数を１つのスペースで区切って１行に出力して下さい。

回答：AOJ/vol0/AOJ0005.cpp at master · wada811/AOJ · GitHub

GCD( greatest common divisor:最大公約数)最大公約数 - Wikipedia
LCM( least common multiple:最小公倍数)最小公倍数 - Wikipedia
ユークリッドの互除法 - Wikipedia
基礎知識としては以上の3つ。
GCDをユークリッドの互除法で求めて、LCM = a * b / GCD でLCMを求める。

ユークリッドの互除法のアルゴリズムはこちら↓が参考になった。
最大公約数を求める2つのアルゴリズムを書いてみた - sh-2の日記
他にもGCDを求める方法はあるみたいだけどわかりやすさでユークリッドの互除法が一番かな。

20億とか言われて面食らった。データ型の最大値を覚えていないので調べると long で大丈夫らしい。
Ｃ言語講座：色々なデータ型の最大値、最小値
LCMを求める時に上の式で計算すると一時的に long の最大値すら超えるので先にGCDで割る必要がある。

それではまた明日。

[競技プログラミング][C言語][AOJ0004]Simultaneous Equation

AIZU ONLINE JUDGE http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0004&lang=jp

Simultaneous Equation

連立方程式

ax + by = c
dx + ey = f

の解、x, y を出力して終了するプログラムを作成して下さい。
a, b, c, d, e, f はそれぞれ、 -1000 以上 1000 以下の実数とし、
連立方程式の解が一意に存在するように与えれれるものとします。

Input

複数のデータセットが与えられます。入力の最後まで処理して下さい。
１つのデータセットが１行に与えられます。
１つのデータセットに a, b, c, d, e, f が１つのスペースで区切られて与えられます。

Output

各データセットに対して、x, y を１つのスペースで区切って１行に出力して下さい。
各値は小数点以下第３位まで出力して下さい。小数点以下第４位を四捨五入して下さい。

回答：AOJ/vol0/AOJ0004.cpp at master · wada811/AOJ
行列の凄さは教えられないことが多いけど
プログラムがこのように連立方程式を計算するのに役立つって事を教えればいいのに。

fabs()で-0を0に直さないと通らないので注意。fabs()について→abs/labs/fabs関数

それではまた明日。

[競技プログラミング][C言語][AOJ0003]Is it a Right Triangle?

AIZU ONLINE JUDGE http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0003&lang=jp

Is it a Right Triangle?

1000 以下の３つの正の整数を入力し、
それぞれの長さを３辺とする三角形が直角三角形である場合には YES を、
違う場合には NO と出力して終了するプログラムを作成して下さい。

Input

複数のデータセットが与えられます。１行目にデータセット数 N が与えられます。
続いて N 行の入力が与えれます。各行に３つの整数が１つのスペースで区切られて与えられます。

Output

各データセットごとに、YES または NO を１行に出力して下さい。

回答：AOJ/vol0/AOJ0003.cpp at master · wada811/AOJ
スワップして三平方の定理で判定するだけの簡単なプログラム。

それではまた明日。

[競技プログラミング][C言語][AOJ0002]Digit Number

AIZU ONLINE JUDGE http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0002&lang=jp

Digit Number

与えられた２つの整数 a と b の和の桁数を出力して終了するプログラムを作成して下さい。

Input

複数のデータセットが与えられます。各データセットは１行に与えられます。
各データセットは２つの整数 a と b が１つのスペースで区切られて与えられます。
入力の終わりまで処理して下さい。a と b は非負の整数とします。

Output

各データセットごとに、a + b の桁数を出力して下さい。

回答：AOJ/vol0/AOJ0002.cpp at master · wada811/AOJ
久しぶりにC言語やると忘れがちなのが、scanfで読み取れる限りwhileループで処理する方法。

while(scanf("%d %d", &a, &b) != EOF){
}

というかいい加減C言語もツライし他の言語で標準入出力できるようにならないと。
Javaで標準入出力覚えちゃうのが一番早いんだろうなー。
AOJがD言語も使えるようになってたから覚えとくと色々広がりそう(読者層的な意味で)

[競技プログラミング][C言語][AOJ0001]List of Top 3 Hills

AIZU ONLINE JUDGE http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0001&lang=jp

List of Top 3 Hills

山や丘の高さをメートル単位で 1 から 10,000 までの範囲の整数で表した 10 個のデータがあります。
その 10 個のデータを読み込んで、その中で、高い順から３つ出力して終了するプログラムを作成して下さい。

Input

山の高さ１（整数）　
山の高さ２（整数）　
.
.
山の高さ１０（整数）　

Output

最も高い山の高さ
２番目に高い山の高さ
３番目に高い山の高さ

回答：AOJ/vol0/AOJ0001.cpp at master · wada811/AOJ · GitHub
これもバブルソートで高いのを取ってくるだけ。
プログラミングの宝箱 アルゴリズムとデータ構造を参考にバブルソートの書き方を変えた。

int i;
int height[10];
int temp, flag;

do{
    flag = 0;
    for(i = 0; i < 9; i++){
        if(height[i] > height[i + 1]){
            flag = 1;
            temp = height[i + 1];
            height[i + 1] = height[i];
            height[i] = temp;
        }
    }
}while(flag);

ネットのそこいらで見たのを真似して書いたのよりコッチのほうが効率が良かったので次からはこの書き方で書く。

[競技プログラミング][C言語][AOJ0000]QQ

AIZU ONLINE JUDGE http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0000&lang=jp

QQ

以下のような表記で、九九を出力して終了するプログラムを作成して下さい。
（×記号の代わりに、小文字の x を使用すること）

1x1=1
1x2=2
.
.
9x8=72
9x9=81

Input

なし

Output

1x1=1
1x2=2
.
.
9x8=72
9x9=81

回答：AOJ/vol0/AOJ0000.cpp at master · wada811/AOJ · GitHub
ただの二重ループ。
vol100の最後より簡単で拍子抜けだった。

それでは。

[競技プログラミング][C言語][AOJ10033]Stacking Blocks II

AIZU ONLINE JUDGE http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=10033

Stacking Blocks II

ロボットを操作して、n個のブロックの山を作る。各ブロックにはアルファベット１文字で示された色が着いている。
ロボットは以下の命令を実行する：

push p c: 色がｃであるブロックをp個目の山に積む
pop p: p個目の山の頂点からブロックを１つ取り除く
move p1 p2: p1個目の山の頂点からブロックを１つ取り除き、それをp2個目の山に積む
quit: 終了する
最初、すべての山は空（から）である。

ロボットへの命令を読み込んで、pop命令によって取り除かれたブロックの色を順番に出力するプログラムを作成せよ。

Input

最初の行に山の数nが与えられる。続いて、命令の列が与えられる。
１つの命令が１行に与えられる。命令の種類は上述した通りである。
ブロックの色ｃは、aからzまでのアルファベットで与えられる。p, p1, p2は1からnまでの数字で与えられる。

quit命令でプログラムを終了せよ。

Output

取り除かれたブロックの色を順番に出力せよ。１つの色を１行に出力せよ。

Constraints

山に含まれるブロックの数が1000を超えることはない。

山の数が100を超えることはない。

誤った命令は与えられない。

回答：AOJ/vol100/AOJ10033.cpp at master · wada811/AOJ
前回のやつから山の数が増えて二次元配列になっただけ。
これも先頭にpushしてたりするので末尾に追加するように書き換えたい。

これでAOJ/Vol100シリーズは終わり。
とりあえずAOJは放置で溜まったネタの消化とAtCoderへの挑戦で更新していこうかな。
あとCDT導入して記事でも書こうかな。

それではまた明日。

[競技プログラミング][C言語][AOJ10032]Stacking Blocks I

AIZU ONLINE JUDGE http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=10032

Stacking Blocks I

ロボットを操作して、ブロックの山を作る。各ブロックにはアルファベット１文字で示された色が着いている。
ロボットは以下の命令を実行する：

push c: 色がｃであるブロックを山に積む
pop: 山の頂点からブロックを１つ取り除く
quit: 終了する
最初、山は空（から）である。

ロボットへの命令を読み込んで、取り除かれたブロックの色を順番に出力するプログラムを作成せよ。

Input

入力は命令の列からなる。１つの命令が１行に与えられる。命令の種類は上述した通りである。
ブロックの色ｃは、aからzまでのアルファベットで与えられる。

quit命令でプログラムを終了せよ。

Output

取り除かれたブロックの色を順番に出力せよ。１つの色を１行に出力せよ。

Constraints

山に含まれるブロックの数が1000を超えることはない。

誤った命令は与えられない。

回答：AOJ/vol100/AOJ10032.cpp at master · wada811/AOJ
データ構造とアルゴリズムをちゃんと勉強したことがないので自分で作ってみるのは楽しかった。
添字が小さい方に詰めていく形のスタックです。今思えば末尾に追加するほうが良いのでは？
時間があったら作りなおしてみようかな。

それではまた明日。

[競技プログラミング][C言語][AOJ10031]Search II

AIZU ONLINE JUDGE http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=10031

Search II

n個の整数を含む集合Sと、q個の異なる整数を含む集合Tを入力とし、
Tに含まれる整数の中でSに含まれるものの数Cを出力するプログラムを作成せよ。

Input

１行目にn、２行目にSを表すn個の整数、３行目にq、４行目にTを表すq個の整数が与えられる。

Output

Cを１行に出力せよ。

Constraints

n ≤ 100000, q ≤ 50000 とする。

回答：AOJ/vol100/AOJ10031.cpp at master · wada811/AOJ
個数が一気に多くなったのでクイックソートしてから比較することにした。

それではまた明日。

[競技プログラミング][C言語][AOJ10030]Search I

AIZU ONLINE JUDGE http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=10030

Search I

n個の整数を含む集合Sと、q個の異なる整数を含む集合Tを入力とし、
Tに含まれる整数の中でSに含まれるものの数Cを出力するプログラムを作成せよ。

Input

１行目にn、２行目にSを表すn個の整数、３行目にq、４行目にTを表すq個の整数が与えられる。

Output

Cを１行に出力せよ。

Constraints

n ≤ 100, q ≤ 100 とする。

回答：AOJ/vol100/AOJ10030.cpp at master · wada811/AOJ
個数がそんなに大きくないので適当にループで総当りでも大丈夫。

それではまた明日。

[競技プログラミング][C言語][AOJ10029]Sort II

AIZU ONLINE JUDGE http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=10029

Sort II

与えられたｎ個の数字を昇順に並び替えて出力するプログラムを作成せよ。

Input

１行目にｎが与えられる。２行目にｎ個の数字が空白区切りで与えられる。

Output

昇順に整列したｎ個の数字を空白区切りで１行に出力せよ。

Constraints

ｎの値は1,000,000以下と考えてよい。

回答：AOJ/vol100/AOJ10029.cpp at master · wada811/AOJ
問題文はSort Iと同じだが、ｎの値は1,000,000以下と大きくなっている。
バブルソートでは実行時間が長すぎてタイムアウトするので
より速いソートアルゴリズムの採用が必須。
クイックソートもちゃんと使うのが初めてなので、C言語 qsort.クイックソートとかを参考にした。

それではまた明日。

[競技プログラミング][C言語][AOJ10028]Sort I

AIZU ONLINE JUDGE http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=10028

Sort I

与えられたｎ個の数字を昇順に並び替えて出力するプログラムを作成せよ。

Input

１行目にｎが与えられる。２行目にｎ個の数字が空白区切りで与えられる。

Output

昇順に整列したｎ個の数字を空白区切りで１行に出力せよ。

Constraints

ただし、ｎの値は1000以下と考えてよい。

回答：AOJ/vol100/AOJ10028.cpp at master · wada811/AOJ
まずは単純にバブルソートを書くだけ。
実はちゃんとバブルソートを書いたの初めてだった。

それではまた明日。

[競技プログラミング][C言語][AOJ10027]Card Game

AIZU ONLINE JUDGE http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=10027

Card Game

太郎と花子がカードゲームをする。二人はそれぞれn枚のカードを持っており、nターンの勝負を行う。
各ターンではそれぞれ１枚ずつカードを出す。
カードにはアルファベットからなる動物の名前が書かれており、辞書順で大きいものがそのターンの勝者となる。
勝者には３ポイント、引き分けの場合にはそれぞれ１ポイントが加算される。

太郎と花子の手持ちのカードの情報を読み込み、ゲーム終了後のそれぞれの得点を出力するプログラムを作成せよ。

Input

一行目にカードの数ｎが与えられる。続くn行に各ターンのカードの情報が与えられる。
１つ目の文字列が太郎のカードに書かれている文字列、２つ目の文字列が花子のカードに書かれている文字列である。

入力で与えられるｎが1000を超えることはない。また、与えられる文字列の長さは100以下である。

Output

１つ目の数字が太郎の得点、２つ目の数字が花子の得点として１行に出力せよ。
２つの数字の間に１つの空白を出力せよ。

回答：AOJ/vol100/AOJ10027.cpp at master · wada811/AOJ
ただの文字列比較で特に何も面白みはないかな。

それではまた明日。

[競技プログラミング][C言語][AOJ10026]Standard Deviation

AIZU ONLINE JUDGE http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=10026

Standard Deviation

n 人の学生を含むクラスでプログラミングの試験を行った。それぞれの得点をs1, s2 ... snとしたときの、標準偏差を求めるプログラムを作成せよ。

得点の平均値をｍとすれば、分散α2は以下の式で得られる：

α2 = (∑ni=1(si - m)2)/n

分散の正の平方根が標準偏差αとなる。

Input

複数のデータセットが入力として与えられる。各データセットは以下の形式で与えられる：

学生の数 n
s1 s2 ... sn
n が 0 のとき入力の終わりとする。

入力で与えられるｎが1000を超えることはない。

Output

各データセットに対して、標準偏差を１行に出力せよ。ただし、0.0001以下の誤差があってもよい。

回答：https://github.com/wada811/AOJ/blob/master/vol100/AOJ10026.cpp
標準偏差の式がわかっているので、それに合わせてプログラムを組むだけ。
平均を出す時のキャストは片方だけでも良かったんだっけな。
計算時に大きい方の型に自動でキャストされるんだったような気がする。

それではまた明日。

[競技プログラミング][C言語][AOJ10025]Triangles

AIZU ONLINE JUDGE http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=10025

Triangles

三角形の２辺 a, b とその間の角 C から、その三角形の面積 S、周の長さ L, a を底辺としたときの高さ h を求めるプログラムを作成して下さい。

Input

a の長さ, b の長さ, Cの大きさ（度）（整数）が空白区切りで与えられます。

Output

S, L, h をそれぞれ1行に出力して下さい。0.0001以下の誤差があってもよいものとします。

回答：AOJ/vol100/AOJ10025.cpp at master · wada811/AOJ

それぞれの式は上の画像の通り。
円周率πの定数M_PIはコメントのサイトにあるように、以下の一行目の記述で使えるようになる。

#define _USE_MATH_DEFINES
#include <math.h>

それではまた明日。

[競技プログラミング][C言語][AOJ10024]Distance

AIZU ONLINE JUDGE http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=10024

Distance

２点 P1(x1, y1), P2(x2, y2) の距離を求めるプログラムを作成せよ。

Input

x1, y1, x2, y2 （実数）が空白区切りで与えられます。

Output

P1とP2の距離を実数で１行に出力して下さい。0.0001以下の誤差があってもよいものとします。

回答：AOJ/vol100/AOJ10024.cpp at master · wada811/AOJ
二点間の距離ということで中学数学さえ覚えていれば、あっという間に出来る。

それではまた明日。