2011-01-01から1年間の記事一覧
[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で提出) …
問題文: Unit Fraction Partition | Aizu Online Judge 汚いソースなんだよね。それ一番言われてるから。 自明な枝狩りをきちんと実装できるかが問題。 また k*(1/current) がp/qより小さい場合枝狩り。 ↑とくにこのへん あとオーバーフローに対する処理を手…
問題文: Icicles | Aizu Online Judge なんか昔プライオリティキューを使って解くというのを見たせいでまったく解けなかった。頭悪い。。。 プライオリティキュー忘れて適当にメモ化再帰したら解けたっていう...。 しかもこっちの方が短いし早い気が。再帰だ…
先日、supercon2011の通知がきて予選通過やったんや。 知り合いに会えるとか、初superconでワクワクしていたんだがー、 ワシの精神の我慢の限界がきたみたいで、「ああ＾～もうやる気が出るぅ～」と言って以下略 (追記:06/29) テストデータが公開されていた…
(僕が開催者だったら、ジャッジ終わるまでの一週間はあんまり晒して欲しくないけど・・・) とりあえず、晒していいものか分からないけど晒す。配列確保しすぎてダーク♂。 方針としては、 ただのダイクストラでスタートとゴールからの距離とか求めて、それに…
POJ : 1068 -- Parencodings 日本語: 1068 Parencodings - PKU Wiki* ひとつずつネストへらしながらうんぬん。 #include <iostream> #include <vector> using namespace std; int main(){ int T; cin >> T; while(T--){ int n; cin >> n; vector<int> d; int p = 0 , q; for(int i =</int></vector></iostream>…
GCJ GCJなんて無かった。超低速1完2000位くらい。悲しかった。 UAPC2011 UAPC2011なんて無かった。2完で60位くらい。悲しかった。 とまあ、UAPCは5時間掛けたのに結局解けたのが2問だったわけですよ。 Bが復活していたのに気づけなかったのが痛かった。一応…
JOI参加記をさぼっていますが。UTPC2011参加しました。無理ゲーだった。いつもの形式で書く。 問題文はこちら: 404 Not Found (ネタバレいやな人は見ないように) [00:00] コンテスト開始 A読む。やるだけ過ぎて不安になったので念入りに入力制限等をチェック…
お疲れ様でした。楽しかった！ 3日目 - 灘文化祭 (見学に来ている小学生みんな頭良さそうでチビりそうになった) 3日目は灘の文化祭にJOIerで行きました。 僕は東京組より少し早めに着いて、パソコン研究部に荷物置かせてもらったりしました。中2くらいからCF…
良問だと思う! 問題(要ログイン) 任意の位置の文字列を適切な位置に挿入できますが、最小何回でソート済みに出来るかみたいな問題。
と思ったらkyuridenamidaになってた。 開始前 いつものようにCFのサイトにそのコンテスト用の記事が出来る。 読む。 →「Today I(ir5) and rng_58 are the authors of Codeforces Beta Round #71.」 →日本人やん！！！！！！！１ →最近英語読めてなかったので…
kyuridenamidaが見えてきたよ
おわった。 西会場での参加でした。久留米から来たnikollsonさんと、灘の4人と一緒の会場。6人少ない。 どうせ僕は今年は代表になれるような選手ではないので、もう点数とかどうでもいいです。なので晒しちゃいます。とりあえず合宿、残りの問題解けるように…
またもや死亡なうと言った感じ。 x-- 0.0Pt. 試合前 少し熱気味でしたが久しぶりだったので参加したかった。 Target1人 Red4人 Blue4人 他Yellowとかいうとんでもない部屋に当たる。 250 ToastXToast? 絵が・・・よくわからない・・・。問題文・・・よく分か…
やろうと思っていたMM、昨日の朝からやりはじめて昨日の夜までやってましたが、ムリっス(・×・) したこと 長方形判定とか座標とか文字列ポインタとか持った配列につっこんで追加していく。 実際に二次元配列に埋める感じではなく、最後に生成する感じ(非効率…
本文:404 Not Found 「超 大 作」。 枝狩りがうまくできなかったので先輩の手助けなどを借りた。とっても感謝。 とりあえずしたこと。気が狂う感じだった。 入力制約よく分からないので色々対策 まあ当然元々の'.'とパーツの'#'の個数照合して不一致だったら…
404 Not Found 問題文は↑を、と言いたいところなのですが僕は読めなかったので、 AOJ : 1235 - Life Line - Respect2Dの日記を参考にさせて頂きました。丁寧な説明本当に助かります。 まあやるだけなわけですが、cと同じ番号のを多めに引いて後で足すって形…
なんか今日の8時からやるそうだったので参加してきました。(ツイッターで募集されてた。) 250 MnemonicMemory なんか数字と単語の長さで語呂合わせしたいからよろしく。みたいな問題。解は必ず存在する。 けど、複数解がある場合は辞書順で最小のものを返せ…
