motu*2

DIV1目指して問題を解き続ける

TopCoder SRM 641 DIV2 Level2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13547 概要 xy平面上にいくつかの点が与えられる。 この点の中から3つ選んで三角形を作った時、 原点が三角形の内部に含まれるような組み合わせが 何通りあるか求めよ。 解法 三角形があ…

TopCoder SRM 640 DIV2 Level2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13557 概要 始めx=1とする。各ステップで2xか、2x+1に値を変えることができ、 最大k-1回までできる。 禁止の値リストがあり、この値にすることはできない。 作れる数字の合計を答える。 …

AOJ 0108 Operation of Frequency of Appearance

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

AOJ 0107 Carry a Cheese

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

AOJ 0106 Discounts of Buckwheat

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

AOJ 0105 Book Index

AOJ

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

C言語で作る五目並べ

初めに 本稿はSLP KBIT Advent Calendar 2014 の12日目の記事です。 前書き 最近競技プログラミングしかやっていなかったので、たまにはGMVらしく ゲームを作りたいと思います。 今回は比較的簡単に作れそうな五目並べをC言語で作ってみたいと思います。 配…

AOJ 0093 Leap Year

AOJ

問題文 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>…

AOJ 0096 Sum of 4 Integers II

問題文 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>…

AOJ 0089 The Shortest Path on A Rhombic Path

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

AOJ 0069 Drawing Lots II

問題文 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>…

AOJ 0057 The Number of Area

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

AOJ 0056 Goldbach's Conjecture

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

AOJ 0054 Sum of Nth decimal places

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

AOJ 0016 Treasure Hunt

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

AOJ 0015 National Budget

AOJ

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

AOJ 0067 The Number of Island

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