POJ1065 http://poj.org/problem?id=1065 DP問題の練習です。 ソートして順次大きい方からつなげていけば終わりです。 久しぶりだったのでc++のいろいろな書き方忘れちゃって時間かかりました。 あと、終わってから気づいたのですが、subsetはvectorである必…

POJ1742 1742 -- Coins 今回もDPの練習です。 最初は入れ子ループを何重にも張り巡らしてしまい、タイムアウトしてしまいました。 あとコインが何枚残っているかをメモすれば効率化を計れるんですね。 蟻本で読んだ覚えがあってもいざ自分で実装するとなると…

POJ2385 2385 -- Apple Catching DPの練習問題です 最初問題を読み間違えて、Wを移動してからW分待つと再び移動できるようになると解釈して、一時間くらい悩みました。 英語力の欠如です。 問題の正しい理解ができてからは比較的すぐに実装することができま…

POJ2393 2393 -- Yogurt factory 一週間ぶりくらいですね 今回は貪欲法の練習として解きました ヒントに32bitより大きい整数になるかもしれないぞって書いてあるのにそれに気づかず悩んでました。 考え方としては、その週で買ったコストと保存しておくコスト…

POJ3187 3187 -- Backward Digit Sums 今回も全列挙の練習です。 こちらの方は前回のようなめんどくさい入力もなく、ただ問題の通りに処理するだけで済みました。 前回覚えたnext_permutationくんにまた頑張ってもらった。 next_permutationくんって辞書順に…

POJ2718 2718 -- Smallest Difference 全列挙の練習です。 この問題は各データセット内の入力の回数が与えられていないため、入力のところで無限に時間を食いました。 結局、iostreamを使用して、空白を削除しました。 最初は入力されたデータセットをグルー…

AOJ0525 おせんべい | Aizu Online Judge 深さ優先探索 お煎餅を行で裏返すか裏返さないか、$2R$回探索するだけ。 色々考えた結果、裏返さない場合と裏返す場合の煎餅の並びを先に計算しておいて、各行について裏返すか裏返さないかのフラグを入れていった。…

AOJ0558 チーズ | Aizu Online Judge 幅優先探索の練習第二弾です。 こちらは方針がすぐにたち、2,30分くらいで書きました。 が、枝刈りしてなかったので大きいデータに殺されましたﾁｰﾝ すでに通った座標をキューに入れないように書いたのですが、条件式のx…

AOJ0121 7 パズル | Aizu Online Judge 幅優先探索の練習です。 入出力のところで戸惑いました。 iostreamを使わなきゃいけないんですかね。。。？ 今回は方針が全然立ちませんでした。 最初、それぞれのデータセットに対して毎回計算させてました。 最初に…

AOJ0033 玉 | Aizu Online Judge 深さ優先探索の練習第二弾 今回は割とすぐ解法が思いつきました。 解答時間は25分でした。 solveでどこでreturn falseすればいいのか迷いました。 以下コードです。 #include <stdio.h> int n; int data[10]; int ans[100]; bool solv</stdio.h>…

AOJ0118 財産分配 | Aizu Online Judge 深さ優先探索の練習として解きました。 うる覚えの深さ優先探索だったので解答時間は1時間でした。 最初、dfsの中に一緒にsumを計算させようとして、うまくいきませんでした 以下、コードです #include <stdio.h> int h, w; cha</stdio.h>…