2010-01-01から1年間の記事一覧

CodeForces 51

死亡 ox---- 484pt(275位). 流れ A見る。お!実装。(8分) Bチラ見する。BNFはやめろ!!!!!!閉じる。 C見る。なんか解けそう。早くも通してる人いるし簡単なのかも! 計算量どうすればいいんや・・・。悩む。 いろいろな方法で実装するもサンプル通らないしで二…

hos’ Xmas Contest 2010

ああ完全に負けたわ。昼の部に参加しました。 A: Christmas Trees 問題開く。サンプル図を見る。余りの取り方にかなり悩んだ挙句とりあえず書く→60% っかしいな・・・何か見落としてるんじゃないか?(気づかないまま時間経過) 夜のコンテスト終わった後に c=d…

JOI予選2010/2011

Passed pre-match test 84.0Pt . 1.oooxo(入力ファイル提出してた...) 2.ooooo 3.ooooo 4.oo--- 5.ooooo 6.----- 3完 + 6 (書き忘れてた)

AOJ Problem 0081 : A Symmetric Point

0番で解いてないのをチマチマ埋める。 404 Not Found 対称な位置にある点を求める。学校では最近習ったりもした。 何も使わず、面倒くさい手計算をして点rと与えられた直線との直交点を求めてからそれを内分するもう片方の点を求めれる式をつくった。 直線が…

AOJ Problem 0090 : Overlaps of Seals

404 Not Found 円の交点座標を求めてその点を含んでいる円の数をカウントすればいいんだけど、 円の交点座標を求めるのがなかなか大変。三角関数とかベクトルを使わないと恐ろしいことになるっぽい。 ということで、 エクセルを用いた円と円の交点計算 を見…

AOJ Problem 0530 : Pyon-Pyon River Crossing

404 Not Found 謎のWAると心が折れそうになる。1行目の石が0の時を考慮していなかった。こういう見落としパチモンの時もあったけどデバグに時間掛かりすぎてヤバイ。 #include <iostream> #include <vector> #include <cstdlib> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) int main(){ int n , m; while(cin >> n</n;i++)></cstdlib></vector></iostream>…

AOJ Problem 0527 : Setting Go Stones

404 Not Found 最初に置く石の条件とか適当に付け加えてしまったせいで汚いソースになったけど方針としては、 同じ色で連続しているのを1つの要素にまとめる。 奇数番目だったら普通に置く。 (といっても、今の右端の色と同じだったらその要素に足すだけで、…

AOJ Problem 0538 : IOIOI

404 Not Found 例えばn = 1 の時、 "IOI"でカウントした後 "OI"がきたら絶対2カウント目する。(IOIOIになるから) n = 2の時も同様に、 "IOIOI"でカウントしたあと"OI"がきたら"IOIOIOI"が出来上がる。 それを利用してうまくやる。 #include <iostream> using namespace</iostream>…

AOJ Problem 0517 : Longest Steps

JOI本選に向けて過去問を解きまくる。 404 Not Found 白紙が1つだけということに注目する。もしひとつじゃなかったらしゃくとり法等で解くことが必要になるが、今回の場合はそうじゃないので、解き方を簡単にした。 配列を用意する。 連続している区間をカウ…

AOJ Problem 0215 : Pachimon Creature

404 Not Found やっと通った!! 問題文から次に手に入れるべきモンスターの属性はひとつに定まることがわかるのでDAGのDP?る。 最初自分が書いたコードでは、"S2345G"みたいなマップが与えられた時にNAを返していた。("1 5")が正しい。DPの初期化は気をつけな…

AOJ Problem 1020 : Cleaning Robot

404 Not Found [残りのバッテリー][y座標][x座標]で確率のDP! 常に等確率なのでやりやすい。 #include <iostream> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) const int dx[] ={ 0,1,0,-1}; const int dy[] ={-1,0,1, 0}; int main(){ int n; while(cin >> n , n){ long double dp[16][5][5] = {{{0.0}}}; char map[5][5]; rep(i,5)rep(…</n;i++)></iostream>

AOJ Problem 1209 : Square Coins

404 Not Found テーブル埋めていくタイプの組み合わせ数のDP! ループまわす順番間違えると重複数えしたりするから気をつけよう #include <iostream> #include <cstdlib> #include <cmath> #include <vector> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) int main(){ vector<int> tbl; int dp[301] = {0}; for(</n;i++)></vector></cmath></cstdlib></iostream>…

AOJ Problem 0146 : Lupin The 4th

404 Not Found 巡回セールスマン問題を面倒くさくした感じ。50分くらい掛かった。vectorじゃないと配列が取れなかったでござる・・・。 #include <iostream> #include <vector> #include <cstdlib> #include <algorithm> #include <cmath> using namespace std; #define rep(i,n) for(int i=0;i</cmath></algorithm></cstdlib></vector></iostream>

AOJ Problem 0191 : Baby Tree

404 Not Found ベイビーツリーはかわいい。動的計画法全く出来なかったので練習に。 昔一瞬取り組んで検討もつかなかった記憶があるけど、問題文をよく読んで因果関係とか考えるとなんか分かる気がした!ということでsolve。 直前に何使ったか情報しか要らな…

Member SRM 491 DIV2

仮眠取って、JOI予選直前だけど参加してきました。問題の一部をid:JAPLJ君が作問したらしい。div2 500もそれだったけど、良い問題だったと思います! 250 OneDigitDifference 1桁弄って最小の値を作れ。与えられた整数の最大の桁の値を0にしてやればいいこと…

JOI 2010/2011

今日の13:00 ~ 16:00にあったので出てきました。提出ミスが無ければ、 20 + 20 + 20 + 8 + 20 + 0 = 88. 本選行けるといいんだけど……。 今回特に悔しいのが問4.コンテスト中にDPを思いつかなかった。DPホント苦手。 終わってチャットとかしてたら、みんな解…

Codeforces School Personal Contest #3 (Winter Computer School 2010/11)

兼 Codeforces Beta Round #45 (ACM-ICPC Rules) 参加してきました。 結果から書くと、3完で、96位/218位(学生/全体)でした。 A→B→D→Cの順番で解いたはずだったんだけどCがWA出して、原因分からずコンテスト終了。 A. Rock-paper-scissors 効率的な実装法を…

SRM 489 DIV1

初Div1死亡 -25.0Ptで最下位 -X-(Challenge Succeeded.) 1202 → 1048 チャレンジせずにおとなしくしておけばこんな下がらなかっただろうに・・・。 0.0Ptの時は気をつけなければ。実際同じくらいのレートで0.0の人が30くらいしか下がってないのを見て後悔す…

Codeforces Beta Round #42 (Div. 2)

結果から言うと4完で28位/92位(DIV2/ALL)でした。 Cの問題文読み間違えてロスったり、Dのコーディングにえらい時間かかった挙句にコーナーケース見逃してて一回Hackされたりした。 A - Football よく分からんけど、頻出のチーム出力。 #define rep(i,n) for(…

Problem 0121 : Seven Puzzle

404 Not Found やっと解けたっていうか昔から一応正しい答え出すソースあったんだけど、ずっとTLEしてた。 原因は毎回手数を探索していたからで、最初に"01234567"から遷移できる全ての状態に対する手数をメモってから、それを出力するようにしたら高速化し…

AOJ Problem 1116 Jigsaw Puzzles for Computers

404 Not Found バックトラック。 #include <iostream> #include <vector> #include <algorithm> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define TOP 0 #define RIGHT 1 #define BOTTOM 2 #define LEFT 3 vector<string> puz(9); vector<string> cur(9); bool done[9]; int ret; bool diff(char a,char b){ if…</string></n;i++)></algorithm></vector></iostream>

SRM 487 div2 &amp; Codeforces School Team #3

とりあえず、Codeforcesの方は半分黒歴史的点数なので後で書く。今回のSRM。色々と残念な結果に終わりました。しかしレートは上がる。上がってくれるなよマジで。完全にチャレンジ回。 250 BunnyExamAfter ブラックはクズなので0点でした(全部不正解)。 そし…

CodeForces #41 Div2

最初鯖落ちしててはんぱなかった。ていうか2問しか解けなかったヤバイ。Eは解けそうで解けなかった。Dに至っては見てない。 A 文字列a,bが入力され、bがaの反転文字列になっているか判定。 #include <iostream> #include <algorithm> using namespace std; int main(){ string a,b</algorithm></iostream>…

Q.ryousanngata 2010/11/09 16:47 哲学? A.哲学です。

パソコン甲子園2010本選 出たもの

1.かっこいいコード書く 2.貪欲法 3.やる 4.計算式立てる 5.幅優先探索 6.効率化 7.確率(期待値)のDP 8.マイナス10進数 9.木構造をゴニョる 10.ダイクストラ + 効率化 11.ハミルトン閉路(想定解:バックトラック) 12.幾何学+強連結成分分解 僕たちは1から6番…

Problem 2206 : Compile

404 Not Found 簡単な実装問題なんだけど、39分掛かった。そろそろ大会だということで、問題を解くにしても時間を気にして解いている。 とりあえず提出でWA、原因分からない(26分)→ 5分後くらいにお邪魔ブロック消しのルールの解釈を間違っていたことに気づ…

ハニカム状を扱う

// Example: dy[i%2][d] ( i is 0-indexed ) const int dx[2][6] = {{ 1,-1, 0, 0,-1,-1},{ 1,-1, 0, 0, 1, 1}}; const int dy[2][6] = {{ 0, 0, 1,-1,-1, 1},{ 0, 0, 1,-1,-1, 1}};

SRM DIV2 486

人生初の全完…かと思いきや1000点の解法がおかしく死んだ。悔しい。 TxMsg 分かりそうで分からない問題。条件が謎かった。最初間違った解釈してて、途中で気づいて慌てて考え直した。stringstreamを使うと非常に楽。 198.08 Pt. #include <iostream> #include <vector> #includ</vector></iostream>…

CodeForces School Team Contest #1

先輩と同学年の子と参加した。開始して早々同学年の子は逃げ出してdxlibのお勉強をしていたので実質二人で解くことに(別に構わなかったけど)。 問題の傾向としては実装ハード杉問題が多くてライブラリ無いとやってられなかったのもあるし、そういう問題はAcc…

JAPLJ Contest

結局1問(A)しか解けなかった・・・。正直B,Cは部分点とりにいけば良かったと思っている。高校生が作った問題だとは思えないほどに難しいもの。id:JAPLJ君恐ろしい。 てか、Aの問題の意味を理解するのに2時間近く掛かったでござるの巻。 JAPLJ[B]も含めた結果…