JOI 2012-2013 問3 Signboard

int main() { int res = 0; int n; string s, a; cin >> n >> s; for(int i = 0; i < n; i++) { cin >> a; bool f = false; for(int j = 0; (j < a.size()) && !f; j++) //始点を決める if(a[j] == s[0]) // 間隔を決める for(int k = 1; (k < a.size()) && …

AOJ 0561 Books

反省 dp[i][j][l] := 今までにi冊売り、今見ているジャンルjの本をl個売った時の最大の買取価格 最初はこれでDPしようとしたが、メモリが確実に収まらないのは自明だし(それでも頑張って削減して通そうとしたが)、書いている途中でlがいらないのにも気づいて…

AOJ 0568 Pasta

前の状態2つ考えないといけないと思ってたけど,1つで十分だった. やっぱメモ化再帰のほうが何も考えずに書ける. dp[i][j][k] := i日目にjのパスタをk個連続で作ったとき,i日目までの条件を満たす予定の数 n日目までの条件を満たす予定の数 ∋ i日目までの条…

AOJ 0536 Shuffle

汚い ソースコード typedef pair<int, int> P; int main() { int n, m, p, q, r, x, y; while(cin >> n, n) { vector<P> cards; cards.push_back(make_pair(1, n)); cin >> m >> p >> q >> r; while(m--) { // flag : 0 => Left, 1 => Middle, 2 => Right int flag = 0; v</p></int,>…

ADLSI : 連鎖行列積

参考:アルゴリズムイントロダクション15章 動的計画法 コード中のコメントはここに書いてあることです…。 勘違いしてるかもしれません… ソースコード /* 連鎖行列積問題 演算結果はカッコ付けの順序にはよらないが、カッコ付けの順番には依存する ー>乗算回…

無線LANが不安定なときの対処

環境 OS Windows7 無線LANアダプタ Atheros AR9485WB-EG 全然Windowsとか使ったことなかったし、無線LANアダプタとかナニソレ状態だったんですが、まぁ上手く接続できたのでまとめときます。 いろんなことを試したのですが、最終的にドライバを更新すること…

AOJ 0150 Twin Prime

方針 素数判定してから愚直に求める. コード int main() { fill(is_prime, is_prime + 10001, true); is_prime[0] = is_prime[1] = false; for(int i = 2; i < 10001; i++) if(is_prime[i]) for(int j = i * 2; j < 10001; j += i) is_prime[j] = false; int…

AOJ 0135 Clock Short Hand and Long Hand

方針 実際に時計の絵を書いて適当に変換して,式出して求める。 コード int main() { int n; double h, m, hr, mr, diff, res; cin >> n; for(int i = 0; i < n; i++) { scanf("%lf:%lf", &h, &m); hr = (30.0 * h) + (m / 2.0); mr = m * 6.0; diff = abs(h…

AOJ 0244 Hot Spring Trip

方針 深さ優先探索. 特殊な切符を使って頂点nにたどり着いた時の最小コストがdict[0][n],使わなかったときdict[1][n]です. コード const int INF = 1 << 30; int N, M; int G[100][100]; int dict[2][100]; vector<int> A[100]; //n:今の場所 //c:特殊な切符 //</int>…

AOJ 0223 Stray Twins

方針 ちゃんと問題文を読まなければいけない(反省). というより,なんで座標(1, 1)から始まるんだ(憤怒). 幅優先探索です. コード const int dx[][4] = {{1, 0, -1, 0}, {-1, 0, 1, 0}}; const int dy[][4] = {{0, 1, 0, -1}, {0, -1, 0, 1}}; int X, Y; boo…

AOJ 0220 Binary Digit A Doctor Loved

方針 深さ優先探索です.全探索なので頭悪い解法かなと思いながらもたかだかO(2^12)っぽいので余裕だろーとか思いながらやりました. コード double n; double x[12]; int tmp[12]; int ans[12]; void dfs(int p, double sum) { if(sum > n || p > 12) retur…

AOJ 0207 Block

方針 自分で処理しやすいようにマップ作っていって,始点の位置にある色と同じ色を始点と接している場所から塗りつぶしていく. コード typedef pair<int, int> P; const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; int w, h, xs, ys, xg, yg, n; int m[128][1</int,>…

AOJ 0191 Baby Tree

方針 メモ化再帰. memo[i][j] := j番目の肥料を直前に与え,i回目の肥料を与える時の成長度の最大値 ソースコード double g[128][128]; double memo[128][128]; int n, m; double dfs(int c, int prev) { if(c == m) return 1.0; if(memo[c][prev] != -1) re…

AOJ 0154 Sum of Cards

方針 メモ化再帰. 主に下準備で面倒くさいコードになってしまいました. コード int memo[8][1024]; struct card { int value; // 値 int resid; // 残数 card(int a, int b) : value(a), resid(b) {} }; void input(int m, vector<card>& cards) { int a, b; for(i</card>…

AOJ 0089 The Shortest Path on A Rhombic Path

方針 再帰をしろという天からの声が聞こえた気がしたので,再帰を書いたのですがなぜか通らず. ということでfor文に直して解きました. dp[i][j] := i段目j個目まで選んだときの最大の値 半分より上の時と下の時で進む方向が変わるので注意です. コード int…

K2PC Easy

結果 下らないミスして3完でしたが, しなくても3完です. A - ハンバーガー(Hamburger) 方針 問題文通りにやれば通る コード int main() { int n; int a, b, c; cin >> a >> b >> c; cin >> n; int _a = n, _b = 2 * n, _c = 3 * n; cout << (_a - a <= 0 ? 0…

AOJ 0033 Ball

友人が解いていたので再び解いてみた. 方針 全探索しました.O(2^10)かな. #include <iostream> #include <vector> #include <algorithm> #include <cstdio> using namespace std; int ball[10]; bool dfs(int i, int prevLeft, int prevRight) { if(i == 10) return true; if(prevLeft < ball[i]) </cstdio></algorithm></vector></iostream>…

Mail.appでhotmailを送受信できるようにする

ちょっとだけ詰まったのでメモ 環境 Mac OS X 10.8 受信用メールサーバ pop3.live.com 送信用メールサーバ smtp.live.com 送信用メールサーバの設定の詳細 デフォルトポートを使用からカスタムポートを使用にする(ポートは587) 認証をパスワードにする. Appl…

AOJ 0180 Stellar Performance of the Debunkey Family

方針 最小全域木。 AOJ 0072 Carden Lantern - Allen' Memoと一緒です。 const int INF = 1 << 30; int V; int cost[100][100]; int mincost[100]; bool used[100]; int prim() { int res = 0; mincost[0] = 0; while(1) { int v = -1; for(int u = 0; u < V…

AOJ 0072 Carden Lantern

方針 最小全域木問題。 プリム法で解いています 蟻本と一緒です。 const int INF = 1 << 30; int cost[100][100]; int mincost[100]; bool used[100]; int V; int prim() { int res = 0; mincost[0] = 0; while(1) { int v = -1; for(int u = 0; u < V; u++)…

SRM 550 EasyConversionMachine

問題概要 サンプルセット見れば分かる. kが与えられる.k回文字列oから1文字変化させることができる.k回でその操作を行った時文字列fと等価になれば,"POSSIBLE". ならなければ"IMPOSSIBLE" 方針 まずoがfと等価になるときの最小限の変化させた数cを求める. そ…

AtCoder Regular Contest #006

結果 3完でした。もうちょっとよく考えたらD解けたかもしれないなぁ A - 宝くじ うわぁめんどくさい実装問題だなぁとか思ってクソ汚いコードを提出した。 int e[10]; int l[10]; int main() { int count = 0, b, tmp; for(int i = 0; i < 6; i++) { scanf("%…

SRM 403 TheLuckyNumbers

問題概要 サンプルセット見れば分かる. aとbが与えられる. 4と7で構成されている数の内, [a, b]に存在する数を求める 方針 再帰で4と7をつなぎ合わせていったら解けると予想. 引数にstringを持ってくる. b a d _ a l l o c素直に整数で実装すると通ります. …

SRM 403 TheLargestLuckyNumbers

問題概要 サンプルセットを見ると問題文が分かる nが与えられる。4と7で構成されるn以下の数を求める. 方針 最初のsubmit nは[4, 1000000]なので全探索 Medium解き終わってからのsubmit 幅優先探索 class TheLargestLuckyNumber { public: int find(int n) {…

SRM 548 KingdomAndTrees

問題概要 数列xが与えられる. x[i]を[max(1, x[i] - m), x[i] + m]の範囲で置き換えることができる. xが単調増加になることを満たす時の最小のmを求める. 方針 二分探索でmを求める. mで単調増加な数列が作れるかどうかは貪欲に求まる. class KingdomAndTree…

AOJ 0242 Input Candidates

問題概要 読める 方針 stringstream便利. multimapで自動的にソートしてもらうようにした. int main() { int n, i; char k; string s; vector<string> vs; map<string, int> ms; multimap<int, string> mi; while(~scanf("%d", &n), n) { cin.ignore(); for(i = 0; i < n; i++) { getline(cin, </int,></string,></string>…