keyword 最小全域木 Java 問題概要 ノード数N( 解法 接続次数が2の時点で環状になることが分かる。部分的な最小全域木は重み最大の辺を1本だけ辺を取り除いたものになる。なので重み最大の辺がいくつあるか数えるだけ。グラフの探索にDFSをやるとstack overf…

2分探索するだけ。

構文解析するだけ。

分母に関して全探索+分子に関して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扱いにしてオーバーフローを防ぐ)。 感想 「こんなの余…