Monthly Archives: 9月 2013

JAG夏合宿に参加しました。

初めまして、1年生のヘクトです。
競技プロを初めてだいたい半年くらいになります。(プログラミングを初めて半年でもあります)
今回の活動報告は私とにゃま先輩とRyo君先輩の3人でJAGの夏合宿に初めて参加しました。
アジア地区予選に向けて、ICPC形式のコンテストをウォーミングアップを含めて4セット行いました。
参加者はICPC国内予選を突破した上位陣がメインでしたので、参加者のレベルと問題の難易度は高く、ACが取れるのか不安でした。しかし、来年に向けていい経験になりました。来年はアジア地区予選に行きたいです。(ICPC国内予選については3問ACでした。)
では、簡単にそれぞれの日の内容と取り組んだ問題セットについて振り返ります。
チーム名はLabHecで参加しました。

初日 懇親会
他大学の方とアルゴリズムやTopcoderやCodeforcesの話ができて面白かったです。(cookieも焼いていました。)
(この日の夜にCodeforces #201があって、合宿参加者の一部はやっていたみたいです。)

二日目
この日は2つ問題セットがありました。
午前中はウォーミングアップ(という名のハラスメント) KMCoderセット  3時間セット
A 巡回スケジューリング問題
実装を試みるもWA なお、蟻本に書いてあったみたいです。
D Union-Findを使って、クエリを逆から読めばいけるみたいだが、なぜかWA
J 数列が与えられて、ある手順でK回シャッフルする中で前半分の数列の和の最大値を求める問題
シャッフルされた後の前半分の和がたかだか数列の長さ通りしかないことに気づき、すべて列挙して
からシャッフルをして判定していく方法でAC
Jが思いついたのは感が冴えており、しかも終了2分前でした、
結果 1AC

午後はThe hik Revolutionsさんのセット
A 変わった距離尺度上でWifiが全ての範囲に届くかという問題
いもす法を使い先輩がAC
B 最適な場合の脱出人数を求める問題 シミュレーション
方針を先輩と一緒に考える。それを先輩が実装するAC
G 巡回置換を行った時にある範囲が一周するまでのその範囲の和を求める問題
方針が思いつくが、サンプルと答えが合わない。 RMQというデータ構造が必要だった模様。
結果 2AC

三日目
この日は1つ問題セットがありました。
++++w++++さんとnegainoidoさんのセット
A DP 最初、greebyに近い方法で解き、WA テストケースからgreebyではないことがわかり、DP考えるも時間切れ。
B ダイクストラを走らせて最短距離を求めてから、始点と終点から2回bfsして始点と終点からのある距離の個数
を求める。そして、組み合わせる。一回int型でやり、overflowしてWA テストケースの名前からlongに変えてAC。
C 鏡像と二分探索 本番では解けませんでしたが、翌日ACしました。
D 法則ゲー 自分がn=3の時に計算ミスしていたため解くのに時間がかかった。先輩が理解して、AC
実装はすぐにできました。
G 構文解析 演算子の優先順位をすべて等しくして、計算式の括弧の付け方でなんとかしようとするも実装間に合わず。
K くるくるくるりん 闇です。解説のアニメーションすごかった。ジャッジがジャッジできないなんてことあるんだ。
結果 2AC

四日目
この日は1つ問題セットがありました。
JAGのOB/OG会のセット
A 木構造 先輩たちに任せる。 AC
B スタッフの動きをシュミレーションしてグラフを作り、ダイクストラ法で解けるとまず思いつく。
実行時間からこれで通るだろうとわかり、書くもTLE。ヒントが出るもそのことは理解していた。その後先輩にダイクストラ法をプライオリティキューを使って、高速化してAC。
C なんかうまい方法でもあるのかなと考えるも思いつかず。
F 行列累乗と連立方程式
まず、方針がよくわからない。シミュレーションは計算量的に不可。問題文のタイトルがオートマトンだったので、
2012年のアジア地区予選の問題が浮かぶ。実行時間を見る。10sと長い。行列累乗で解けるのでは?
先輩が遷移を行列の掛け算で求めることを証明した。蟻本のライブラリを写す。解が1つの時はちゃんと解けるみたい。しかし、解なしか複数かの判定方法が思い出せない。とりあえず、書いてみる。WAとRE                            (係数行列と拡大係数行列のrankの値を見ればよかったみたいです。)
結果 2AC

結果として、どのセットも0ACを避けられたので今回は良かったです。(また、自分もチームにかなり貢献できたので良かったです。)
合宿中のピックアップ
・くるくるくるりんの再現アニメーションがすごかった。
・みなさんcookie焼いていた。
来年も国内予選を突破して、また参加したいです。

KAIT練習会

先月8/29に神奈川工科大学(KAIT)で開かれたICPC練習会にお邪魔してきました。
ジャッジサーバーはKAITの方が建てたサーバーを利用させて頂き、問題はMCCの部員が作問したセットとKAITの方々が作問したセットを順番に解きました。

MCCセットの大まかなジャンルは、
A:シミュレーション
B:探索
C:幾何
D:Dijkstra
といった感じでした。

始めにMCCのセットを他大学の人たちに解いてもらったのですがほとんどの人がA問で苦戦して、始めにA問がACされたのは開始後15分でしたが、一番多くACした人でもA・B問だけで、C問についてはSubmitすらされていませんでした。
A問は単にやるだけなのですが落とし穴がいくつかあり、そこでつまづいた人が多かったようです。

今回持ち込んだ4問中3問が1年生による作問だったのですが、どれも1年生が作ったとは思えない良問でした。

前半のMCCセットが終わると、今度はKAITセットを解きました。
MCCセットよりは優しめだったようで、全完の方もいらっしゃいました。

双方の問題セットを解き終わった後、作問者による解説が行われました。
1年生は作問も解説も初めてのことでしたが、頑張っていました。

両方の解説が終わったあとは同大学の研究室をお借りして懇親会を開き、談笑やLTをしながら交流を深めました。