問題 http://uva.onlinejudge.org/external/112/11287.html概要 Fermatの小定理：（または） であるが、pが素数でないときこの関係式が成り立つ p を 基数 a における pseudoprimes という。 p が 基数 a における pseudoprimes であるかどうか判定せよ。解…

問題 http://uva.onlinejudge.org/external/113/11350.html概要 走査の方向 'L' または 'R' が書かれるので、Stern-Brocot Tree を親ノードから辿れ。解法 左と右の数字の和を取って木を走査していく。二分探索木である。 図を見ながらコードで確認した方が…

問題 http://uva.onlinejudge.org/external/2/264.html概要 AOJ1007 JPEG Compression の劣化版解法 うまいやり方もあると思うけど、方向で場合分けをして四方向分作り、愚直にプログラムを書けば終わり。 #include <bits/stdc++.h> using namespace std; int main() { int </bits/stdc++.h>…

問題 http://uva.onlinejudge.org/external/2/297.html概要 画像が４分木を用いてモノクロで入力される。２種の画像を合わせたときに塗られたピクセルはいくつあるか解法 １次元配列の 4*深さ+i (1 深さに対応したピクセルの数を配列で持っておくと便利。４…

解法 直前与えた肥料が何であるかが、今回に何を与えるのが最適であるかを決める。 よって、状態として「肥料を与えた回数」と「直前に与えた肥料」を持ち、成長率を最大化するDPをすればよい。 具体的には、k 日目に肥料 j を与えたときの成長率は、k-1 日…

問題概要 アルファベットの大文字で構成された vector が与えられる。この要素の順列から生成される文字列Sのうち、Sを1文字ずつシフトするように回転させたときちょうど K 回転となるものの数を答えよ。制約 vector の要素は 1 〜 8 各文字列は 20 文字まで…

解法 問題の「x+y=a」という式は x-y と x+y を繋げた式。 a を string とみなして切り分ける場所を決める。切り分け方が正しいかどうかのチェックは以下で可能。 切り分けた結果、先頭に0を含まない数字になるかどうか 和より差の方が必ず小さい xとyが両方…

問題 http://uva.onlinejudge.org/external/114/11461.html ２つの正の整数a, b(a, bを含む)の間に含まれる２乗の数を答えよ。解法 整数の間をループで回して調べても良いが、もっとうまい方法がある。 a-1, b それぞれのルート取って切り捨てて差分を取れば…

解法 ポイントは以下 はじめの状態で同じ配置の行は何度列をフリップしても同じ配置の行のまま 同じ列を2回フリップすると Kが2回分消費できる よって、各行について '0' の数をカウントし '0' の数が K "以下" で、'0' の数と K との偶奇が一致すればその行…

解法 容易に定まる条件を持つものから決定していく。 円の中心が三角形の内側にあるかどうか調べる必要があるが、これはCCWするかそれに値するような外積の符号を見る式を書けばよい。内積で角度出してやろうとしたらうまく行かなかった。単純なミスなのか、…

解法 問題文を読んで、やるだけ反省 ボウリングの意味を勘違いしてたので、ずっとサンプルが合わなかった。 #include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { typedef pair<int, int> Pii; int N; while(cin >> N && N) { vector<Pii> SCORE(N); for(int m</pii></int,></vector></algorithm></iostream>…

解法 地鶏を上限まで買えるだけ買った後、鶏肉の地鶏と普通の鶏との合計が足りるように地鶏を減らしながら調整する。地鶏が1匹も購入できない場合は "NA" と出力。ポイント 購入できる地鶏の数を予算から単価を整数除算することで見積もること 購入する地鶏…

考え中の解法 シミュレートする。1000個のブロックが落ちてくるとき最悪ケースでフィールドがどれだけうまってしまうかは 5*1000 で 5000 なので、grid[5001][5] を用意すれば十分。

解法考え中 多分、球面三角法使う。二点を最短で通る円から、その中心から二点までのベクトルのなす角を求める。 なす角が分かったら、半径に角度を掛けて弧を求める。

大意 プレイヤーのいる座標(u, v) から、X, Y軸平行に絶対値距離d だけ離れてつくられる正方形の領域が、プレイヤーの勢力域であるとする。敵の座標(x, y)が与えられるので、敵を勢力域に入れるためにプレイヤーが初期位置 (0, 0) から移動すべきユークリッ…

問題 http://uva.onlinejudge.org/external/108/10858.html意訳 生物名が複数種与えられる。与えられた関係から食物連鎖に関わるグループを部類分けできるので、そのときの食物連鎖のグループの最大サイズを出力せよ。ただしAがBを捕食する関係にあるとき、…

解法 拡張ダイクストラ。各エッジをわたるコストが0または1で、1のみではないことを考えると幅優先ではなくコストの小さいものをキューから取り出す拡張ダイクストラがいいと思うけど、多分幅優先でも出来る。問題では場外から目的地に向かうが、スタート地…

問題概要 ある有向グラフが与えられる。このグラフをたどるとき、そのパスの数が多項式の距離で表されるかどうか判定せよ。一度通ったノードでもパスがあれば何度でも通ることが出来る。解法 i から到達できる j を全て探す。中継点kを決めるN^3の方式で、判…

問題文 http://uva.onlinejudge.org/external/106/10664.html解法 取る取らないのO(2^20)のDFSで解けばよい。 ちょうど半分に分けられるかどうかを判定するが、ここで入力の重さを安易に整数除算して切り捨てによるミスを犯さないようにする。ただサンプル1…

問題概要 テーブルに有るコインを４方向にずらして枠外に振り落とせる。テーブル上に残るコインの数が、与えられた数Kに一致するための最小のテーブルの移動回数を求めよ。解法 制約が小さく、テーブルが 30*30 なので単なる6重ループで求まるはずだが、二次…

解法 問題文が長いが、冷静に必要な部分を把握して解く。 ポイントはエラトステネスの篩をかけた後に、区間の素数の数をO(1)で求められるように累積和を取ること。つまり、サブプライム(sub-prime)は求めずに、サムプライム(sum-prime)を求めればよい（激寒…

http://uva.onlinejudge.org/external/106/10633.html問題概要 ２桁以上の整数Nと、Nの下一桁を取り除いた整数Mが与えられる。N-M の値があなたに伝えられるので、もとのNの候補を昇順ソートして全て示せ。解法 #include <bits/stdc++.h> using namespace std; typedef unsi</bits/stdc++.h>…