主人が競技プログラミングを始めて一年が経ちました

はじめに

いきなりの投稿失礼します。 久光さやか、29歳の未亡人です。 お互いのニーズに合致しそうだと思い、記事を書いてみました。 自分のことを少し語ります。 昨年の5月、わけあって競技プログラミングをはじめました。 自分は…アルゴリズムのことを…死ぬまで何も理解していなかったのが とても悔やまれます。 主人はTopcoderに頻繁に参加していたのですが、 それは遊びの為のプログラミングコンテストではなかったのです。 レーティングを得るために、私に内緒であんな危険なchallengeをしていたなんて。 一年が経過して、ようやく主人の0完+チャレンジ失敗から立ち直ってきました。 ですが、お恥ずかしい話ですが、毎日の孤独な夜に、 身体の火照りが止まらなくなる時間も増えてきました。 主人の残した財産は僅少なレーティングです。 つまり、WAは幾らでも出きますので、 私の競プロ欲を満たして欲しいのです。 お返事を頂けましたら、もっと詳しい話をしたいと 考えています。連絡、待っていますね。

レーティング

AtCoder

半年前: 1728(青)→ 現在: 1930(青) / highest: 1930 (2017/06/24)

f:id:fluffyowl:20170626204650p:plain

メインで参加しているプロコンサイトです。レーティングの面では残念ながら色を変えるほどには上げられませんでした。 きりよく一年で黄色になれましたと言いたいところだったんですが……。ただ最近は全然振るわない時期を抜けて少しずつhighestを更新できているので、1年半経つ前には黄色に届きたいですね。

Codeforces

半年前: 1579(緑)→ 現在: 1928(紫) / highest: 1952 (2017/04/21)

f:id:fluffyowl:20170626195423p:plain

AtCoderほどではないですがこっちも結構参加しています。振り返ると半年前は4回しか参加してなかったんですね。一時期全然解けないしシステムテスト落ちるし問題文が読みづらすぎるしでマジで苦手だったんですが最近は結構解けるので好きです。あとAtCoder, Codeforces, Topcoderの中で唯一青より上に行けているので好きです。Div1残留安定が目標。

Topcoder SRM

半年前: 参加経験なし → 現在: 1215(青) / highest: 1428 (2017/02/09)

f:id:fluffyowl:20170626200338p:plain

微妙なところです。最初結構順調で黄色楽勝じゃんとか調子こいてたんですが負の点数取って一気に緑に落ちたりして今は間くらいで落ち着いてます。開催自体が少ないのと平日昼間にやることが多くて参加回数増えない・フィードバックなしのチャレンジありなので点数も安定しないといった理由でレーティングが収束してるような感触が全然ありません。とはいえ分散がでかければその分上振れする余地もでかいと思うので黄色に一番近いのはここかな〜と勝手に思ってます。

その他のコンテスト

CSAcademyとかHackerRankとかCodechefとかにたまに参加しています。

過去問埋め

だいたいAtCoderかyukicoderの過去問を埋めています。yukicoderは最近レベル75になりました。しばらく考えてわからない問題は割とホイホイ解説を見てしまっています。知識面に関しては黄色目標レベルなら「知らなかったから解けなかった」はもうほぼないかなとなってきたので最近は考え方とか発想とかそういうところを吸収するようにしたいな〜〜って感じです。

今日ツイッターで流行っていたやつだとこんな感じ

そろそろTopcoderとかCodeforcesも埋めていきたいですね。

その他の進捗

オンサイトに出れた

前の記事の話ですが、RCOさんの日本橋ハーフマラソンの本戦に出ることができました。念願の初競プロ衣服も頂けてとても嬉しい経験でした。思い返すとこのコンテストは突出しなくていい(2問両方でそこそこの得点を取るのでも上位に行ける可能性がある)という点で自分に合っていて運が良かったな〜〜と思います。

GCJでTシャツ

Google Code JamでTシャツがもらえました。1000位以内でTシャツのところ999位に滑り込み(終了時点では1004位とかで一日経ったらなぜか順位上がっていてマジで滑り込みだった)、2つ目の競プロ衣服獲得となりました。パーカー・Tシャツときてるのでズボンとか靴下とかを配るプログラミングコンテストが待たれます。

マラソンにも手を出した

上の日本橋ハーフマラソンの件とも関連しますが長期間のコンテストにもちょいちょい手を出したりしています。Topcoder MM, Codingameなど。実力不足による徒労感があったりして最初の方ほどモチベーションは高くないですが…。

競技プログラミングの効能

  • 楽しい!
  • コーディング欲が満たせる!
  • 日々の生活に小さな目標ができる!
  • 10歳下の人にボコボコにされる!

おわりに

半年時点で記事書いておいて今回書かないのもあれかな〜と思いつつぐだぐだ引き伸ばしてたら1年と1ヶ月になってしまいました。他にすることないし競プロはまだまだ楽しいし、今のところ飽きる気配はなさそうです。最近はKaggleとか、あと大学の数学をちゃんとやるのとかに興味が発展してきてるのでそっちの方もやっていってよい循環を作れたらいいですね。あとこれは競プロだけじゃないんですがなにかしらを作ることに取り組んでいきたいという気持ちも出始めました。競プロの作問でもいいし競プロ関係ないプログラミングでもいいし絵でも小説でもいいのでなんか創作物を作ることも日常の活動に加えていけたらな〜という感じです。どうもありがとうございました。

RCO presents 日本橋ハーフマラソンに参加しました

3/20にRCO presents 日本橋ハーフマラソンに参加しました。競プロをやりだしたのが学生じゃなくなってからなので、予選付きコンテストでオンサイトに出ることは半ばあきらめていたんですが、予選でギリギリ引っかかって上げてもらいました。感謝です。

予選

A問題 Multiple Pieces

最初山登り的なものを実装しようとするが、実装が難しく最初の提出まで1時間かかった上に点数が泡を吹くほど低い。ただ低すぎたおかげで逆にそこまでの方針を捨てる踏ん切りがついて、ごくごく単純な貪欲で書き直したら点数が10倍くらい上がってそこそこの順位に。具体的には「全マスを大きい順のpriority queueに突っ込む→順に取り出して周りの大きいマスと貪欲にくっつけていく」という感じ。単純すぎて制限時間10sのところ6msで終わってしまう。このあたりで3時間中の1時間半くらいが経っていたので一旦よしとしてB問題へ行くことにする。

B問題 Food Collector

今度は時間をかけすぎたら終わりなのでA問題の教訓を活かしてとにかくまずは単純な方針からやっていこうと考える。ということで「初期解として完全ランダムにターン数分の移動命令を生成 → 何ターン分かの移動をランダムに変えてシミュレート → よくなるならその解に乗り換える」という山登りを10秒いっぱい回す。割とまともな点数が出て一安心し、残りの時間はこの方針をベースにして逐次改善していこうとしたが大して変わらず終了。

結果

A問題50位+B問題73位で、全体49位。だいぶ微妙でしたが上位にオンサイト不参加者も何名かいたようで、「学生の上位40名を抜いたあとの上位10名枠」の9番目につけてギリギリ本戦に通してもらえました。

本戦

開始前

開始までは後ろの方に座ってぼやぼやしながらオンサイトの雰囲気を味わった。あと参加賞ということでパーカーをもらった。競技プログラミングで衣服をもらうのがひそかな目標だったのでとても嬉しかったです。あと気がつくと真後ろの席にAtCoderの社長が座っていてヒョエ〜〜〜〜となった。あと業務の説明を聞いてたのしそ〜〜〜となった。

A問題 石油王Xの憂鬱

問題文を読んだだけで変な汗が出た。めちゃくちゃ苦手な算数パズル(天秤をn回使って偽物の金貨を特定してくださいみたいな類のやつ)っぽかったからである。ちょっと考えるけど取れる行動も多いし方針すらまったく立たないのでさっさとB問題へ。

B問題 日本橋大渋滞

こっちはA問題と比べるとだいぶ素直な印象を受けた。まず何も考えず全車を目的地に向かわせる貪欲解を書いたところ、0だけの自明解(3331点)をちょっとだけ超える(4613点)。ここでビジュアライザを見てみると、どうやら車が多すぎてほとんどの車がまともに動けてないことがわかった。要するにこれをどうにかする問題なんだな〜〜〜とやっとこの段階で気づく。とにかくどこかで回り道させないといけないので、ある車が目的地に近づけない場合はランダムな移動を行うようにするとちょっと上がる(6513点)。たしかこの時点でB問題だと2位か3位を取れていてかなりウキウキしたが、1位の人を見ると60万点とかいう異次元のスコアを出していて最初真剣にバグか?????と思った。さすがにここまでスコア差がつくということは根本的にもっといいやり方がなんかあると思ってスコアの計算式をよく読んでみると、かかったターン数で割り算が発生しており桁違いの差が付くならこの辺が鍵かなあなどと考える。自分の解を省みると制限ターンいっぱい使っていたのでこれは明らかにダメだろうと思い、解を得た段階でスコアの動きをシミュレートし一番よいターンで打ちきって出力とすることしてみる(12478点)。数十万のオーダーには全然届かないが順位的にはかなりよかったのでB問題はここで一旦やめにしてA問題へ。

A問題ふたたび

相変わらずアイデアは一切なかったが、ここで予選A問題の教訓(そんなんでいいの?という単純な方針でも割と点数取れることがある)を思い出し、めちゃくちゃ単純なやり方が何かないか考え始める。そこで「自分が持ってるどれかの容器1個とまったく同じ容量の注文を出してきた客には売る、そうでなければパス」というやり方で出してみたところ、とりあえず正の点数を得ることができた(154272点)。上位陣は700万とかで争っているので順位的にはアレだけどこれでだいぶ落ち着いた。ちょっとB問題で試したいことが浮かんでもう一回戻る。

B問題ふたたび

これまでの解答だと各ターンで車の移動を考えるとき与えられたインデックス順に動かしていたのをランダムな順番にするよう変更したらスコアが4倍くらいになった(52297点)。同じ順番で動かしているとデッドロックがとれづらいとかそういう理由だろうか?ともかく今度こそA問題にちゃんと向き合うことにする。

A問題みたび

さっきの超単純貪欲からもう一歩進んで、「自分の持ってる容器を足して作れる数字の注文が来たときは売る、そうでなれけばパス」という方針にすることを考えてみる。手持ちの数列から作れる和を求めるのはDPでよくあるやつだからこれならできる!と思い実装を始める。バグを仕込みまくって泣きそうになりながら3, 40分くらいかけてやっと書き上げて提出(5576164点)。これでA問題もオーダー的にはまともなスコアが出たので、あとはここからの改善だけを考えることにした。で思ったのが同じ和に対して組み合わせが複数通りあるときどの容器を売っぱらうかは大事だなということで、dpつくるとき保存しておく組み合わせの条件をいじったりしてたら結構よかった。いろいろあって最終的には100万点底上げできた(6657203点)

結果

A問題が11位、B問題が7位の合計18で全体6位(提出者48名)でした。まさかこんな順位を取れると思ってなかったのでマジか〜〜〜ウレシ〜〜〜〜〜と思いました。いい大人だったのでお金はもらえませんでした。(事前に学生以外賞金出ませんという連絡があってそのときは自分には関係のないことだと思って気にも留めていなかったということを思い起こすと、それが関係ある順位に入れたということでむしろもらえないことが嬉しくもあった(複雑な心の動き))

まとめ

正直今後オンサイトに出れる機会があるかと考えると自分の実力だとなかなか難しいところがあると思うので、今回は本当に良い経験になりました。このような機会を与えてくださったみなさまに感謝します。あといまぜんぜんプログラミングとか関係ない仕事してるので転職してコード書く人になりたいです。PythonC++D言語をよく書いています。何とは言いませんがよろしくお願いします。

競プロ始めて半年経った

いわゆる競技プログラミングというものに手を出し始めて半年ほど経ったので、マイルストーン的な意味合いで文章を残しておきます。

お前は誰だ

プログラミングとは無関係の事務職についてる新卒一年目です。ただ学生時代は半分情報系のような研究室にいて授業とか研究でコードは書いてました。

コンテスト

AtCoder, yukicoder, Codeforcesのコンテストには時間が合うならできるだけ参加するようにしています。競プロの代名詞的存在っぽいところのTopcoderもやりたいんですが開催頻度と時間帯の問題でまだ一回も参加できてません。レートは11/23現在でそれぞれ以下のような状況です。

AtCoder f:id:fluffyowl:20161123152408p:plain

Codeforces f:id:fluffyowl:20161123152525p:plain

過去問を解くこと

今はコンテストよりもむしろ過去問解くのがメインのような状況で、AtCoder, yukicoderを中心に解けそうなものから手を付けていっています。過去問埋めは時間にも拘束されないし基本的に積み上げていくだけでマイナスがないのでモチベーションが保ちやすく、RPGの素材集めみたいなのが好きな人にはおすすめです。取り組み方として、最初のうちはなるべく解説を見ないでがんばる、わからなかったら撤退して別の問題に当たる、という方針でやってましたが、最近は割とさっさと解説見てしまうことが多いです。ただしわからん問題は解説読んでもわからんことが多く、そういう場合は周辺知識を調べたり他の解説がないか探したり解説を踏まえて考え直したりして出来る限り納得してから実装に取り掛かるようにはしています。

過去問埋めはAtCoderに関しては AtCoder Problemsをとても便利に使わせてもらっています。yukicoderはそもそもサイトの仕組みとして問題一覧のソート、絞り込み機能が充実していて、最高です。

Atcoderの埋め状況 f:id:fluffyowl:20161123155255p:plain

yukicoderの埋め状況
★1: 103/103
★2: 122/122
★3: 82/134
★4: 6/70
★5: 0/18
★6: 0/2

感想

別に競プロに限らずなんでもそうだろと言われてしまえばそれまでなんですが、新しいことを知れる、それによって今までできなかったことができるようになったという実感を得られるのが自分にとって競プロのいちばん楽しいところです。

たとえば自分はPythonが好きで競プロでもPythonばっかり使ってたんですが、最近はD言語を勉強し始めて本番の軽そうな問題以外はD言語で書くようにしています。昔は新しい言語を覚えようとして少しかじってすぐやめる、みたいなことが多かったんですが、明確なタスクがあると書かざるを得ないんで競プロの範囲ではだいぶ違和感なく書けるようになってきました。こういう新しいことの積み重ねが楽しさに繋がっています。(ちなみにTopcoderではD言語は使えないらしい、死)

で、初めのうちは暇つぶしで気ままにやってるだけでこういう進捗が適度に得られて十分楽しかったんですが、さすがに半年も経つと頭打ち感がでてきてしまいまして、これ以上目に見える進歩を得たいならそのための取り組みを意識的にやってく必要があるな〜と感じてます。がんばるぞい。

今後の目標

レーティングに関して、AtCoderでは黄色になること、CodeforcesではDiv1に参加できるようになること、Topcoderは参加すること。あとは蟻本を一度ちゃんと読むこと、時間に余裕があれば作問側の考え方を学ぶこと。あと転職してえ