2つの趣味をやる一日(後編) AtCoder講義

3月9日は、午前中SIMPLOという若い方の集まる万年筆の会合に出席し、午後はAtCoder社長高橋直大氏の講義に出席するという、二足のわらじを履く日でした。午前中はアナログな万年筆の話で盛り上がり、午後は競技プログラミングの話をするというすごい日でした。その午後編の報告です。

「やってなんぼ」で普及しよう

万年筆愛好家と会うことが多く有ります。それはそうでしょう、私だってその中の一人なのですから…。競技プログラミングを普及しようとしている方とお話する機会が多く有ります。それはそうでしょう、私だって思いを共にしているのですから…。

日本のプログラミング大会とGCJJ

あちこちのプログラミングコンペティションに参加して、その参加記録をもうひとつのブログTatuyan's Pro-con blog!で公開しているわけですが、日本の大会と他の国の大会の違いが見えてきます。

「おめでとう、金メダル！」の価値

この度のIOI(国際情報オリンピック)を始めとする各科学五輪の日本人メダリストやGoogle Code Jamで優勝された方に、心から、「おめでとうございます」。このような活躍が日本全体を活気づけると思います。私はしがないプログラミング愛好者ですが、我がことのように喜び、近くにいた人と(その人は訳が分かっていなかったのですが)ハイタッチまで交わしてしまいました。

なのに・・・

強い参加意欲とその対比から見える気持ちの弱さ

EPOCH@まつやまという大会に、参加できるかどうかを真剣に考えています。資格はありますが、相手がいるかどうか、という点が問題です。

Codeforces Beta Round #75(Div.2) 参戦記

燦燦たる出来でした。

Aを5分で解答…まではいつも通り。

Bの問題の入力条件を「入力される2進数は10進法で10の6乗以下である」と勘違い。当然正解できるはずもなく、これに30分悩みます。(入力要件が実際は違ったので、方針自体を変えないと解ける問題ではありません)

その後、Cの問題に行きますが、いい解法を思いつかず、力任せで、当然TLE.

Dの問題もよく意味がわからず、今回はさっぱりでした。498位/937人、490点、当然Green落ち。
次回リベンジで、なんとか青になりましょう。

Codeforces Beta Round #74(Div.2) 参戦記

おなじみの参戦記です。

開始。万全の状態で、なにか後に控えていることもなく、気持よく参戦。
解き始めて、7分。まずはA問題をPretest Passedでした。

丁寧に考えて、計算回数が増えないように丁寧に組みなおして、32分でB問題Pretest Passedです。万全です。

その後C問題にとりかかりますが、ぱっと見ではやや難しいですが、丁寧に考えていきます。いろいろなケースを紙に書いて、じっくりと解いていきます。走行していくうちに、解き方が見えてきました。無事に解いて、ちょうど1時間でPretest Passed!です。

その後のD-E問題はとく気になりませんでしたし、また、hackにも取り組みましたが、なぜかなかなか表示されず、腹がたったので途中でやめて寝てしまいました。

朝起きてから確認すると、3問ともAcceptedで、2498点、39位/896人でした。そして、青くなることができました！嬉しい限りです♪

プログラミング大会の記事

少なからず、競技プログラミング/プログラミング大会の記事を載せています。そして、最近はTopCoder部の日記からもリンクを張っています。それを書いていて、どうすべきかと思ったのは…。

Topcoder SRM509(Div.2) 参戦記

前に用事があったので、10分ほど遅れての開始。

まず、250を見ます。回文数は再帰関数で組むことが多いので、久しぶりにJavaで再帰関数を組みました。今考えたら文字列化したほうが早かった気がします。Javaで文字列化する方法を調べるのが面倒だったので、ゆっくりやってしまいました。やはり、JavaやC++を鍛える必要がありそうです。Submitは151.78。ちょっと遅すぎです。

その後、500に移ります。今回は少し遅目の参加だったので後回しにしたのですが、ほとんど問題なく、アルゴリズムも悩まずに立ちました。Submitして、419.42。部屋内では2番目で、かなりありがたいスピードでした。

1000は解けず。1000を解けるように、もっと精進しないといけません。

結果、120/1204で、かなり良い成績。571.2でした。

Codeforces Beta Round #73(Div.2) 参戦記

ちょっと疲れていたので、ゆっくりする感じで参加。

問題Aを読み、解きます。ギターのコードの問題。普通に解きましたが、だいぶゆっくりだったため、解き終わったのは36分。

次いで問題B。方針はあっていると思うのですが、すごく汚いコード。WAでしたが、Pretest1とのこと。しかし、どの入力例に対しても、ローカルでは正しく出力しています。何が悪いのかがわからない…。もしわかる方がいらしたら教えてください。仕方ないので、問題Cに移ります。

問題Cは比較的好きな漸化式の問題。先にこちらを溶いておいたらよかったと思いましたが後の祭り。問題Bを諦めたのが残り20分で、コーディング間に合わず、結局問題Aしか解けませんでした。

順位は361/946で、得点は428でした。今ひとつです。最近ちょっと下降線なので、少し上げていきたいですね。問題はこちら。

UAPC2011/IPSC2011 参戦記

6月5日はUAPC2011/IPSC2011の両方が行われる日でした。両方共フル参加すれば楽しいのでしょうか、いろいろ立て込んでいましたので、UAPCは2時半から4時半、IPSCは7時から9時までの時間限定で参加しました。他の時間は、テスト勉強等で忙しくしていました。

今回色々読みましたが、テスト勉強できもそぞろだったからか、どちらも解けたのは一問目だけでした。もう少し落ち着いて大会に出たいものです。一息付ける時期がきたらSuperconの問題を解かないと…。

UAPCの第1問(A)は初心者の練習問題にも出来る問題で、ifを用いて丁寧に書けば書くことができました。

一方で、IPSCの第1問(A)はそれなりの問題でした。ジャンケンに似たゲームの問題です。私は一種のバックトラックで書きましたが、もっと効率的な解法があったのでしょうか。

UAPCはこちら、IPSCはこちらです。

Topcoder SRM508(Div.2) 参戦記

いまいちでした。

いつも通り500点からやろうとしたのですが、何をいっているかがわからない。しばらく考えても全くわからないので、250にチェンジ。250はそれなりに理解でき、何度か組み直しつつSubmit。でも、この段階で半分が過ぎていました。173.50。

それから1000へ。問題の意味はわかりましたが、さてどう解くか。いろいろ迷って、ビットに注目するのかな？と考えましたが、結局答えは出ませんでした。諦めついでに残り10分でSummaryを見ると…

ーーー250以外は誰も解けていないし、250も部屋内3位…

かなり難しかったのかもしれません。

そして撃墜ラウンド。私のすぐ下にいた人のコードを読んでみると、再帰処理をたくさん使っている。
「これは撃墜できるかも」
慣れないながらデータを作り、再帰回数ができるだけ多くなるようにして投げました。

--Challenging Success--

今までで初めて、私は撃墜することができました。
そしてその後です。
自分自身も撃墜されてしまい…。(よく読めば、問題にそぐわない回を出していたことがわかりました)

結果は50点、372/1362でした。

Supercon2011を前に

私がこの大会に参加したのは、もう5〜6年前になりますが、今年もSupercon2011が始まります。明日、6月1日から予選開始で、今年も3週間の予定です。ホームページはこちら。

Codechef 2011 May cook 参戦記

Codechefに初参加したので、その参戦記です。

開始後、とりあえず、一番おいしそうな名前の(本当にそういう理由です)"Popular Rice Recipe"に挑戦します。難しくありません、昨日のTopcoderでも似たような問題がありましたが、今度はCですのでもっと楽です。14minでaccept。

ですが、これ以降が情けないのです。

次に人数の多い、"Socializing Game around Pizza"に挑戦しますが、なかなかうまくいきません。幾つか予想をたてて、証明も考えました。
予想1:Bが勝つものに2,3を足したものはAが勝てる(これは理由があって、問題文から、Aは「Bが勝つ」形にピザを変形できます。Bが勝つ=その段階での後手が勝つ、なのでこの場合Aが勝てます。)
予想2:偶数ならAが勝つ(線対称に切って、対称性を崩さないようにすれば勝てます)。
まではうまく行ったのですが、ここから「4で割って１余るときだけBがかつ」としたのは勇み足でした。42minでWrong Answer。いろいろ考えるも、奇数の場合の処理が思いつかず、お手上げです。

仕方がないので戻ってみると、"Distribute idlis Equally"のほうが増えていたので、それを解きます。マージソートで実装して、次いでストランドソートを使いましたが、どちらもTLE。どうしたらよかったのでしょうか。

この段階で諦めて、1/5でした。コンペティションサイトはこちら。

Topcoder SRM507(Div.2)参戦記

久しぶりに書きます。次の日が休みということで、終わったあとすぐに書いています。

いつも通り開始。今回は途中休憩に250を当てようということで、まずは500から解きます。

色の塗り分け問題です。正方形の各面を、与えられた色で塗り分けられるかどうかを考えます。隣り合った面を同じ色で塗ってはいけません。塗り分けられますか？というものです。一色は2回しか使えませんから、最大カウントを2回として、いったい何色使えるかを数えればOKです。Submitして通り、374.77点。

次に250です。これはかなり単純で、場合分けをして考えればOKです。228.59でSubmit。

その後1000を解こうとしたのですが、フェルマーの4n+1定理、三平方和定理、四角数定理などと考えて、うまい方法が思いつかず、そのまま撃沈でした。

チャレンジフェーズでは一つ見つけたのですが追いつかず、他の人がわずかに早くとってしまいました。初チャレンジかと思ったのですが、惜しかったです。

合計点で、順位は370/1367でした。久しぶりでしたが、楽しかったです。後は、JavaもしくはC++にもっと慣れなければなりません。Cと僅かな道具で戦っているだけでは、正直厳しいと思っています。(が、その向上にあまり時間をかけられていないのが実情です…)。

UTPC2011自分の答案

UTPC2011、じっくり参加したかったのですが、実際にはこの後夜通しのイベントがあるので、そこまで気合を入れて参加したわけではありません。「間が悪いなー」というようなものです。ついでにいうと、Top Coder Open Qualify1はイベントとかぶっていて、参加できません。残念です。

実際に答えたのは2問だけでした。気持ちが落ち着かず、大して考えていないというのがその最たる理由ではありますが。一応、2問ともAcceptedでした。

Codeforces Beta Round #72(Div.2) 参戦記

終了10時間後からUTPC2011があるので、そのプラクティスまで入れて3ラウンドの真ん中に位置するCodeforces Beta Round #72に参加してきました。なお、UTPC2011はちょこちょこ参加する感じですが、この参戦記は後日。

第1問、これは良問。3n/2を出力すれば良い、ということを予想して解答、accepted。ここまで8分、好調。

第2問、いろいろ考えるが、ソートするとダメそうなので、前から愚直に「これを初項とする、条件を満たす部分列は…」と線形探索。後から考えれば、これでは当然遅すぎて、同じ数字からなる連続部分列の長さをnとして、n(n+1)/2がその部分から取れる数。愚かなミスです。当然TLEになるのですが、Pretest acceptedで油断しました。ここまで28分。

第3問、バイアスロンの的あて問題。これも第2問と全く同じ罠にはまります。これで50分です。

第4問、これはキューを愚直に弄るとアウトとなるとおもい、いろいろ変更してみますが、なんだかんだでキューを弄るのと変わらない時間がかかるプログラム。その上、痛恨のミスで、最後までacceptedが取れませんでした。

結果はaのみ正解で504/1042位、484点でした。問題はこちら

Topcoder SRM506(Div.2) 参戦記

最近レジストした後にすっぽかすとか、疲れてねるとかをしていたのでいつの間にかグレーにまで落ちていました。前回いまいちだったのもありますが、とりあえず、JAVAの練習がてら参加。

パソコンの調子がいまいちだったので、15分後からスタート。
ひとまず、500pointを見て解くのですが、なかなかうまくいきません。35分ぐらいかかって解きましたが、後から(後と言ってもかなり後です)難しく考えすぎていることに気づきます。

250pointの問題に移ります。色々書いていますが、なんのことはない「ある配列の最大値と各要素の差の総和を計算せよ。」というだけです。簡単すぎます。サラッと解いて、さすがに1000点問題をとくのは難しそうだったのでやめました。

結局、242点だけでした。

競技プログラミングの一抹の寂しさ

今でも競技プログラミングをしていますが、その中で、かつての「戦友」たちとの距離を感じます。

プログラミングの反省と目標

今月は競技プログラミングがものすごく多いので、参戦記でほとんどブログが埋まりそうなほどです。今分かっているだけで5月全体で約20回あります。

最近良くプログラミング大会に参加していますが、もう少し勉強したいと思うことが少なからずあります。

・C++の習得
・アルゴリズムの実装練習
・英語の読解力の練習(これは主にプログラミング向けですね)

プログラミング大会をしたあとで伸びないのはこれらが原因だと思っています。

ひとまず「ロベールのC++入門講座」と「プログラミングコンテストチャレンジブック」あたりを読了しないことには実力アップは見込めなさそうですので、この2冊を読了して、C++を鍛えて、来年の今頃には、もう少しましなプログラムを打ちたいものです。