問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0108 概要 省略 解法 直前の状態を配列に保持して、それぞれの数を数えて配列を更新し、 直前の状態と比較する。 同じだったら終了。sは12までだと思ってたけど違うみたい。 制約をちゃん…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0107 概要 立方体の縦、横、高さの長さが与えられる。 この立方体を半径rの円に接さないように通すことができるか。 解法 立方体の面の対角線が一番小さくなるように向けたとき、 対角線 /…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0106 概要 そば粉をnグラム買いたいと思っている。 3つの店での1袋当たりの単価と、量、 数袋買った時の割引料金が与えられるので、 一番安くなる組み合わせの金額を出力する。 解法 5000g…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0105&lang=jp 概要 語句とページ番号がいくつか与えられる。 辞書順に語句を表示し、対応するページ番号すべてを 昇順で出力する。 解法 STLのmapを使ってやる コード #include <iostream> #include <cstdio></cstdio></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0093 概要 a年からb年までの閏年を求めよ。 解法 is_uruuを実装する コード #include <iostream> using namespace std; bool is_uruu(int y) { return (y % 4 == 0 && y % 100 != 0 || y % 400 == 0)</iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0096 概要 nが与えられたとき、a + b + c + d = n となる組み合わせ数を求めよ。 解法 全探索だと、1000^4 なので間に合わない。DP[i個目][合計]で数え上げをする。 コード #include <iostream> usin</iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0089 概要 ひし形上に並べられた整数が与えられる。 一番上から左下か右下に移動していったとき、 通過した整数の和の最大値を出力せよ。 解法 動的計画法で解く。 コード #include <iostream> #incl</iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0069 概要 あみだくじに、新しく1本線を引いてゴールに行けるか。 解法 左上から、線引けるところを全探索 コード #include <iostream> #include <cstdio> #include <string> #include <cstring> using namespace std; int n, </cstring></string></cstdio></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0057 概要 領域をn本の線で分割する。 このとき、最大の領域の数を求めよ。 解法 n = 1のとき どこに線を引いても領域は2つになります。 n = 2のとき 先ほど引いた線と交差させることで、4…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0056 概要 二つの素数の和がnとなる組み合わせの数を求めよ 解法 素数列挙して、全ての組み合わせを確かめる。 エラトステネスの篩を使って素数を調べる。 コード #include <iostream> #include <cstdio> #in</cstdio></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0054 概要 a / b の小数点第1位から第n位までの値を足せ 解法 最初doubleでやっていたけど、精度で死んだ。aを10倍しながら、bで割っていくと少数部分が計算できるらしい。これは使える。 …

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0016&lang=jp 概要 最初、x=0,y=0でy軸方向に向かって立っている。 現在向いている方向にdisメートル進んで、右にdir度だけ回転する。 数回行い、終了後の座標を出力する。 解法 最初、原点…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0015&lang=jp 概要 80桁までの整数が二つ与えられる。 その和を出力する。 80桁を超える場合は"overflow"を出力する。 解法 unsigned intだと(0 ～ 4294967295) unsigned long longだと(0 ～…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0067 概要 12×12の地図が与えられる。島の数を出力せよ。 解法 深さ優先探索で解く。左上から見ていき、「１」を見つけたら、上下左右に繋がっている場所をすべて「０」にする。最後に島の数…