Category Archives: ICPC練習会

専修大アジア地区予選練習会

初めまして.1年のわーるどです.
夏休み真っ盛りの9/26に,専修大学のICPCアジア地区予選練習会に行ってきました.
農工大からの参加メンバーは1年生3人(ヘクト・icchy・わーるど).1年生のみでの遠征は今年度初では無いでしょうか.
参加チームは,専修大・明治大・農工大からそれぞれ1チームずつの計3チームでした.農工大以外は構成員が2人のチームでした.

さて,今回扱った問題セットですが,さまざまな地区予選の問題を合計10問になるように接ぎ合わせたセットのようです.問題ごとに各地区独特の雰囲気が漂い,説明の段階で早くも経験値の少ない農工大チームの先が暗くなってきました.

結果は,専修大が3完・明治大が4完・農工大が2完となりました.
与えられる時間はアジア地区予選と同じ5時間なのですが,次の3つが足りないことがネックとなっていたように感じます.

1.英文の読解能力
2.時間計算量の見積もり能力
3.アルゴリズムの知識

1の欠如により,ざっくりとした問題概要は理解できるものの,条件の読み落としにより詰まるパターンがありました.

今の学内練習会のプログラムは上記の不足を補うことが可能であるものだと思うので,意識しながら取り組もう,という意識の高い提案が頭をよぎりました.

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焼いていた。
来年も国内予選を突破して、また参加したいです。

専修大主催合同練習会

お久しぶりです!
3か月ぶりでしょうか.にゃまとしては2年ぶりくらいです!

さて,久々の活動報告です.私とRyo君2人で専修大学主催の合同練習会に参加してきました.
7大学合同でICPC形式のコンテストをし,他大学と交流しながら競技プログラミングへのモチベーションを高めることを目的とした練習会です.

せっかくなので,事前準備と当日の私たちの活動(些細なものですが)についてまとめたいと思います

1.事前準備

実は,私もRyo君もB4で卒論で手一杯? で2人で練習はできませんでした.なので,2/4の1時間ほどの打ち合わせが全てでした.協議に関する内容は,大きく分けて以下の2つです.

  1. 当日のタイムチャート
  2. 練習メニュー

どちらも,上級者の方は基本作っています(みっちゃんさんの熱心な活動のおかげでこの準備もできるようになりました感謝).大したものではないですが,簡単に公開しますね.

1.1 タイムチャート

タイムチャートは,当日のコンテストの時間管理をするものです.私たちは2人なので,基本交互にコーディングするスタイルで設計しました.画像の通りです.

1時間ごとに打ち合わせを入れています.打ち合わせでその後の解答方針を決めることにしました.問題の難易度が分からなかったので,前半以外は割と適当で,1問辺り25分とるということと,バグが出てしまっても解けそうなときはペアプロをするという2つの方針しか立てていません.しかし,当日は割といい感じに機能したと思います.

1.2 練習メニュー

こればっかりは,2人で時間を取ることができなかったので各自ですることとしました.その際の練習メニューは,以前学習した内容を思い出すことを中心に,ダイクストラやDPなどの基本的な問題を1問ずつ解いてくることとしました.

私は結局時間が取れなくて1問も解きませんでした(土下座)が,Ryo君は何問か解いてきてくれたようで助かりました.

2.当日

練習不足を感じながらも当日は来てしまったので,とにかく打ち合わせの通りにやろうと頑張りました.ぬけぬけだったソースコードのファイル名やサンプルについてなど最後の取り決めをして,コンテストが始まりました.上級者の方を見習って当日の流れを書いてみます.

14:05~14:10

私がjavaのテンプレートを写している間にRyo君がA問を読み始める.Ryo君は解法は立った様子.

14:10~14:25

Ryo君がA問を書く.その間,私がB問を読んで紙コーディング.Ryo君のA問のサンプルが通らず,私の紙コーディングも手間取っていて雲行きが怪しく...

14:25~14:40

A問が煮詰まったので印刷してRyo君が紙デバッグ.私はB問を紙コーディングの通りに書いてAC.時間はオーバー気味.
でも,Ryo君はA問の紙デバッグが終わり,C問の読んで解法までたつ.

14:40~14:55

Ryo君がさくっとAをACmそのまま続けてC問のsmallを書く.そしてAC.私はD問を見て基本の素数判定+αでいいことを確認して方針を立てる.

14:55~15:00

C問largeは提出しないでおいて,私がD問を書いてAC.Ryo君には他の問題を確認してもらう.

15:00~15:10

E以降の問題について,お互いの問題解析について確認.E問はシミュレーション,Fは適当,Gは数論?というところまで話が進み,EがRyo君,Fが私と割り当てて問題を解く.

15:10~15:20

Ryo君がE問を丁寧に書いて1発AC.その間,私はFを連立方程式とみて空きの数値を解く.

15:20~15:30

私がFを書く.一部配列のインデックスが間違っていて時間を食ってしまうがAC.このとき,Ryo君がG以降を確認する.

15:30~15:40

思いのほか早く2問解いてしまったので,早めの2度目の打ち合わせ.Ryo君がHをDPで書けるじゃねという方針を提案.私は良く理解できなかったけど確かにいけそうだったので任せることに決定.私は,残されたところから,C問largeかJで悩み,どちらかというと確実なC問largeを考えることに決定.

15:40~15:50(ここから割と曖昧)

C問はローリングハッシュを使う(キリッ という方針を立てた私が書けるところだけ書く.Ryo君は紙コーディングして終了と同時にコーダーを入れ替わる.

15:50~16:20

Ryo君がHを書いて提出.しかしWA.私はCを紙コーディング.一度コーダーを変わってRyo君が紙デバッグをし,私がコーディング.途中でRyo君がデバッグし終わり,コーダー変わってちょろっと書き換えて提出したらAC.

16:20~16:55

私がClargeを書く.だがローリングハッシュなんて去年書いて以来なので苦戦する.なんとかバグを取り終わって提出しAC.

16:55~17:05

ラスト,G門を考えてタイムアップ.

細かくなってしまいましたがだいたいこんな感じ.今回は割と連携がうまく取れたと思います.おかげでいい感じの成績を取ることができました.もう少し時間があれば,Jに取り組めたのではないかと思います.こればっかりは練習不足なので次回への課題ですね.

懇親会では,問題のことだけでなく様々な話題で盛り上がれて楽しかったです.皆さん競技プログラミングに意欲的でうかうかしていられないですね.良いモチベーションのアップになりました.

まとめ・感想

前半期以来,久々の練習会でしたが,中々な成績を取れてよかったです.同時に,他大の練習量なども見られて有意義な練習会でした.これを機に私たちも練習をちゃんとしていけたらと思います.このような機会を用意して頂いた専修大学の皆さん,本当にありがとうございました.次回は後輩を連れて行きたいです(チラッ).

P.S. 練習会とは別の機会に,交流会や人狼や人狼ができたらそれはそれはうれしいですね!