読者です 読者をやめる 読者になる 読者になる

CodeRunner 2014 予選A 辞書ゲーム「Dic Hack」

問題 ログイン - CODE RUNNER ある文字列を送るとスコアがもらえる。スコアを最大化したい。 生い立ち 今まで普通のプログラミングコンテストにしか参加したことなかったのでマラソンとか初めてでした。 最初、入力もないのでどうすればいいのわからなかった…

AOJ JOI 2013,2014

予選4完、本選2完です。たしか本選Aランクが220点以上だったと思います。 0592 Average Score やるだけ。下を40にそろえて平均を出す。 0593 Vote 面白い競技の順に走査してく 0594 Super Metropolis 幅優先探索で解こうとしたけど、無理。普通に計算で解け…

動的計画法のお勉強と学ぶためのリソース

8月に入ったら情報オリンピックの過去問を解いてく予定なので動的計画法が使えないとどうにもならないと思い、勉強します。題材は蟻本の01ナップサック問題から ナップサック問題 重さと価値がそれぞれw_i, v_iであるようなn個の品物があります。これらの品…

AOJ 1091 KND is So Sexy

問題 KND is So Sexy。 解法 シュミレーション問題です。 ヘロンの公式っての使った。あとは三角形の周長が同じ場合は正三角形が一番大きくって一辺が固定されているなら2等辺三角形が極大。知りませんでした。 コード int main(){ double a, l, x; while(~…

AOJ 1016 Fibonacci Sets

問題 Fibonacci Sets f(i) = f(i-1) + f(i-2) フィボナッチ数です。で、1001で割って。 i...Vのノードがあって、iとjが | F(i) - F(j) | < d ならiとjは同じ集団に属している。 集団の数はいくつか 解法 Union_Find木を使うと解けます。 蟻本の出番。 コード…

AOJ 1127 Building a Space Station

問題 たくさんのなんかコロニーみたいなのがあって、全部のコロニーに行ったり来たりできるようにしたい。 各コロニーのx,y,z座標と半径rが与えられるのでコロニー間に設置する道の最短総距離を求める。 解法 似たような座標から距離求めて最短経路を求める…

PKU 1007 DNA Sorting

問題 DNA Sorting 解法 ソートするだけの問題。 逆順になっている要素を数える。 コード int n, m; char c[64]; bool cmp(const string &a, const string &b){ int ac = 0, bc = 0; rep(i, a.size()){ REP(j, i, a.size()){ if(a[i] > a[j]) ac++; if(b[i] >…

AOJ 0190 Eleven Puzzle

問題 Eleven Puzzle。 解法 BFSだと間に合わない。地球は爆発しないよね。 id:nanikakaさんのはてなダイアリーで両側探索というものがあるのを知った、 実装はJavaだったので見ずに勘で実装してみた。 一発AC。 嬉しかったです。 コード vi p, next, now; ve…

PKU 1005 I Think I Need a Houseboat

問題 (http://poj.org/problem?id=1005)。翻訳されてます。 解法 (0,0)から家までの距離を求めて、円の半径がそれを超えたら浸食される。 コード double x, y, d; int N; int main(){ scanf("%d", &N); rep(i, N){ scanf("%lf%lf", &x, &y); d = sqrt(x*x+y*…

PKU 1002 487-3279

問題 (http://wikiwiki.jp/pku/?1002%20487-3279)。 解法 map使うと簡単、入力を全部数えていって、複数あるやつだけ表示させる。 cin使うとTLEになった コード int n; vector<string>s; char in[100]; int main(){ map<char, int>m; m['A'] = m['B'] = m['C'] = '2'; m['D'] = </char,></string>…

PKU 1003 Hangover

問題 Hangover。 日本語訳。 解法 カードを落とさないように重ねていくクイズみたいなの解いたことあったような気がする。 カードが1枚から一つずつ増やしていって、つ長さを超えるのか計算していきます。 コード double d; int main(){ while(scanf("%lf", …

AOJ 0151 Grid

問題 Grid。 解法 縦横斜めで走査していって1の数をカウントする 斜めに走査するループの回し方が自分で書いたのにどうなってるのかよくわからない コード int n; char grid[256][256]; int solve(){ int res = 0, c; rep(i, n){ c = 0; rep(j, n){ if(grid[…

AOJ 0119 Taros Obsession

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0119)。 解法 なんか論理の問題かな、推論とかするのかなと思っていたら、 (きこえますか...あなたの脳内に...直接語りかけています...トロピカル...いえ...トポロジカルソートを使うのです…

AOJ 0157 Russian Dolls

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0157) 解法 DPで解きます。ソートした後最長増加部分列を求めます。 コード int n, m; vector<pi>s; int dp[1024]; int main(){ while(scanf("%d", &n) && n){ s.clear(); int h, r; rep(i, n){</pi>…

AOJ 2153 Mirror Cave

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2153)。 解法 BFSで解く。今まで通った場所を記憶するのにmapを使うとメモリが足りなくなる。 コード int W, H, used[52][52][52][52]; int dy[] = {0,-1,0,1}, dx[] = {-1,0,1,0}; char le…

AOJ 2026 Divisor is the Conqueror

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2026) N枚のカードがあったそれを一枚ずつ出していく。出せるのは今までに出した、カードの総和の約数だけ。 解法 DFSで解く。普通に解いても無理だった。逆から解くとできるんだって コー…

AOJ 1218 Push!!

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1218) 図だけでもなんとか分かるよね。ゴールまで最短で何回動かせばいいか 解法 BFSで動かしていきます。押す方向と逆の方向に人が立てるか、現在いるところからそこにいくことができるか…

AOJ 1103 Board Arrangements for Concentration Games

問題 AからHのカードを並べてく、カードのセットに相対的な位置だけでカウントしていくから AとBのセットをかえても同じ 解法 DFSで解きます。 コード int board[4][4]; int dy[4], dx[4]; int dfs(int n){ if(n >= 8) return 1; int res = 0; int y, x; rep…

AOJ 2011 Gather the Maps!

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2011) 解法 詳しくはhttp://www.deqnotes.net/acmicpc/p0017/。 コード ````cpp int m[64][64], in[64][32]; int main(){ int n, f, day; while(scanf("%d", &n) && n){ memset(m, 0, sizeo…

AOJ 0169 Blackjack

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0169) 解法 DFSが楽。あとは1以外を全部足してから1をどうするかってやる。 コード DFS int a[512], p; int dfs(int n, int c){ if(n > 21) return 0; if(c == p) return n; if(a[c] == 1) …

AOJ 1210 Die Game

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1210) top、north、westはそれぞれ1,2,3とする さいころを指示通りに転がした時、topに来る面は何か? 解法 シュミレーション問題です。 コード int n, top, west, north; string op; int m…

AOJ 0199 Chairs Where Demanding People Sit

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0199。 解法 シュミレーション問題です。 Cの座る条件をいくつか見逃していてWA連発。 『How to Solve It』に問題を理解することって書いてあったのに。 ちゃんと問題を読むようにします コ…

AOJ 0178 TETORIS

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0178。 解法 シュミレーション問題です。 指示通りに処理すればできる高さは十分にとっておかないとRUNTIME ERROR吐かれる コード int t[UNDER+10][5], n; int count(){ int res = 0; rep(i,…

AOJ 1117 Missing Numbers

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1117。 所々、虫食いになってる表が与えられるからそれを埋める。 解法 一カ所だけ?の行(列)なら埋められる。 コード int p, s; char row[10]; int a[128][128], b[128][128]; int main(){ b…

AOJ 1248 The Balance

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1248。 2つの重りと計りたい分量が与えられる。それぞれ重りをいくつ使えば計れるか? 重りはより少なく、軽いものを選ぶ。 解法 aの数、xがでれば、yは一つに定まる。xに関するループを回…

AOJ 0165 Lottery

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0165。 解法 p-m以上p+m以下の素数数えていく。素数を用意する配列にはa[i]、i以下の素数の数を累積和で記録しておかないとTLEになる コード int p[MAX_P], n, sum[MAX_P]; int main(){ p[0]…

AOJ 1214 Walking Ant

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1214。 antが自分の巣に帰る最短距離を求める。四方向に一つ進むのに1timeかかる。初期の体力が6で1timeごとに1ずつ減っていく、食べ物のマスを通ると体力が6になる。 解法 食べ物は2回以上…

AOJ 0156 Moats around the Castle

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0156。 解法 天守閣からBFS、複数続いている堀をその度にカウントしてWAを出していた。 コード nt dx[] = {0,-1,0,1}, dy[] = {-1,0,1,0}; int main(){ int n, m, i, j, d, res; while(scanf…

AOJ 1055 Spider Jin

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0155。 解法 それぞれの距離をはかり、距離が50以下のものだけでグラフを作る。 あとはダイクストラで最短距離を求めて経路復元。 上限が1000なのでO(N2)で十分だと思う。 コード double cos…

AOJ 1044 Camel Case

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1044。 解法 これもシュミレーション問題かな。たぶんそうだと思います。 与えられた文字列の記法が分かれば記法ごとに別の記法に変える。 最初は一緒くたに変換しようとしてWA出してた。 コ…

AOJ 0111 Doctor's Memorable Codes

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0111。 解法 シュミレーション問題かな コード string encode(string code){ map<char, string> m; m['A'] = "00000"; m['B'] = "00001"; m['C'] = "00010"; m['D'] = "00011"; m['E'] = "00100"; m['F'] =</char,>…

AOJ 1008 What Color Is The Universe

問題 |A|と配列Aが与えられる。N[i]はAに含まれるiの数。 N[i] > |A| / 2 を満たす。iを探す。 解法 実装するだけ コード int A, N[1000001]; int main(){ int a, i; while(scanf("%d", &a) && a){ memset(N, 0, sizeof(N)); rep(i, a){ scanf("%d", &A); N[…

AOJ 1084 K Cards

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1084。 日本語 解法 全探索で解けます。計算量はどれくらいなのかな。どうやって表記するのかよくわからない。 単純にループのとこだけでやるとO(n(n-1)/2(n-k))とか?こんな複雑な書き方な…

AOJ 1074 Popularity Estimation

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1074. 日本語。 解法 i秒後に何人映っているかをメモしておけば簡単。やるだけ。 計算量は*O(nm)ぐらいでいいのかな。 コード int main(){ int n, m, d; char name[256]; while(scanf("%d", …

AOJ 2014 Surrounding Area

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2014 日本語。 解法 あるマスからDFSしていって黒に到達したら、1、白に到達したら2って感じにして行く。 dfsの再帰のところを最初+=にしようとしていた コード int f[50][50], c[50][50];…

AOJ 1144 Curling 2.0

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1144&lang=jp 日本語。 解法 DFSで解く。四方向見て、進めるなら進む。盤面の外に行ったら次っていう感じでまわしてく。 コード int w, h; int board[20][20]; int dx[] = {0,-1,0,1}, dy[] …

AOJ 1045 Split Up!

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1045 日本語。 解法 適当にDFSすればできる。 コード int n; int a[128]; int dfs(int p, int g, int c){ if(n == c) return abs(p-g); return min(dfs(p+a[c], g, c+1), dfs(p, g+a[c], c+1…

林晴比古さんのコードが長くて読むのがたいへん

林晴比古さんのC言語による実用アルゴリズム入門読んでいて、電卓プログラム、まねして作ろうかなと思って書き始めたら長くて2ページ目で断念。以前からよく眺めていた、ohahirokiさんの電卓プログラムを頭の中で考えながら簡単な電卓プログラムを実装して…

SRM 619 Div 2

ARCにせよSRMにせよ、記事書くのがだいぶ遅いのはなんとかなりませんかね。 Level 1 GoodCompanyDivTwo Brute Forceで解ける問題っぽいです。システムテストで落とされました。 superior[i] = superior[j]でworkType[i] = workType[j]、同じ上司を持ってる二…

AOJ 2503 Project Management

何のことはない、有効グラフつくってクリティカルパス求めるだけ。 ワーシャルフロイド法でもなんでも解けるんじゃないかな。 int n, m; int cost[400][400]; int main(){ scanf("%d%d", &n, &m); rep(i, n) rep(j, n) cost[i][j] = 0; int a, b, c; rep(i, …

全探索の勉強

今日は深さ優先探索と幅優先探索で1日が終了したみたいです。chokudaiさんのとこのアルゴリズム勉強会でDFSとBFSの講義があったのでまずはスライドで http://www.slideshare.net/chokudai/wap-atcoder2んで、kyuridenamidaさんがまとめてくれていた、典型問…