読者です 読者をやめる 読者になる 読者になる

PCK(パソコン甲子園)2012予選

今年は出れて良かった~!!!去年は台風の影響でクソつまらない再予選受けたので。 P040 Ryu☆年(たつどし)で,id:refiute君と出ました。 相方の参加記: eristical 結果 まず結果から言うと、1~9を解いて9完/10問でした。たぶん80点/100点? WAペナルティ数は…

JOI夏季セミ2012

一日目 新幹線降りてすぐオリセンに。なんかぼちぼち人がいて、原将己(後のqnighyである)とかが待ち構えている。 superconで見た灘勢(catupperさん,指圧マットさん,intさん)がチーム1つ丸ごとみたいな感じでいた。ついてまもなくli_sakuとjapljがセットで来…

supercon2012

一日目 drafearと梅田で待ち合わせして石橋向かう。石橋駅で切符旅費証明としてもらおうにも係員がいなくてあたふた。 あたふたしてたらroxion,さて,ふるーつご一行と遭遇。 asiさんがいるゾ~~~チューターや。阪大でrefiute待つ。その間iPadで遊ぶ 後ろの…

AOJ 0247 Ice Maze

問題文 Ice Maze 感想 本番じゃ手出したくない部類の問題だなあ。 枝刈り探索。semiexpが自明な枝刈りするだけで通ったと言っていたのを思い出して解いた。 ただ1.0sとか厳しくて、1.5sくらいでTLEしててハマってた。もっと自明な枝刈りしたら普通に通ってワ…

AOJ 0246 Bara-Bara Manju

問題文 Bara-Bara Manju 感想 難しいが良問。去年の予選終わったあと、バックトラックとかしてて泥沼にはまってしまって、わかんなかったのでsemiexp先生に解法教えてもらった。 ただAOJのテストケース厳しいナァ。 ほかの人たぶん違う解法をしていて気にな…

AOJ 0245 Time Sale

問題文 Time Sale 感想 なんか探索多いけど、これもその1つ。ただこれは状態の持ち方間違えなければ普通に間に合う。 もし時刻tを持てなかったら割りと実装が大変になるんですが、さすがにPCK優しいので楽。問題文うろ覚えている程度には知ってたので、昨日…

AOJ 0244 Hot Spring Trip

問題文 Hot Spring Trip 感想 明らかに前問より簡単。ダイクストラを用いた最短経路問題に慣れていたらやるだけに感じた。10分で書けた。これ10分ってタイピング速度向上してる感ある。 DPするにしても探索するにしても何にしてもそうだけど、状態に対する感…

AOJ 0243 Filling Game

問題文 Filling Game 感想 この位置にあるしどうせ枝刈り全探索だと思って適当に15分くらいで書いて投げたらなぜか通ってしかも自分以外に1人しか通ってなかったので???ってなった。(まあ本番とはテストケース違うけど) 運良かったのか。こういう怪しいの何…

AOJ 0242 Input Candidates

問題文 Input Candidates 感想 とても悪名高い予選問題の1つ。AOJのテストケースは知らないが本番では改行コードがCR+LFだったので見えない制御文字\rに苦しめられた人々がたくさんいた。 解法 日頃からちゃんと\r消す習慣つけとくと嬉しい。 stringとかmap…

AOJ 0241 Quaternion Multiplication

問題文 Quaternion Multiplication 感想 うまく実装してくださいっての好き。 解法 やるだけだが、上手いやり方を思いつかなきゃいけないあたり好き。普通に手計算したりするのはちょっと恐すぎるし、それで泥沼にはまったら予選落ちメニーチャンシーズなの…

AOJ 0240 Interest Rates

問題文 Interest Rates 感想 複利の場合の誤差が恐い(1.001)^30乗とか2^30とか大きくて恐いがまあ通りそうだと思った。 解法 元のお金は1円として考える。 ソース 実装マジで下手。 #include <iostream> #include <algorithm> #include <cstdio> #include <vector> #include <cmath> using namespace std;</cmath></vector></cstdio></algorithm></iostream>…

AOJ 0239 Calorie Counting

問題文 Calorie Counting 感想 絶望的に条件を拾いづらくしており悪質。 解法 読んだらあとは実装すると通る。 ソース 実装下手 #include <iostream> #include <cstdio> using namespace std; int II[1000] , PP[1000] , QQ[1000] , RR[1000]; int main(){ int n; while(cin >></cstdio></iostream>…

AOJ 0238 Time to Study

問題文 Time to Study 感想 読みやすいこともない。 解法 素直に実装する。 ソース ふつう。 #include <iostream> #include <cstdio> using namespace std; int main(){ int t; while(cin >> t && t){ int n; cin >> n; int s = 0; for(int i = 0 ; i < n; i++){ int a,b; cin </cstdio></iostream>…

パソコン甲子園2011 予選・解法

PCK2011予選。僕は去年台風で予選参加できなかったのですが、今回AOJにその問題があがったので解いてみました。 1. 勉強の時間(4点) : AOJ 0238 Time to Study - kyuridenamidaのチラ裏 2. カロリー計算(4点) : AOJ 0239 Calorie Counting - kyuridenamid…

WUPC2012

お久しぶりです。ブログ更新してませんでした。 WUPC2012(早稲田大学プログラミングコンテスト2012)にオンライン参加しました。僕は早稲田の学生ではないです。 結果から言うと全体で2位でした。良かったんじゃないかなと思います。 運営の皆さん、お疲れ様…

SRM540 Div1

o-- 110点くらい + チャレンジで210位/950人くらい。レーティングは1660くらいから1730くらいに伸びた。 Easy 250 n個の数字をn-1個の演算子(+か-)で結んだ数式があります。 1 + 2 + 3 + 4 とか。 その隣接したペアを計算するとn-1個の数が出ます。1+2+3+4→ …

SRM539 Div1

一応Easy早解きしましたがUnratedになりました。 Easy 250 問題文 本当にうろ覚えなので嘘かも。なんかある箱を使うと石を少なくともx個,最大でもy取り出さなきゃいけないという制約があって、箱の使い方は任意。 9000より大きい石を得たい。その条件下で"石…

copy and paste (JOI)

今さら感ありすぎてオワコンな上に赤黒実装ではないため生ゴミ。 実装は RBST(≠Treap) + 永続化 + メモリやばげなら再構築とかいう多分模範解答に近い。 思ったこと RBSTはmerge/splitベースの実装じゃないとよろしくない。 newより連続した配列確保したほう…

Day5 (合宿まとめ)

チューターがフレンドリーであった チューターとか生徒とかにペロリンが人気であった 問題は難しすぎた 問題文をちゃんと読みましょう が心に染みた たぶんもうこういうハラハラする機会ないんだろうけど 合宿問題に自分が愛用しているアルゴリズムとかが全…

Day4

Opened 0/100 Compiled 0/100 Opened 0/100 Total 178/1200 2番楽しかった(絶望)

Day3

MLE 70/100 Opened 0/100 Opened 0/100 Total : 178/900 動的セグ木は使わないようにしましょう( 空間使用量がO(n)→O(n log n)になるのでやばい) 閉区間やめます

Day2

98% Accpeted 98/100 Opened 0/100 Compiled 10/100 Total : 108 / 600 yabasugi

Day1

Opened 0/100 Compiled 0/100 Unopened 0/100 Total : 0 / 300 hidosugi

SRM 537

Div1で参加。レーティングは1582→1662らしい。 Easy A,B,Xが与えられて、A,Bのセットで支払える硬貨を完全に含む(X,Y)というセットを新たに作りたい。 A != B , X != Yである。無限にそういうX,Yの組を作れる場合は-1,有限ならその個数を出力しなさい。Yを決…

COCI CONTEST #5

1時からSRMなので、20分遅れくらいで1時間半もないくらい適当に参加。英語が読みやすい。 Križaljka 50/50 問題文 : 単語A,Bが与えられるので、クロスワード作りなさい。 感想 : はい。細かい制約(何を優先するとか)全く読まずに投げたので落ちそうでしたが…

CTPC

お疲れ様でした。参加ありがとうございました。僕は運営してました。 404 Not Found 404 Not Found 高専枠の natrium11321 Tan HETARE さんそれぞれ1位,2位,3位おめでとうございます。 一般枠の k_yuridenamida k_operafan tozangezan chokudai Komaki uwi h…

AOJ 2270 - The L-th Number

問題文: The L-th Number | Aizu Online Judge 想定解ではない計算量で解いたらしい。問題文は日本語なので省略。この記事、説明不足が多すぎるので注意。 解法 ※僕がこの問題でやったHeavy-Light分割、適当なことしているので嘘っぽいです。信用しないでく…

UVa BUET Inter-University Programming Contest - 2011

コンテストサイト : UVa Online Judge 解いたのはA,E,Hだけ。他は一部読んだけど分からなくて、半分くらいは読んでないかも。そもそもAだけ解いて消えるつもりだったのでよいかなと思いました。 でも、要求される知識としては、JOI的にも良い感じのコンテ…

合宿問題

便乗。 (□正答っぽいがジャッジしてない,△=方針が嘘っぽい,怪=方針は合っているはずだがバグ取れない,-=未着手,思=実装してない) 2007 問題名状態記事 Score□ Factorial□ Mall□ Building□ Fermat□ Salt- Anagram□ Route□ Circuit△ Fiber□ Lines怪 …

JOI 2011-2012 本選(読みにくい)

結果から書くと、100+100+100+20+0 = 320でAランク、つまり合宿に行けます。 恐らく去年合宿行った高1で300点台を取ってしまったのは"僕だけ"っぽい?のでこれはちょっと悔しいですが、何はともあれ通過です。 まあ土日にあったことを記録しておきます…

AOJ 0552 Exposition

問題文 Exposition | Aizu Online Judge 感想 かなり時間かけた。解けると嬉しいですねえ。問題文は日本語なので略。これが距離の総和とかだったらどうやって解くんだろう・・・。誰もブログに解法書いてくれないし情報オリンピックも解法公開しないし陰謀じ…

Codeforces Beta Round #1 C. Ancient Berland Circus

問題ページ Problem - C - Codeforces 問題文 現在では、バーランドの円型競技場は、直径13mの円型アリーナを持っていますが、昔はそうではありませんでした。 古代バーランドの円方競技場のアリーナの形は正多角形でした。その大きさと角度はそれぞれの闘技…

Codeforces Beta Round #1 B. Spreadsheets

問題ページ Problem - B - Codeforces 問題文 人気な表計算システム(例えばExcelとか)では、列の表現方法として、以下に述べる方法が使われています。 1列目はAという番号を持っています。2列目はB,3列目はC,...,26列目はZという番号を持っています。 それ以…

Codeforces Beta Round #1 A. Theatre Square

問題ページ Problem - A - Codeforces 問題文 首都バーランドにある劇場広場はn×mの長方形の形をしています。都市の記念日に際し、広場を花こう岩敷石で舗装することにしました。それぞれの敷石はa×aのサイズを持っています。広場全体を舗装するのに必要な敷…

目標

学内の人意識高すぎるから。 とりあえず実現できそうな順に。(最初そう思っていたが書き終えてみたら方針変更してた) 競技プログラミング TopCoder 年末までに●じゃないにしても、レート1850~1900くらい目指したい。 そのためにMedium安定させたい。あと少…

PKU3579 Median

問題URL: 3579 -- Median 問題文: n個の1次元座標が与えられるので、それで作れるnC2通りのペアの距離リストを作って、それらの中央値を求めろという問題。奇数の場合はそのまま中央値で、偶数の場合はn/2番目のものを求める。 感想: ちょっと悩んだ。こうい…

PKU 3378 Crazy Thairs

問題: 3378 -- Crazy Thairs 問題概要: 長さNの数列aが与えられる。i < j < k < l < m かつ、a_i < a_j < a_k < a_l < a_mであるような要素の組は何個ありますかという問題。 同じ値が2度出てくるのかとか、もし出てきた場合に今まで出来たやつと同じになっ…

PKU 3250 Bad Hair Day

問題: 3250 -- Bad Hair Day 問題概要: 牛さんが右向きで並んでる。 それぞれの牛について、自分より右方向かつ自分が見渡すことの出来る範囲(=自分より厳密に小さいやつしかいない範囲)にいる牛の数を数え、それを合計したものを出力する。アスキーアート図…

PKU2019 Cornfields

問題: 2019 -- Cornfields 問題概要: N * N の整数(N<=250)で満たされたフィールドが与えられる。二次元区間は正方形でサイズは予めB*Bと決まっている。クエリの数Kが与えられるので、各クエリ毎に与えられる(R,C)の組が左上頂点(?)であるようなB*Bの正方形…

「TopCoder 飲み会 2011 @大阪」に参加してきた(りんごジュースだよ)

snukeが書いていたので。↓ 2011-12-29 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ 集合前 refiuteとかmecha_g3さんとkyubunsの家で過ごす。 mecha_g3が1500円くらいするチーズケーキ買ってきたのでkyubunsのMBAで切る。→チーズケーキを包丁無…

UVa - 7th Contest of Newbies

年越しコンテスト(12/31 21:00 ~ 01/01 1:00)参加してきました。 どこがNewbiesやねん・・・。 蕎麦食ったりしつつも真面目に参加していて、結果としては5位/114人でした。とりあえず3時間だと思ったら4時間で、残り1問解けそうで解けない感じだったので…

2012

合宿行って500点取る ●kyuridenamida

JOI予選2011-2012

ハッピー。 ID J120012GB 予選ランク Aランク 得点 120

JOI2011-2012予選 問6 ジグザグ数 (Zig-Zag Numbers)のソース

さすがに遅いので書き足した。たしかに500倍くらい速くなった。与えられるAをジグザグ数か判定することによって多倍長回避。60行くらいでシンプル(ただそれでもreading-hard) #include <iostream> #include <algorithm> #include <cstring> using namespace std; int M; int memo[512][16][</cstring></algorithm></iostream>…

JOI予選2011-2012

1<2<3<4<5<6の順番に実装の時間が掛かったけど、1~4が(例年より)難しくて、難問が易化してた気がする。JOIは去年みたいな感じで、4番解けなくても実装力(と知識)ある人が5番解けるようにしているのだろうか。 見直し結構したので提出ミスはないはずだけど、…

PCK2011本選

3完なのでさすがのきゅうりも猛省。とりあえず本当にごめんなさい。こんなことになるなんて! 問1 ポーカーのストレートとかがない役判定。後輩がやった。あとで読んだら実装量が例年より多いらしく、一発で通すrefiuteかっこいい。 問2 3つの条件があって、…

AOJ 0542 Authentication Level (JOI2008-2009本選 認証レベル)

昔はダメだったのに、最近読んだらすんなり読解成功したので解いた。今年は合宿まで行ったのに今さらという感じだが。 Authentication Level 問題: なんか2つの事務所があります。 それぞれの事務所には部屋(長方形のマスみたいな感じ)で、複数あります。 そ…

PCK再予選

通過してました。再予選組みんな真面目に参加していたことが分かって感動しました。 さすがに満点(1WA)で落ちたら諦めようと思っていました。 P21『P ≠ notP』として参加します。後輩であるid:refiuteと参加するのでよろしくお願いします!

AOJ 2288 Oh, My Goat!

今思えば意外にすんなり解いたもののアイデアは力作っぽいので、別記事にした。 H Oh, My Goat! 全力で怪しい解法をしたが、まあ辺数的にも状態数少なそうなのでどうとでもなりそうだったし予想を大きく裏切り一瞬で通った。 まあ基本方針として、与えられる…

RUPCあとで解いた

PCKの悲しい処理をしていて貴重なコンテストであるRUPCに参加できなかったので、解いてみた。 自分の実力にはちょうどよいコンテストだった気がします。幾何は読んでません。あとリーディングハード多かったです。 A Swap Cipher これはPCK開始直前に解いた…