全国高等専門学校プログラミングコンテスト有明大会 参加記

こんばんは！kagamizです.

2012/10/13 - 10/14の間に開催された, 高専プロコンの競技部門参加者としての参加記(主に参加するまでの過程)について記します.

続きを読む

今年度の目標の到達度(中間発表)

kyuridenamidaさんに便乗して書きます.

こんなことかいてました.

[必ず達成しなければならない!(must)こと]
・JOI本選に出場する. (?)
目標が春合宿(以上)に変わりつつありますが, 予選怖すぎなのでこれ大丈夫かわかんないです...

・AOJ Volume5の問題をすべて解く.(100% Scored : Passed System Test)
5月までの僕が頑張ってくれました. つらかった.
解いた問題たちは今でも活かせています.

・ AOJで500問解く. (66% Scored : Testing)
あの記事を執筆した時点では、 239問の問題をAOJで解いていたらしいです.
今は337問なのでゆったり感が... さすがに危機感を感じますやばい.

1.動的計画法の考えを用いる問題
2.特殊なデータ構造を用いる問題
3.グラフ構造を用いる問題
4.構文解析の問題
5.基本的なアルゴリズムを工夫した問題

1, 2, 3あたりは割りと解いていますが, なぜここに構文解析をいれたんだろうか...
とにもかくにも, あと163問なのです.


・EPOCH本選に出場する.(?)
とりあえずSubmitはしたのですが, チームをくんだのが月曜日なのでキツそう.

・PCK本選に出場する.(Accepted)
全国9位で予選通過なのです! 本選頑張ります～


[できると嬉しい!こと]
・応用情報技術者試験に合格する.(Accepted)
午後に奇跡的な点数で合格することが出来ました.わあい.(午前は余裕勢してました.)

・KOJの機能追加, サービス呼びかけ.(Testing)
やるやるいって全然できていなくて心苦しいです.しっかりしないとなあ.
早く公開できるように善処します!

・JMO本選に出場する.(?)
・JOI合宿、JMO合宿などに参加する.(Accepted)
・プチ研究をしてみる.(数学)(Failure)

[生活面で]
・計画をしっかり立てる.(Failure)
相変わらず目の前のタスクを殺して言ってる感じです, 武者ですネ.
計画ちゃんと立てれなくて色々殺されそうです. 今からでも計画できることはやるようにしよう.

・11時半に寝て, 5時半に起きよう.(不可能)
寝る時間はともかく, 5時半は僕には無理でしたぐぬぬ.

PCK予選

5完 (oooo-o----)でした. 34 / 100？ とか.
やはりこういうの緊張しますが, 先輩が落ち着かしてくれたので満足はしています.
本当に感謝しかないです.

続きを読む

K^2PC 解説Phase (kagamiz担当分)

こんにちは！ kagamizです.
去る8月17日に行われた, K^2PCの問題の解説を行いたいと思います.
公開遅いですね.後悔してます(激寒)

参加していただいた皆さん, ありがとうございました!!
また, コンテスト環境を提供してくれたAtCoder社の皆様, テスターをしていただいたfura2さん, CTPCに引き続き一緒に作問していただいたkyuridenamidaさんには大変お世話になりました.
たくさんの方の協力があって開けたコンテストでした. ありがとうございました!

きっときゅうりさんもそのうち公開してくれます.きっと.

続きを読む

JOIss参加記

かがみず(@kagamiz)が何かを思い出す度にこのページのボリュームは増えていきます. (Last update : 9 / 4)

続きを読む

[JOI合宿]2009-Day1:Sequence

循環性に気づくまでが勝負です.

まず, 奇数の数だけを知りたいので, 各数の下位ビットのみに注目します.
すると, それらの数を結合して, 2進数とみなすことができます.
鳩の巣原理っぽく考えると, 2^m個以上の相異なる項を作ることが出来ないのが分かり, かつ, ある2進数を作り出す規則は前の項に依存することより, この2進数列は循環することが分かります.

ゆえに, 実際に循環する2進数を列挙して, (1 ~ q項めの奇数の数) - (1 ~ p - 1項目の奇数の数)を求めてやれば良いです.

続きを読む

PKU 3254:Corn Fields

問題文 : http://poj.org/problem?id=3254
概要 : 0のところは必ず0で, 1のところは0または1にできる. このとき, 1が隣接しないようなマスの作り方は何通りあるか.

解法とか問題の種類とか:
簡単なbitDPです.
今見ている場所より上がvalidで, 下は今から決める, という考え方で, 考えるべき空間がグッと減るのがbitDPの良い所だなーと思います.

この問題は右と上に隣接することを念頭に置きながら考えないと行けないのですが, 今見ている場所が右端だとすると、右隣が無いことに注意しましょう.

続きを読む

AOJ 0245: Time Sale

全探索だと状態が爆発しちゃうので, メモ化できるところはメモ化してしまいたい問題です.
どの状態を保持するかを見極められるのが大切ですね. これできれば誰も苦労しないか...

続きを読む

AOJ 0244: Hot Spring

色々やり方があると思いますが, 僕は枝刈りDFSしました.

このコードを載せておいてなんですが, N^3全探索がオススメです.

続きを読む

[JOI合宿]2008-Day1:Flu

愚直に探索するとN^2になりますが, 周辺の点を調べると計算が減る感じの幅優先探索問題です.
O2つけると爆速でいいですね.

ソートが一番重くて, O(NlogN)くらいだと思います.

整数点のユークリッド距離は二乗しておくと誤差が怖くないです.

続きを読む