構文解析するだけ。

分母に関して全探索+分子に関して2分探索(or sqrtをとる)だけ。

構文解析するだけ。

幅優先するだけ。

言われた通り確かめるだけ。

多倍長で計算するだけ。

5で何回割れるか数えるだけ。

丁寧に数えるだけ。

幅優先するだけ。JavaだとTLEした。

やるだけの問題概要を書くのは面倒くさい。なので簡略化する。

keyword Java BruteForce Java 問題概要 2次元平面上にN( 解法 正方形は対角線上にある2点を決めたら残り2点の座標も決まる(このとき全ての座標を2倍にしておくと全部整数でできて楽かもしれない)。なので、2点を全て試せば良い。残り2点が存在するかどうか…

keyword 動的計画法 Java 問題概要 N( 解法 dp[i個めの町まで訪ねた][船が町jに置いてある]としてDP。最初にWarshall-Floydするのを忘れないこと。計算量O(N^3 + N^2*R)。

keyword 空間幾何 回転行列 Java 問題概要 N*M(N,M極座標が与えられる。北極星を中心にα度だけ回転させた後、z座標が正になっている星を求める問題。 解法 回転させるだけ。回転行列に関してはググるとヒットする。

keyword 構文解析 行列 Java 問題概要 行列の構文解析をする問題。 解法 BNFにしたがって実装するだけ。全て行列で処理すると良い。 感想 構文解析の練習になる問題だと思う。

keyword 数列 半順序集合 C++ 問題概要 長さM( 解法 DAGの最小パス被覆だが、ノード数が多いので2部グラフの最大マッチングでは解けない。まず、x座標でソートする。その後multiset Sを用意してxが小さい順に次の様に処理する。 Sにyより小さい元があれば、…

keyword シミュレーション C++ 問題概要 M*N(M,N 解法 価値の高いものから拾いにいく。次の価値の高いものを拾いに行ってそれから戻ってこられるなら次のを取りにいく。そうでないならその時点で戻る、とすればよい。

keyword 構文解析 Java 問題概要 文字列Xに対してX^nをn(X)と圧縮できる。圧縮された文字列(長さL 解法 BNFで次の様に定義する。 ::= | ε ::= | '(' ')' | 後は長さを調べてやるだけ(iを越えるものはINF扱いにしてオーバーフローを防ぐ)。 感想 「こんなの余…

蟻本に載っていた事実だけど、理解するのに時間がかかった。 まず、前段階として|マッチング| 具体的に最小点被覆を構成してみよう。2部グラフにsinkとsourceつなげて最大流を流し、最大マッチングを作る。このとき、残余グラフでsourceから到達不可能な左側…

keyword A* Java 問題概要 ノード数V( 解法 「DはDijkstraのD」再び。直前にいた位置と現在の位置と速度でDijkstraする。しかし状態数がV*V*MAX_Vでエッジが最大3*V本位出るので計算量がやや厳しい。そのままでも通るかもしれないけど目的地までの時間の下限…

keyword Dijkstra Java 問題概要 W*H(W,H 解法 D問題なので…。位置と方向を状態にしてDijkstraするだけ。

keyword Dijkstra C++ Java 問題概要 W*H(W 解法 また「DはDijkstraのD」の問題。どのマスにいるか、どの足を下ろしているかを状態としてDijkstraするだけ。ちなみにAOJでJavaを使っている理由は他にJavaの練習できるオンラインジャッジが少ないから(主にTLE…

keyword 包除原理 メビウス関数 C++ 問題概要 A 解法 f(x,y)を a_i in [x..y]かつgcd(a_1,...,a_N)=1となるような数列の種類と考えると、包除原理より答えはf(A,D)-f(B+1,D)-f(A,C-1)+f(B+1,C-1)となる。なのでf(x,y)さえ求めれば良い。 gcd(an)=1となるもの…

keyword BruteForce 構文解析 Java 問題概要 3つの未知変数P,Q,Rを含む3値論理の式が与えられる。式全体を真にするようなP,Q,Rの割り当てが何通りあるか求める問題。 解法 割り振り方は3^3通りしかないので全部試す。構文解析の部分もとても簡単。

keyword グラフ Dijkstra A* Java C++ 問題概要 ノード数M( 解法 「DはDijkstraのD」を地で行く問題。N=8とかどうみてもbit使って下さいといわんばかりなので使ってやる。今まで使ったチケットとノード番号のペアを状態としてDijkstraする。ただし何の工夫も…

keyword シミュレーション 平面幾何 Java 問題概要 ふたつのタイヤが付いた棒がある。左右のタイヤの角速度と移動時間が与えられる。移動後の棒の中心の座標を求める問題。 解法 軌跡は平行移動か円運動になるので適当に回転させれば解ける。0除算に注意する…

keyword シミュレーション 累積和 Java 問題概要 N( 解法 サイズが小さいのでどんな方法でもやれば通ると思う。今回は時刻i分にいくつのパソコンにログインしているかという情報を配列で持ってやった。開始時刻に+1、終了時刻に-1を加えておいて最後に累積和…

PKU(POJ)で500ACと一区切りついたので他のオンラインジャッジにも登録してみた。AOJとかProject Eulerとか放っぽり出しているものもあるけど、少しずつ同時進行で進めていこうと思う。UVaもSPOJもRuntime Errorの判定が厳しいので、横着せずに丁寧にプログラ…

keyword 整数 2項係数 C 問題概要 N,M(M 解法 mod 10で考えるので、2項係数を積で計算するとき2や5の因数は実際にかけずに指数だけ計算しておく。2,5と互いに素なら逆元も存在するので割り算も普通に計算できる。5の指数が2の指数より大きいときは答えは5だ…

keyword 動的計画法 組み合わせ C 問題概要 正N( 解法 DP臭のする問題。ある1辺に注目して、それを含む三角形or四角形で分類して考える。 まず、ある1辺を含むのが三角形である場合を考える。これは、まず三角形を作って、残りの2辺に残りのN-3頂点をどう割…

keyword ゲーム木探索 無向グラフ C 問題概要 ノード数N( 解法 典型的なゲーム木探索。グラフが木なのでflood-fillを流すときについでに勝敗を調べてやれば良い。計算量O(N)。