keyword 整数 BruteForce Java 問題概要 整数N(三角錐数(i*(i+1)*(i*2)/6で表せる数)の和で、Nを越えない最大のものを求める問題。テストケースは10^3個以下。 解法 N以下の立方数と三角錐数をたくさん作ってその組み合わせを全部試す。一つのテストケースに…

keyword 動的計画法 Java 問題概要 1~Nまでの数のうち、a*x + b*y(x>=0 and y>=0)で表せない数がいくつあるか求める問題。N,a,bは全て10^6以下。 解法 典型的な動的計画法。表し方が何通りあるかも(modの形で)求めることができる。

keyword 整数 素数 Java 問題概要 長さN(素数Q( 解法 文字列をa[0]a[1]..a[N-1]とする。b[i] = a[i]a[i+1]..a[N-1] (10進の数値として解釈)とすると、b[i]=b[j] (mod Q)ならb[i]-b[j]=a[i]a[i+1]..a[j-2]a[j-1]0..0 (10進の数値として解釈)はQの倍数。ここで…

keyword ライツアウト 掃き出し法 Java 問題概要 W*H(W,H 解法 マンハッタン距離云々は本質に全く関係ない。連立一次方程式をmod 2の世界で解くだけ。計算量はO( (W*H)^3 )。計算量は係数に1/6だか1/3だかがつくけど割と厳しい。でも問題なく通った。 感想 …

解法 各操作に対して逆の処理はすぐ分かるので、やるだけとしか言いようがない。

解法 ただの最小全域木。誤差死することすらまずない親切設計な問題。

keyword 反復深化 シミュレーション Java 問題概要 5*5の盤面でライフゲームの初期値が与えられる。ただし、ある一つのマスには謎の物体Xがいて、Xは周囲のマスに対しては生きている様に振る舞い、しかし自分の存在するマスは回りの状態によらず死んだままと…

keyword Greedy Java 問題概要 W*H(W,H 解法 各数列はソートしても大丈夫だと分かる。 あとは、図の様に右上から左下に向かってGreedyに置いていく。計算量O(W*H)。

keyword 最小全域木 BruteForce Java 問題概要 ノード数V( 解法 下限に対して全探索する。下限さえ決めてやれば普通に最小全域木を求めると目的関数の値が計算できる。計算量O(|E|^2)。 感想 最初は下限に関して二分探索してたけどよく考えたら単調性はなか…

解法 二分探索するだけ。

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

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

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

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

keyword 空間幾何 C 概要 空間状に星がN( 何の工夫もなく角度を求めるだけ。計算量O(N*M)。あとPKUでGCCを選んだときは-lmがついていることも確認できた。

keyword 平面幾何 C++ 概要 頂点数N( 凸多角形の切断を繰り返す。計算量O(N^2)。

keyword 探索 C++ 概要 2次元のボード上に石がいくつかある。この上でカーリングをして滑るヤツを目的地に持っていきたい。滑るヤツは石に当たるまで止まらないし、石に当たるとぶつかった石を破壊する。最短で何回滑らせれば良いか求める問題。ただし10回以…

うろ覚えだけど覚えている分について書いてみる。

keyword 平面幾何 平面走査法 C++ 概要 100個以下の長方形が与えられる。長方形がカバーする部分の面積を求める問題。 Y軸に平行なイベントラインをずらしていく典型的な平面走査法の問題。区間のカバーする長さを毎回求めてやる。

keyword 幾何 C++ 概要 直線から構成された図形が与えられる。合同な図形を判定する問題。直線はすべてX or Y軸に平行。 端点を原点に平行移動して回転させてやればよい。

keyword 動的計画法 C++ 概要 整数n(素数の和がnになるような組合せの総数を求める問題。 硬貨の支払い方の問題のバリエーションの一つに過ぎない。1120以下の素数表を作っておき、dp[和がn][使った中で最大の素数(の番号)][使った素数の個数]で順に求める。…

keyword 2部グラフ マッチング C++ 概要 数列a_iとb_iが与えられる。a_iとb_jは互いに素でなければペアとして選ぶことができる。最大でいくつペアをつくることができるか求める問題。 2部グラフの例題のような問題で動作確認にありがたい問題。

keyword シミュレーション Java 概要 列車を2つに分割し、分割したそれぞれを反転させても良いし、前後を入れ替えて連結してもよい。全部で何種類のパターンができるか求める問題。 サイズが小さいので全パターンを列挙すればよい。易しめの実装ゲー。

keyword シミュレーション C++ 概要 金額と、金利と毎年の手数料の組と年数が与えられる。決められた年数で最大お金がどれだけ増やせるかを求める問題。 問題文が長いけど、ひねりは無い。読めたら後は書くだけ。調べるの面倒で変数名にtanriとかhukuriとか…

keyword シミュレーション C++ 概要 長方形のケーキを何度かに分けて切った。各ピースの面積を小さい順に出力する問題。 入力の渡され方がとても面倒くさいけど基本的には実装ゲー。毎回番号を振りなおすというよく分からないことをしているのでmultisetで何…