解法 除外する二点を考えた上で、一回り大きい領域を二重ループから算出するだけ。反省 問題文の誤読の連続だった。 正方形なのに長方形だと勘違いしたり、N-2個は完全に内部だが、残りの２個は境界上にあるか内部かのどちらかだと勘違いしていてライターさ…

解法１ 牽牛と織姫とをつなぐ線分と、三角形の３つの線分との交差を判定しカウントする。 一回の交差のみなら "OK" それ以外の回数の交差なら "NG" と出力する。解法２ 牽牛と織姫が、三角形の内部か外部かで同じ場所にいるかどうかを判定すれば良い。 例え…

問題 どの隣も同じ文字にならない文字列をLuckyStringと呼ぶ。 入力の文字列sを並び替えたとき、LuckyStringはいくつ生成できるか。 ただし文字列が10文字以下である。解法 階乗を含むオーダー計算が正しく出来ますかという問題。 10! = 3628800 #include<bits/stdc++.h> us</bits/stdc++.h>…

解法 bitDPで解く。 dp[S] := 状態Sでステージを全てクリアするのにかかる最小時間 dp[0] = 0 for S[0, 1<

解法 行の赤丸の数で降順sortする。全ての列の一つの赤丸で一行を丁度全て使いきったなら正しい。それをすべての行でループする二重ループ。 このGreedyで何故一意に復元できると言えるのかはわからない。 int n, row[10000], col[10000]; bool solve() { so…

解法 BFS (or Warshall-Floyd) BFSではノードの接続を隣接行列でなくて連結リストにして解いたけどその必要はあったのだろうか。 因みにnは100以下なので、コストを1に定めて Warshall-Floyd しても解ける。この方が実装が短いし、一度最短路を求めればクエ…

解法 蟻本の反転の考え方を使う。最上部を踏むか踏まないか2^10で決め打ちし、2段目からはマスの一つ上が 1 であるなら 0 に埋めることを 9*10回 繰り返す。反転のオーダーは O(M*N*2^N)蛇足 Emacsのゲームにある 5x5 で遊んだらイメージがしっかり掴めて実…

解法 典型の配るDP。ジャンプ後の位置に障害物がある場合を見逃さないようにする。 あと問題文に書かれているけれど、ジャンプ台に乗って Y を超えるようなケースも注意。 自分は斜めからスキー台に侵入する場合分けが面倒になりそうだと思ったので直進を0, …

解法 １．先ず太郎と鬼を結ぶ線分と円の中心点との距離を求める。 線分のベクトルと線分の端点と円の中心を結ぶベクトルのなす角が鈍角なら、線分と円の中心点との距離は、鈍角になる線分の端点と円の中心点との２点間の距離に当たる。鈍角の判定は内積が負…

解法 BNFが与えられるので、そのとおりに実装する。ただし substr() で時間がかかるためメモ化する。 BNFの実装方法は、自分は 'e' の位置を全て調べて正しい構文かどうかを再帰で繰り返し判定し、一つでも正しいパターンがあればその文字列はBNFによって正…

解法 二つの文字列を選んで、そのうち一つの区切る位置を決めて反転させる。これと他方の文字列が一致したらカウントする。 #include<bits/stdc++.h> using namespace std; // rep #define REP(i,a,b) for(int i=a;i<b;i++) #define rep(i,n) REP(i,0,n) class FoxAndWord { public: int howManyPairs(vector <string> words) { int result = 0; rep(i, words.size()-1) { REP</b;i++)></bits/stdc++.h>…

解法 Xが負であることが保証されるので、正の数×負の数のペアでなければ必ず解に含まれる。また与えられた数列は必ず偶数個の要素であるので、正の数×負の数のペアが現れる場合は、正の数と負の数がそれぞれ奇数個の場合で、この一個だけが解に関わる。解く…

解法 本が全て「入りきる」または「入りきらない」を評価の条件として、本棚の幅を二分探索により求める。本棚の幅が正の整数の増加列の中の値であることから、この数列のうちで解を仮定して二分探索をすることができる。二分探索の基本問題。 #include <bits/stdc++.h> usi</bits/stdc++.h>…

解法 先にハミング数を全列挙してクエリに答える。 2と3と5の数を決めうちして列挙する。重複を許さないように、得られた値は set に詰める。 2^20 が100万を超えるので、2, 3, 4 は 20 個まで選択すれば十分。 #include <bits/stdc++.h> using namespace std; set<int> hamming;</int></bits/stdc++.h>…

解法 メモ化した愚直な素数判定。エラトステネスの篩でも良い。反省 はじめnの制約を見てなかったので愚直のisPrimeでTLEだったが、実行時間は4秒ほどだった。これならメモ化で十分かとなり、コードを書き直す必要はなかった。 #include<bits/stdc++.h> using namespace std</bits/stdc++.h>…

解法 やるだけシミュレーション。注意すべきところは思いつかない。反省 はじめused配列をboolで宣言してたにも関わらずintとして利用してた。 それを直してサンプル通って提出したらWAでおかしいと思ったら3x3の中で数にダブりがないかチェックする作業忘れ…

問題概要 'L','O','V','E'の頻度を調べて、与えられた式によって得点を最大化せよ。解法 概要の通りの実装。 class LoveCalculator { public: int calc(int l, int o, int v, int e) { return ((l+o)*(l+v)*(l+e)*(o+v)*(o+e)*(v+e))%100; } string findBoy(…

以下のコードで通る問題。 class DesignCalendar { public: int gcd(int a, int b) { if(b==0) return a; return gcd(b, a%b); } int shortestPeriod(int d, int y) { return d/gcd(d, y); } };

解法 購入するそば粉がちょうど入力と一致するとき買うことが出来る。 ナップザックでDPしても解けるが、入力は 500 〜 5000g の間で、100g 刻みで与えられると書かれているので全探索でも解くことが出来る。それぞれの店で購入するそば粉の量の単位を三重ル…

問題 Aの発生と消失の中でBが可能か判定するタイプのシミュレート問題（参考: AOJ0231 Dangerous Bridge）解法 pair(時間, 種類) で入力を vector > につめる。シミュレートに queue を使う。 #include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std;</queue></vector></algorithm></iostream>…

問題文 http://uva.onlinejudge.org/external/4/440.html問題概要 1からNまでの数列それぞれにランダムに対応させた地域のネットを遮断していく。方法は公平性を極めたいので、遮断の順序にランダム性を導入する。ランダム性は、数列を循環させた上ではじめ…

問題文 http://uva.onlinejudge.org/external/4/400.html問題概要 ls コマンドで出力されるような表を実装せよ。ファイル名がある部分だけ、全ての項目を最も長いファイル名 + 2 まで空白で埋める。'-' は丁度60文字である。解法 行と列のサイズ設定が一番詰…

問題概要 会社でX人運べるシャトルバスを数台雇いたい。このシャトルバスを雇う費用は一台 baseCost + X * seatCost で計算される。各地点に住む従業員数が vector cnt で与えられるので、すべての従業員を運ぶようにしたとき会社の負担する費用の合計を最小…

解法 ワーシャルフロイドした後、１つ中継点を決めてソースから２つのシンクまでのコストの和を最小化する。 中継点を k とすると、 cost[S][k] + cost[k][g1] + cost[k][g2] とすればコストの和が求まるので、forループで和が最小となる k を決める。反省 …

解法 ２円の交点を全て求めて、交点の集合を得る。その交点それぞれがどの円に含まれるかを全て調べ、含む円の数をカウントし最大値を求めれば良い。 ２円の交点を求める際、complex の polar が便利。polar(r, θ) で、対応する複素平面における座標が求まる…

問題概要 数直線上にいる複数の猫が、それぞれの与えられた初期位置から絶対値Xだけ移動する。猫が最適な動き方をしたとき、猫のいる区間の中で最も端にいる２匹の距離を最小化せよ。解法 どの２匹が区間の端になるかを二重ループで決める。このときすべての…

問題概要 与えられた文字列から同種の文字を全てを削除することを任意回数繰り返す。残った文字列から "CAT" を作れるなら "Possible" 作れないなら "Impossible" を出力せよ。解法 与えらた文字列Sの中の文字を初めから見ていき、'C', 'A', 'T' のときだけ…

問題概要 トーナメント戦で自分とライバルが当たるのは何ラウンド目か求めよ。ライバルと当たるまでの試合は互いに全て勝つものとする。解法 自分とライバルの位置だけtrueにしたvectorを用意し、vectorの隣同士で比較し、論理和を取りながらtrue同士が衝突…

解法 探索やるだけ。ブロックの位置と色をうまくグリッドに記録する。初期位置の色と同じ色を辿るように判定する。BFSで解いたけど普通にDFSの再帰で問題ない。反省 簡単...のはずが2x4の長方形を2x3で実装してて、生成したマップがおかしくて優に1時間くら…

問題概要 単位あたりのXY移動量が与えられるので、初期位置から進んで辿りつけない場所があるならそれを判定せよ。そのような場所がない場合はゴールの位置として最も遠くなるもののコストを算出せよ。解法 指定の初期座標からBFSをし尽くしたときに、まだ訪…