Road Construction | Aizu Online Judge 与えられた無向グラフで、長さ優先で、次にコスト最小のグラフをつくりたい。辺ごとに維持費みたいなのがあって、最低で必要なコストを求めなさい。(長さは元の最短と同じじゃないとだめ) よくわからない。あまりイメ…

! | Aizu Online Judge 問題文: n進数(8≦n≦36)のm(12桁以内)が与えられる。m!をn進数にすると、0がいくつ続くか。 解法: 10の階乗に0がいくつ続いてるかの考え方のアレをn進数に適用する。 まず、10進数で考えてみる。 (m!に0がいくつ続いているか) = min(m!…

And Then There Was One | Aizu Online Judge ヨセフスの問題とか、ヨセフスの芋とか言われるやつ。 n人いて、m番目の人からはじめてk間隔で処刑していくヨセフスの問題という設定。 シミュレーションだと間に合わないので、「ヨセフスの問題」とかでググる…

KULASIS | Aizu Online Judge とりあえず、性質的に上の段から順次右から左に確定していける。 [何番目を見ているか][現在含め７個先まで情報(bitとかで持つ)]持って、"確定したところの最大の点数"を求めるdp～(メモ化再帰とか #include <iostream> #include <cstring> using n</cstring></iostream>…

ゲーム木探索知った勢いでコーディングしてみた。 したこと ①現在のビットと使った個数を持っておけば、何を使ったかを復元できる(一意に定まらないことがあっても問題ない) ②そのために[何番目まで使ったか][ビット状態][使った個数]で、使ったアイテムを記…

問題文: 1082 -- Calendar Game ゲーム木探索できるようになってうれしい (その状態から遷移できる中でひとつでも負けの状態(false)があるとreturn trueするやつ使いやすい) #include <iostream> #include <cstring> using namespace std; int leap(int n){ return n % 400 == 0</cstring></iostream>…

DPで書いてみた。 問題文: Sergeant Rian | Aizu Online Judge アホなDP解(メモ化)なので、0.5sくらいTLEします。 いちおう出力はただしいらしい(PCKオンライン講座で確認済み) DPは何も考えずに目先のことだけ考えてれば解けるからいいけど、やはり性質を考…

問題文: 2305 -- Basic remains mが小さいことに注意する。一回mを十進数にしたものを得てから、それで余り取りながら基数変換する。 今さら気づいたんだけど基数変換ってもっとシンプルに書けるよな・・・。 #include <iostream> using namespace std; #define rep(i,</iostream>…

[Easy]250 PrimeContainers 問題文 与えられたNを切り捨てながら2で割っていって、操作の途中で何回素数が出てきたか。Nが素数の場合も含む。 解法 素数判定やるだけ。O(N)の素数判定でも、N log Nで間に合う。が、できればO(√N)以下にしたいところ。 bool i…

[Easy]250 LinearTravellingSalesman 問題文 全ての点を通る１本の直線(軸に平行でなくても良い)が存在するような点の集合が与えられる。(例えば{(1,1),(2,2),(3,3)}とか) (X1,Y1)-(X2-Y2)間を移動するときに、|X1-X2|+|Y1-Y2| (まあ要するにマンハッタン距…

前回こんな記事を書きましたが、1年程経ったのでその続きを書こうと思ったり。忘れてることも多かったり。 9月 直前にプリム等のアルゴリズムを知る。ほえうえ。 高１なので初のパソコン甲子園予選。緊張しまくってＷＡだしまくり、結局僕自身は１問も解けず…

問題文: Yanagi’s Comic | Aizu Online Judge UAPCの問題。とりあえず幾何かなとか思って避けてた人は問題文をしっかり読むべき。(自戒の意味を込めた) 実装方法をミスって悲惨な書き方しているけどいちおうソース。 再帰的にやると楽。忠実に実装した。 #in…

問題文: The Number of the Real Roots of a Cubic Equation | Aizu Online Judge 誤差と戦うゲー 正直x*x*xとか書くのが面倒くさいからと言って、pow(x,3)とか書いてるとかなり痛い目にあう。 あとsqrtとかあまりよくないから自分のsqrtつくるべし。 3回目…

問題文: Dice Puzzle | Aizu Online Judge やっぱりこういう問題時間食うなぁ。 ソースからは除いたけど、最初回転ライブラリを書いていた。24通り列挙して埋め込めたから削除。 バックトラック。枝狩は特別なものはしていない。 全通りの回転状態24コについ…

今日の1:00からありました。 ox- 250 Zoo 猫と兎のグループがある。各動物に対して、であなたより身長の高いあなたと同じ種類の動物は何匹居ますか？と聞いて、みんな正しく答えてくれる。 答えリストが与えられる。各動物が兎であるか猫であるかは分からな…

問題文: Planning Rolling Blackouts | Aizu Online Judge 現在見ている区間の上下左右の端で状態数32^4くらいでメモ化再帰った。 漸化式とかよく分からないのでソースを見てください。 二次元累積和使うと早いヨ! 一番面倒くさいのは、その中でさらに予備電…

問題文: And Then. How Many Are There? | Aizu Online Judge 盤面の状態数は2^24である。それでDPすれば良い。ただ、AOJではcharじゃないとメモリオーバーになって死ぬ。 実装はDPよりメモ化再帰の方が効率的なのでそうした。 円と円の当たり判定は、 2つの…

問題文: Identically Colored Panels Connection | Aizu Online Judge 問題文と戦うゲーム。 正しく問題を把握できて、バグを起こさないコーディングができりゃ勝ち！ 左上をひたすら変えまくるのを全通り(6^5)調べるだけ。バックトラックでシミュレーション…

問題文: The Balance of the World | Aizu Online Judge stackにつんでいって確認していって、途中で矛盾が生じたり、最終的スタックが空になってなきゃno。 #include <iostream> #include <stack> #include <vector> using namespace std; int main(){ string str; while(getline(cin</vector></stack></iostream>…

問題文: Chebyshev’s Theorem | Aizu Online Judge 素数やるだけ。エラトステネスとかしておく。 あと累積和作っておくと、(n,2n]に存在する素数が、O(1)で計算できる。正直必要ないけどなんとなく。 #include <iostream> using namespace std; int p[300001]; void in</iostream>…

今さら書く。結局解けたのはA,B,Cだけ。Dはアホな解釈によりWAったらしく、Eは余る量？みたいなのを出すのに時間がかかり、結局間に合わずオワタ。 テンプレつかったので正直速かった。(本番は駄目なので実際もっと遅いはず) A 素数やるだけ。 (144sで提出) …