Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

PKU 3770 - Baseball on the Mars (この記事を編集する[管理者用])

Source

PKU Campus 2010 (POJ Monthly Contest 2010.05.09) (参加記録)
PKU 3770

問題概要

野球っぽいことを行う.
ホームベースの座標は(0,0),1塁(10,0),2塁(10,10),3塁(0,10).
N人の人が順番にバッティングする.
ボールが落ちた場所が,x座標,y座標どちらかが負なら,バッターはアウトで,ランナーはそのまま.
そうでないなら,ボールが落ちた瞬間にバッターとランナーが次の塁に向かって走り出す.
守備は,ボールが落ちた瞬間に,ボールをキャッチしていて,どれかの塁に向かって投げる.
ランナーが到着するより,厳密に前の時間にボールが届けば,その塁に向かっていたランナーはアウトになる.
その後,他の塁に向かって,またボールを投げても良い.
各バッティング後に,1塁に人がいればK1点,2塁に人がいればK2点,3塁に人がいればK3点,ホームベースに人がいればK4点とカウント.
守備チームは,毎回,それが最小になるようにボールを送球する.
また,ホームベースに人がいれば,その人は,次のバッティングの前に取り除かれる.
毎回のバッティング後の点数を出力する問題.
ボールのスピードは5,ランナーのスピードは2.

解法

シミュレーションやるだけ.

PKU 3769 - Baseball on the Mercury (この記事を編集する[管理者用])

Source

PKU Campus 2010 (POJ Monthly Contest 2010.05.09) (参加記録)
PKU 3769

問題概要

野球っぽいことを行う.
N人の人が順番にバッティングする.
3塁に人がいるなら,犠牲フライっぽいものを,そうでないなら普通にバッティングする.
犠牲フライは成功したら,自分はアウトになり,塁に出てる人たちは,0~2だけ先に進める.
普通のバッティングは失敗したら自分はアウトになり,塁に出てる人たちはそのまま.
成功したら,その成功度合いに対して,バッターと塁に出てる人たちは0~Gだけ先に進める.G=1,2,3,4で成功度合いによって決まる.
同じ塁に1人以上入れない,ホームベースに留まることはできない.
点数計算は,ホームベースに戻ってきた人 - アウトになった人,で計算する.
各選手のバッティングの成功率が与えられたとき,どれだけ進むかを自由に選べるとして,得られる得点の期待値の最大値を求める問題.
Nは10000以下.

解法

DP.
状態は,今何人目のバッターか,1塁に人はいるか,2塁に人はいるか,3塁に人はいるか,で10000*2*2*2状態ぐらい.

PKU 3768 - Repeater (この記事を編集する[管理者用])

Source

PKU Campus 2010 (POJ Monthly Contest 2010.05.09) (参加記録)
PKU 3768

問題概要

空白以外に文字が1種類しか含まれないN*Nの文字列が与えられる.
その文字をcとして,最初の盤面をc,1文字だけからなるものとして,K回だけ以下を行う.
 空白をN*Nの空白に置き換え,cを与えられたN*Nの文字列に置き換える.
このようにしてできたフラクタル図形を出力する問題.
答えは3000*3000以下に収まる.Nは3以上5以下.

解法

書くだけ.実装問題.

PKU 3767 - I Wanna Go Home (この記事を編集する[管理者用])

Source

PKU Campus 2010 (POJ Monthly Contest 2010.05.09) (参加記録)
PKU 3767

問題概要

ノード数600以下の無向グラフが与えられる.
ノード1からノード2に行くための最小距離を求める問題.
ただし,各ノードは2色に色分けされており,違う色に移動するのは1回までしかできない.
ノード1とノード2は違う色で塗られている.

解法

ノード1の色からノード2の色にいったら,逆戻りはできないので,ノード1の色とノード2の色を結ぶ枝は一方通行にすれば良い.
後はダイクストラするだけ.
もしくは,ノードを多重化するなど.

PKU 3766 - Hexagon Coin Toss (この記事を編集する[管理者用])

Source

PKU Campus 2010 (POJ Monthly Contest 2010.05.09) (参加記録)
PKU 3766

問題概要

図のような六角格子が与えられる.
中心がその格子内になるように,ランダムに半径rの円を置く.
円がいくつの六角形と交わっているか,その確率をそれぞれ求める問題.
円の半径は0.5以下,六角形の一辺の長さは1.
六角格子のサイズは1000*1000以下.

解法

頑張って面積を求める.
行数が1のとき,または列数が2のときのみ,離れた辺で他の六角形と接することがあることに注意.

PKU 3765 - Xiang Hex (この記事を編集する[管理者用])

Source

PKU Campus 2010 (POJ Monthly Contest 2010.05.09) (参加記録)
PKU 3765

問題概要

問題の図のような六角格子を考える.
各駒がいる座標が与えられるので,その駒を置いた盤面を生成する問題.

解法

実装するだけ.

PKU 3764 - The xor-longest Path (この記事を編集する[管理者用])

Source

PKU Campus 2010 (POJ Monthly Contest 2010.05.09) (参加記録)
PKU 3764

問題概要

枝に重みがつけられた,ノード数100000以下の全域木が与えられる.
パスの重みは,そのパスに含まれる全ての枝のXORで定める.
重み最大のパスの重みを求める問題.

解法

まず適当な始点を決めてあげて,その始点から全てのノードまでの(XORで定義された)距離d[i]を求める.
ノードaとノードb間の距離はd[a] XOR d[b]で計算可能.
なので,d[i]から2つ選んで,XOR取って最大となる組み合わせを探せば良い.
2分探索っぽく,上位ビットから決めていく.
上位ビットのみ考えて,それが達成できるかどうか,相方が存在するかどうかをhashなどを使って探索する.

PKU 3763 - Tour in Wonder Land (この記事を編集する[管理者用])

Source

PKU Campus 2010 (POJ Monthly Contest 2010.05.09) (参加記録)
PKU 3763

問題概要

ノード数100000以下の全域木が与えられる.
枝を何本か加えて,すべてのノードをただ1回のみ通る閉路を作りたい.
加える枝の最小数を求める問題.

解法

元々ある枝のうち何本を有効活用できるか,その最大値を求めることを考える.
同じノードに繋がってる枝は最大で2個までしか利用できない.
なので,葉からgreedyに使って行くことにすれば良い.

PKU 3761 - Bubble Sort (この記事を編集する[管理者用])

Source

PKU Campus 2010 (POJ Monthly Contest 2010.05.09) (参加記録)
PKU 3761

問題概要

1~Nのpermutationのうち,バブルソートでK roundでソートが完了する物の数をmod 20100713で求める問題.
Nは1000000以下.

解法

適当なNについて,全探索で答え求めてみると規則に気づく.
それの証明方法は,例えば,最初場所iにいたものが左の数字に「抜かれる」回数を考えてみる.
一度でも抜かれないと,次回以降のRoundでは抜かれない.
抜かれる回数は,自分より左にいた,自分より大きな数字の数.
抜かれる回数の最大値は,それぞれ,位置iにいた数字はi-1回まで.
Round数は,抜かれる回数の最大値に等しい.
などを考える.
階乗の値は,最初に1000000!まで求めておく.べき乗はlog nで行う.

PKU 3762 - The Bonus Salary! (この記事を編集する[管理者用])

Source

PKU Campus 2010 (POJ Monthly Contest 2010.05.09) (参加記録)
PKU 3762

問題概要

N個以下のタスクが与えられる.
タスクiを行うには[A_i,B_i)の間,タスクに取り組まなくてはいけなくて,タスクをこなすとC_iだけ利益がある.
1人が同時にできるタスクは1個のみで,K人だけ人がいる.
利益の最大値を求める問題.
Nは2000以下,Kは100以下.

解法

最小費用流.
各タスクの,開始,終了をノードにして,2N個のノードを作る.
時間が自分より後のもの(か等しいもの)に流量無限大,コスト0の枝を張る.
各タスクの,開始から終了に向けて,流量1,コスト -C_i の枝を張る.
このようなグラフを考えれば良いが,このままだとTLEだった.
終了に対応するノードを端折って,終了のかわりに次の開始のノードを使う.
開始時間でソートしておいて,次のノードに向けてのみ,流量無限大,コスト0の枝を張ることにする.
こうすることで,ノード数N,枝数O(N)にできて,これでギリギリ通った.
また,流量無限大の枝のコストを10000にして,コスト -C_i の枝は,タスクiからタスクjに枝を張っているならコスト 10000*(j-i)-C_i に変更したら速くなった.

POJ Monthly Contest 2010.05.09 (参加記録) (この記事を編集する[管理者用])

2010年05月10日13時から5時間,10問.
[ Link ]

ここ2日ぐらい体調が悪くて,頭痛がしてたのだけど,軽く参加.
久しぶりのPOJ Monthly.
昔は2問ぐらい解ければ良いやって感じだったけど,最近のPOJは易化してるので,もうちょっと解きたい.
で,結果は6問でした.いくらなんでもちょっとひどいかな….
でも,9問は凄いと思う.1位の人.

AはN=7ぐらいで全探索してみて規則を見つけた.Accept.
Gはダイクストラするだけだった.Accept.
Hはフラクタルっぽいのを実装するだけだった.Accept.
Cは各頂点2つまで枝が使えるので,葉からgreedyに使う枝を決めていった.Accept.
Eは六角座標でいろいろな駒の位置を出力するだけの実装問題だった.Accept.
ここから泥沼.
Dはノード100000以下の木が与えられて,各枝に重みがある.重み最大のパスの重みを求める問題.ただしパスの重みは,パスに含まれる枝の重みのXORで定める.
わからん,飛ばす.
Fは幾何.面積を頑張って求める問題.
頑張って書くと,2個以上と重なる面積はサンプルとあったのに,3個と重なる面積が合わない.
3個と重なる面積って,半径rの円の面積×3つの六角形でできてる頂点の数じゃないの?
一番簡単そうなのが合わない….
Iを読んでみると,DPを書くだけっぽい.でも少し実装が面倒.
まぁ,書いてみる.
合わない.
普通に打ったときの,失敗する確率が,1-入力の前4つと言うことに気づいた.
(それまでは,badな当たりが失敗だと勘違いしてた)
直す.合わない.
サンプルが間違っているんじゃないの?サブミット.RE.なにぃ.
読み間違え前はパターンの数4パターンで,直した後パターンの数が5パターンに増えてるのに配列のサイズが4のままだった.
直すとサンプルでてきた.
Accept.
Fは,
 半径rの円の面積(r*r*PI)×3つの六角形でできてる頂点の数

 r*r*(PI+6/sqrt(3))/2 ×3つの六角形でできてる頂点の数
に変更するとサンプルと一致することを発見.
なんだこの式?意味不明?
サンプルと合うので一応サブミット.WA.
ちなみに,行数が1行のときは,隣り合わない2辺で接している六角形が出てくるというコーナーケースはちゃんと考えている.
Bは,最小費用流に落とせそう.落とした.
でも,ノードの数が2N,枝の数がO(N^2)でグラフ作ってTLE.
Jは問題を読んでない.

以下,コンテスト後.
Bをノード数2N,枝の数をO(N)にしてみる.でも,TLE.
ローカルでランダム最大ケースを走らせると4秒かかる.うーん.
ノード数Nにしてみると,ローカルで1.2秒で終わるようになった.
サブミット.Accept.ただし,制限時間2秒で,1.969秒とかかかってる.ぎりぎりすぎる.
最小費用流はダイクストラ繰り返してるんだけど,枝の重みが負か0しかなくて,幅優先っぽい順番で探索してるような感じになってて,ちょっと効率悪そう.
全部の枝に適当に重みを足して,正にしてやると,ランダム最大ケースが0.2秒ぐらいで終わるようになった.
それをサブミットすると,0.485秒でAcceptされた.
うーん,最小費用流って難しい….

PKU 2528 - Mayor's posters (この記事を編集する[管理者用])

Source

Alberta Collegiate Programming Contest 2003.10.18
PKU 2528

問題概要

基本的にはSPOJ 138 [POSTERS]と同じ問題.
サイズが少しだけ違って,ポスターの枚数が40000枚以下ではなくて,10000枚以下.
サンプルが一緒なのに,出典が違うし,絵も微妙に違うという謎問題.

解法

SPOJ 138 [POSTERS]の記事を参照.

PKU 2230 - Watchcow (この記事を編集する[管理者用])

Source

USACO 2005 January Silver
PKU 2230

問題概要

ノード数10000,枝数50000以下のグラフが与えられる.
全ての枝を,往路復路1回ずつ通るようなパスを1つ求める問題.
答えが存在することは保証されている.

解法

再帰.
あるノードにある枝を通ってきた場合,その枝を通って前のノードに戻るとして,通ってきた枝を消して,進む先がある限り前に進む.

PKU 2151 - Check the difficulty of problems (この記事を編集する[管理者用])

Source

POJ Monthly (2004.12.26)
PKU 2151

問題概要

1000チーム以下の人たちが,問題数30以下のプログラミングコンテストに参加する.
それぞれのチームがそれぞれの問題を解く確率が与えられるので,
 1) 全てのチームが最低1問は解く
 2) 最も多くの問題を解いたチームはN問以上解いた
という条件が満たされる確率を求める問題.

解法

まず,DPで各チームがk問解く確率を全て求める.
後は,DPで条件が満たされる確率を求める.

PKU 2112 - Optimal Milking (この記事を編集する[管理者用])

Source

USACO 2003 U S Open
PKU 2112

問題概要

ミルクマシン30個以下,牛が200匹以下いる.
ミルクマシン1台にM匹までの牛を割り当てることができる.
最初牛のいる場所,ミルクマシンの場所をノードとして,無向グラフが与えられる.
全ての牛を割り当てられたミルクマシンに移動する必要な最大移動距離を最小化する問題.
割り当てる方法が存在することは保証されている.

解法

最初にワーシャルフロイド(もしくはミルクマシンの回数だけダイクストラ)して,牛,ミルクマシン間の最短距離を求めておく.
後は,2分探索+最大流.

PKU 3747 - Scout YYF II (この記事を編集する[管理者用])

Source

POJ Monthly Contest - 2009.08.23
PKU 3747

問題概要

2次元平面上で,原点中心,半径Rの中が基地.
基地の中に自分と10個以下の爆弾がある.
爆発すると爆弾中心でとあるスピードで通れない場所が膨れる.
自分はそのスピードと同じ速度で走れる.
爆発に巻き込まれる前に基地の外に辿り着けるかどうかを判定する問題.

解法

2次元幾何(垂直二等分線 + 凸多角形のカット).
自分と爆弾の位置が一致したら不可能.
後は,2次元平面全体から初めて,各爆弾と自分との垂直に等分戦の自分側のみからなる領域を求めて(そこに全速力ダッシュしたら爆発に巻き込まれる前に辿り着ける場所の集合),それが基地の外と共通部分をもつかどうかを調べる.
カットした多角形の頂点のみを調べれば十分.

PKU 3744 - Scout YYF I (この記事を編集する[管理者用])

Source

POJ Monthly Contest - 2009.08.23
PKU 3744

問題概要

長い1直線の升目がある.
10か所以下の地雷のマスが与えられる.
確率pで1マス先に進む.確率1-pでジャンプして2マス先に進む.
地雷を踏まない確率を求める問題.

解法

数学(差分方程式) + straightforward.
差分方程式を解いて,今いる場所からk個先のマスに止まる確率を求める.
後は,地雷の前のマスに辿り着けて,ジャンプして飛び越して,…,となる確率を適当に計算するだけ.

PKU 3742 - Equivalent Polynomial (この記事を編集する[管理者用])

Source

POJ Monthly Contest - 2009.08.23
PKU 3742

問題概要

n次多項式が原点周りのテーラー展開の形で与えられる.(つまり普通の形)
x=t周りのテーラー展開の形に変更する問題.
nは200以下,tの絶対値は10以下.

解法

平行移動するだけ.
たが,多倍長が必要.思いのほか時間制限が厳しくて,コンビネーション*冪とか色々最初に計算しておいた.
いい加減,効率悪い自作多倍長を改良するべき時なのかもしれない.

PKU 3741 - Number System Converter (この記事を編集する[管理者用])

Source

POJ Monthly Contest - 2009.08.23
PKU 3741

問題概要

文字列をP進数と思って整数に直して,その整数をQ進数と思って文字列に直す.
P進数に直すとき,ある桁の数がPを超えていても気にしない.
最初の文字列が与えられたとき,この操作を繰り返すと,何に収束するかを答える問題.
P < Q,最初の文字列は5000000文字以下.

解法

収束先はqより小さい1桁の数.
1ステップで,
 Q → P, Q^k → P^k
などに変わることから推測すると,
最初から,Qより小さいならそのまま,そうでないなら,(入力をQ進数とみなして) Qより小さくなるまでQ-Pを引くと良い.

PKU 3740 - Easy Finding (この記事を編集する[管理者用])

Source

POJ Monthly Contest - 2009.08.23
PKU 3740

問題概要

16行300列以下の行列が与えられる.各要素は0か1かのどちらか.
何行か選んで,全ての列に対して1が丁度1個のみあるようにすることができるかどうかを判定する問題.

解法

2^16通り全探索.
ただし,各行の1の数が1個だけかどうかの判定は,ビットを使用してO(1)で判定する.

PKU 2384 - Harder Sokoban Problem (この記事を編集する[管理者用])

Source
Northeastern Europe 2004, Far-Eastern Subregion
PKU 2384
TJU 2370

問題概要
箱が1個の倉庫番を考える.
マップの形状と,箱を運ぶ最終地点のみが与えられるので,最初の人物の位置と箱の位置を自由に決めて,最小移動回数を最大化したい.
解くために必要な移動回数の最大値を求める問題.
マップのサイズは25*25以下.

解法
状態数は25^4 (40万以下)しかない.
答えの盤面(箱が目的地)を全て列挙して,それを始点に倉庫番ゲームを逆向きにBFS辿る.

PKU 2380 - Sales Report (この記事を編集する[管理者用])

Source
ACM/ICPC Northeastern Europe 2004, Far-Eastern Subregion
PKU 2380
TJU 2366

問題概要
列ID,行ID,数値の3つ組が500000個以下与えられる.
各セルは対応する入力の数値の和となるような表を出力する問題.
IDの値や数値は10^9以下,各セルの値は2^31未満であることが保証されている.
セルの数は10^8以下であることが保証されている.

解法
適当に,列ID,行IDを圧縮して表を作って足す.
PKUだとタイムリミットは3秒.
GCCだとTLEだったけど,Cだと1300msぐらいで通った(scanfおよびprintf使用).

PKU 3171 - Cleaning Shifts (この記事を編集する[管理者用])

Source
USACO 2005 December Silver
PKU 3171

問題概要
N匹の牛がいて,それぞれ,雇うとある金額である区間の掃除をしてくれる.
掃除したい区間[M,E]が与えられるので,全ての区間を少なくても1匹の牛が掃除するように雇う.
コストを最小化する問題.
Nは10000以下,区間の幅は86400以下,コストは64bit整数で計算すればOKな範囲.

解法
基本的にはDP.
N匹の牛を区間の最初の値でソートして,小さい方から順番に処理していく.
で,DPでメモしておくことは,ある場所まで全て掃除している状態でのコストの最小値で,DPの更新するとき,その配列のある場所より後ろの最小値が必要となる.
何も考えずにループを回すとO(N * 区間の幅)でTLEになるので,DPテーブルの管理のデータ構造としてsegment tree (range minimum query)を使う.

PKU 2500 - Pia's Party (この記事を編集する[管理者用])

Source
TUD Programming Contest 2005 (Training Session), Darmstadt, Germany
PKU 2500

問題概要
直径dの円周上に等間隔にn点がある.点は0からn-1までの番号をつけられている.
その中のc個の点のうち4か所に拡声器を置く.
c個の点の番号は
 (g*k) mod n, k=0,1,...,c-1
で与えられる(gとnは互いに素).
拡声器を置かれた4点で囲まれる四角形の面積を最大化したい.
面積を求める問題.
nは10^9以下,cは1000以下.

解法
まず,四角形の対角線(2点)を決めつける.
後は,2点に挟まれる点の中で最も遠い点(三角形の高さが高くなる点)をバイナリサーチで探す.
これだとO(c^2 log c)ぐらい.
僕はバイナリサーチをせずに,尺取りメソッドで探した.これだとO(c^2).

PKU 3573 - I18n (この記事を編集する[管理者用])

Source
ACM/ICPC Europe - Northeastern Europe - 2007/2008 (Northeastern Europe 2007)
LiveArchive 4051
PKU 3573

問題概要
文字列が与えられるけど,ときどき省略された形の単語がある.
省略されている単語を元の単語に戻して文章を全て出力する問題.
省略形はI18nみたいに[アルファベット1][数字][アルファベット2]な形をしていて,それは以前出てきた単語の真ん中[数字]文字だけ省略したもの.
単語はアルファベット以外の文字を区切りとして,アルファベットの連続で,全部小文字,最初だけ大文字,全部大文字の3種類しか登場しない.
単語は大文字小文字区別せずに同じ単語と思って,省略系が3パターンのどれに属するかは,[アルファベット1],[アルファベット2]が大文字か小文字かで区別する.
ただし,以前に該当する単語が存在しない場合,複数あって何の省略形かわからない場合は,置き換えずに省略形のまま出力する.
入力は1000行以下,各行80文字以下.単語は32文字以下のものしかでてこない.

解法
文字列処理,やるだけ.
26*26*33ぐらいの配列を用意して,先頭のアルファベット,最後のアルファベット,文字列の長さごとに出てきた単語の位置を覚えておくと簡単に処理できると思う.

PKU 2558 - Genetic Code (この記事を編集する[管理者用])

Source
University of Ulm Local Contest 2003
PKU 2558
SPOJ 1804 [GENETIC]

問題概要
長さnでN,O,Pの3文字からなる文字列のうちで,全ての隣り合うsubstringが等しくないものを1つ求める問題.
例えば,NOPNPNOはNPとNPが等しい隣り合うsubstringなので駄目.
nは5000以下.存在しないならそれを指摘する.

解法
長さ5000のを1回求めたら,後は,それから長さnだけ切り取って表示すれば良い.
5000のを求めるのは,なんか普通にDFSしたらすぐ求まった.

PKU 2005 - Blackjack (この記事を編集する[管理者用])

Source
ACM/ICPC North America - Rocky Mountain - 2004/2005 (Rocky Mountain 2004)
LiveArchive 3050
PKU 2005

問題概要
トランプを52枚をnセット使ってブラックジャックをする.
といっても,2枚ずつ配るだけで,それ以上のカードをもらうことはできない.
ディーラーのカード1枚とプレイヤーのカード2枚がわかっているので,プレイヤーの勝率を計算する問題.
ドローは負け.

解法
やるだけ.

PKU 2425 - Jersey Politics (この記事を編集する[管理者用])

Source
USACO 2005 February Gold
PKU 2425

問題概要
3*k個の街があって,それぞれ街の人口は1000人で,それぞれの街に自分を支持してくれる人が何人いるかが与えられる.
では,k個ずつ3つのグループに街を分割して,2つ以上のグループで過半数の人が自分を支持してくれている状態にしたい.
そのような分け方を1つ求める問題.答えは存在することが保証されている.
kは60以下.

解法
グループの1つは何でも問題ないので,支持してくれる人が少ない順にk個選んで,それらは排除して2つにわけることを考える.
DPで過半数を超える組み合わせのうち最も小さいものを求めて,それと残りに分ければ良い.
普通にDPするとTLE.どうせ素だろうと適当に枝を刈ると500msぐらいで通った(TLは1000ms).
良く考えると,kは60以下なので,long longでビットに埋め込めて計算量はO(k*(500k))ぐらいになって普通に通る.

PKU 1091 - 跳蚤 (この記事を編集する[管理者用])

Source
HNOI 2001
PKU 1091

問題概要
ノミたちがたくさん住んでいる町のバラエティTV番組の話.
N+1枚のカードが与えられ,そのうちN枚は1以上M以下の自然数,最後の1枚はMが書かれている.
無限に長い線の上を,ノミがジャンプして移動する.
ジャンプするのはカードの中から1枚選んで,それに書かれている数字の距離だけを左右どちらかにジャンプする.
1枚のカードで何回でもジャンプできて,ジャンプする順番も自由.
ゲームの目的は,最初の位置から左に1マスの位置に辿り着くこと.
さて,NとMが与えられたとき,目的が達成できるカードのパターンは何通りあるかを求める問題.
カードには順番があって,順序が違うと別の組と数える.
Nは15以下,Mは10^8以下.

解法
包除原理.
辿り着けるカードのパターンはN+1個の自然数のGCDが1であるとき.
Mを素因数分解してでてくる素数を列挙して,k個(p1,...pk)だったとする.
M^NからGCDがpiの倍数のもの((floor(m/pi))^n)を引いて,GCDがpi*pjの倍数のものを引いて…といった感じ.
多倍長で計算しないとダメなはず.

PKU 2126 - Factoring a Polynomial (この記事を編集する[管理者用])

Source
ACM/ICPC Northeastern Europe 2003, Northern Subregion
PKU 2126
TJU 2706

問題概要
次数20以下の整数係数多項式が与えられる.
その多項式が実数の範囲で,因数分解可能かどうかを判定する問題.

解法
全ての多項式は,1次と2次の多項式の積で書けるので,…(1)
3次以上は因数分解可能,1次以下は不可能.
2次の多項式は,判別式を計算して実数解をもてば因数分解可能.
(1)は,実数解をもてば,その分は1次多項式で,虚数解の部分は共役のと含めて2次多項式というやつ.

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。