PCK予選

3回目のPCK予選に出ました。高3なのでこれが高校生として出る大会では最後かな？

ちなみに相方も3年間同じです。高1のときは競プロほとんどできずただ座って相方の解くのを見ていた感じでしたが、今は肩を並べて戦えるようになったのかな。

・予選前

　夏休みも終わる頃。2週間後にPCKが迫っていたんですが、夏休みの間競プロから離れていた結果、ほんとに夏の間何もしていないことに気づきかなり焦りました。

　とりあえず1週間前まではやや難易度の高めの問題を埋め、そこからは時間を気にしながら解く練習をしました。

　またチームプレイのため、互いの動きを事前にある程度決めておきました。PCが2人で1台しか使えないので、どのタイミングで実装を交代するか、などを考えておきました。

・予選

　相方が前半を担当してくれるみたいなので僕は8番から解きました。なんやかんや20分位で解法が浮かびました。

　9番を見ましたが、その後10番を少し見てみると10番のほうが得意そうな問題だったので10番の考察を始めました。

　相方が5までの解答を作ってくれたようですが、6が苦手なタイプだと言っていたので6の考察に移りました。相方はその間7を実装してくれたみたいです。

　6の考察が一通り終了し、とりあえず8と6を実装します。その間相方が7のコードが正しいか、自力でテストケースを作ってくれました。

　実装後、相方と基本方針を問題ごとに確認。7が怖いと相方が言っていたので相方が作ってくれたテストケースの確認をしました。

(実はこのとき、自分は「大丈夫でしょ、出しちゃえば？」という感じだったのですが、相方が「ちょっとまって、1回確認しよう」と言ってました。これがありがたかったですね。)

1〜8が全部確認できたので2時間くらいのタイミングで一気出し。結果は...6番だけWA!(相方ごめんなさい。) 考えられる最大値を入力したときにREが出るようだったのでそこを書き換え、いろいろなケースで入念に確認し、提出。無事ACできました。この時点で6位くらいまで上り詰めることができました。

10番の基本方針がわかったのですが、二項係数の求め方がわからず。(非素数modでの二項係数を出したいんですが、fermatの小定理しか頭になかった。) あまりうまくいかないまま試合終了。凍結前順位で10位でした。

・終了後

　凍結前10位なので行けるだろ、と思いつつも一方で、凍結後の動きが読めずかなり不安になりました。実力枠は落ちたかな...とか言ってた。

　10番の解法がわかった...道を歩いているときに突然ひらめきました。やはり脳の再起動って大事ですね。

・結果発表

　地域枠(東京)で本選に行けることになりました！本選も対戦よろしくお願いします！

　競プロの存在を教えてくれ、一緒に戦ってくれた相方に感謝。今まで僕を応援してくれた人たちにも感謝ですね。本選もがんばります。

AtCoderで青になりました。

2019/6/2のAGC034で青になりました。

嬉しいですね、これからも精進を続けていきたいと思います。

青になるまでにやったことのメモなどを書きます。

・水色まで

→こちらの記事をご覧ください。

https://i7-yoc.hatenablog.com/entry/2019/01/29/000626

・青になるまで

・500-700点をたくさん解きました

→過去問になれるのは重要ですし、パターンも身につきます。

JOIが終わって競プロを1ヶ月ほど中断してしまったのですが、AtCoderの問題を解いて頭を使うのが楽しいということに気づいたので精進をしました。

(AtCoder Scoresより)

ご覧の通り、4月あたりから精進レートが急に傾きを変えていますね、それと並行するようにレートも伸びています。

・「令和ABC」の存在

→2019年5月以降のABCはRating変化対象が〜1199から〜1999に、パフォーマンスの上限も1600から2400に変更されました。Ratedコンテストの回数が増え、かつ自分にあっているセットだったのでこれでいい感じにレートを上げることができました。ちなみに元号の変化と同タイミングでABCの制度が変わったので「令和ABC」と呼ばれることがあるそうです。

・JOIの問題での基礎力

→(水色の記事でも書きましたが)2月のJOI本選に備えて過去問をたくさん解きました。JOIの問題はしっかりとした考察を要する問題が多く、春合宿にはいけなかったもののこの時期に精進をしたことで基礎力がだいぶついたと思います。データ構造にもなれることができました。(難易度9までを少しずつ埋めました。)

・習得したアルゴリズム

→ないようで意外とあるので、メモしておきます。

・DP全般

・二分探索

・priority_queue

・modの逆元、fermatの小定理

・コンビネーション(nCr)のmod(上と内容がかぶっているかも)

・累積和/imos法(例えばGCD(最大公約数)やXORのように、和でなくても累積的に扱えるものがあります。)

・XORの性質(2回に1回はXORが登場しているイメージがあります。

・繰り返し2乗法

・グラフ理論全般(木の直径、トポロジカルソートなど)

・セグメントツリー・BIT(「令和ABC」はセグ木で殴れる問題が出やすい傾向がありそうなので(まだ3回しか開催されていないのでなんとも言えませんが)、セグ木はもっておくとおすすめです。ただしABCの問題はほとんど想定解はセグ木以外なので、決して必須というわけではないです。

・Union-Find(自分はそんなに使いませんが、他の参加者が使っているのはまあまあ見ます)

このあたりは持っていたほうがいいと思います。あとは問題を解いてひたすら着想過程の練習をしましょう。

水色になるまでに200問近く解いたのですが、青になるのにさらに100問ほど解きました。

<自分の問題の解き方>

ここまで散々「問題を解け」と言っていますが、それでは自分がどのような思考過程で問題を解いているか、少し説明したいと思います。

・アルゴリズムを覚えるときは「○○がO(△)できる」くらいの認識でいい。使うときに呼び出す。

・考察用紙にしっかり性質を書き出す。実験をたくさんする。

・構築なら自分でいくつか構築してみる。構築はサンプルケースが当てにならないことが多いので、自分でサンプルケースを生成する。

・(あまり出ないが)インタラクティブなら99.8％位の確率で二分探索をさせようとしているので、どうしたら二分探索できるか考える。

・実装が重くなりそうならもっと軽実装で済む解を考える。

・貪欲でできそうだと思ったらまずはコーナーケースを探す。(あとから値が良くなる場合。)　なさそうなら証明を考えるが、感覚で理解できれば良い。

・行動パターンをまとめる。一見複雑に見える問題でも、実は最適解は2〜3パターンのうちのmax、などといった場合が多い。

…適当すぎますが、思いつく限りだとこんな感じです。

同じ配点でもARCとAGCの問題では難易度が違っていたりして、AGCのほうが体感的には簡単です。

半分半分の割合くらいでAGCとARCを埋めるのをおすすめします。

こんな記事が誰かの役に立つのかわかりませんが、とにかく青になれたのは嬉しいですね。これからも精進を怠らずさらなる高みを目指したいと思います。では。

(記事書いたの2月以来らしいです。。。もっとちゃんとやれ。)

JOI本選

順次更新しておきます。

12:30に学校が終わったので中央線で秋葉原へ

雪予報でしたが降らなかったのでok.

秋葉原でランチパックをたくさん置いている店があってオレンジなんとかのを買うが2/9現在まだ食べていない。

TXが来たので乗る

Twitterで誰か同じ電車の人がいないのか探すが誰もいない

と思っていたらまみめさんがTwitterで声をかけてくれた。つくばについてエンカ。

一緒に会場に向かう。バスがいい感じに来たので乗るをした。

生徒証を見せたら縦と「みんなのデータ構造」をもらえた　嬉しいけど内容がむずそうなので頑張りたい。

座るをしていると某学校の人たちが話しかけてくれた。遠山英二さん、YTAさんと塩化することに成功

Advetisementを書いていたがプラクティスなので切り上げ

プラクティスが始まる　Eclipceにトラブルが起きたらしいがエディタはemacs派なので知らない

ABCを解く

Dをバグらせた　Eはすぐできたのでok

どんなフィードバックが返ってくるか知りたかったので適当にWAや計算量大きくしたプログラムを投げる

その後30分を虚無に過ごす　正確にはマインスイーパーと数独をやってた

講演会が始まる。その前に、となりがふぁぼんさんであることに気づいたので話してみた。

講義も質問の内容が面白かった

飯になる

一言自己紹介みたいなのがあったのでそれらしく済ますがTwitterの垢を言えばよかったと後悔

魚のフライを5個食べた　これ余り過ぎでは？　みんな食べよう。

ここで名刺を10枚弱配ることに成功する

風呂に入る　熱い　でも家ではいつも45°Cのシャワーを浴びてるのである程度は気持ちよかった　風呂でも人々と話したけど誰だかわからなかった。

みんプロがあったが冷えそうな問題だったのでAdvetisementの続きをやることにした

ふつうにACできたので良い

この記事を書いてみる　人々が600や900を普通に通していてやばいなぁと思いながら寝ようとしています　明日の本選もがんばりたい。

------------------------------------------------------------------------------------------------------

ここから2日めのお話。

ちゃんと6時に起きた。朝食AC。独房を整理しバスへ。

荷物置き場につくが、後ろの方だったので席がない、つまりは人権がない。床に荷物をおいてどうにかする。

グミとスニッカーズと筆箱を持って本選会場へ。

本選開始。

1問目を見る。

累積和をすぐにできたのでよかった。

2問目を見る。

去年と問題名がめちゃくちゃ似ている。

個数最大化なので二分探索でできそうだなと思い、考察を終えて実装パートへ。

テストケースは全部合う。

WA。

ここから負けへの3時間が始まったのであった。。。

とりあえず2のWAがわからないので3以降の部分点を見る。

3:「たのしいたのしいたのしい家庭菜園」　たのしい✕1も✕2も解けてない苦手分野。絶望を味わいながら部分点を見るがさっぱり生えない。

4:「コイン集め」　グリッド。実は自分グリッドめちゃくちゃ嫌いです。データ構造が適用しにくいし実装がめんどいのが多いので。

5:「珍しい都市」　生えません。。。。。

諦めて2の部分点をDPで取る。

二分探索を絵を基準にするのではなく額縁を基準にすればいいことに気づく

WA。

もう人生やめたくなって最初から書き直す。

さっきは非再帰で書いたが今度は再帰をさせたらAC。人生やめたい。

ここですでに3時間を消してしまう。

3を見ながらO(N^3)まで行けるなぁ〜と思いながら、RGYの各次元でDPを置くといい感じになりそうだな〜と思う。

考察用紙に「dp[i][j][k][l]=Rをi個、Gをj個、Yをk個選んで、最後にlのとき」と書く。

あとはこれを書けばよかった・・・・・・・・・の、だが・・・

何を血迷ったのか、4の嘘貪欲に謎の自信を持ち始める。

書く。

WA。

諦めてnext_permutationで全列挙したら小課題1でもTLEする。よくよく考えたらそれはそうだった。

その後3に戻ることはなく非本質的な書き換えをしていたら終わってしまった。

飯を食べる。多いと言っている人が結構いたが普通では？？と思う。昼飯全完するくらいなら34のどっちかくらい解け。

解説を聞く。

1:それはそう

2:二分探索しなくても一意に定まっていたことに気づく　まあlogは実質定数なので

3:dpテーブルが出てきた瞬間に自分の愚かさに気づく　難易度的には時間があれば自分でも溶けるやつだったのでものすごく悔しみを感じる　自殺したい

4:解説の人が「これは嘘解法です」と言っていたやつを自分が終わるまで思いっきりやっていたことに気づく　死にたい

5:解説聞いてもわからなかった　まあ小課題2ですら正解者1人なので仕方ないね

帰宅。34をやろうと思っていたが体力が残っていなさそう。実装力のなさは一生の課題かもしれないね。

ABC117参加記

明日提出の物理レポートがあったので遅延参加。

2,3時間くらいかかると思っててABCは出ないつもりでしたが意外と早く片付いた。

(この場合に限っては)嬉しいことに水色なのでレートを気にせず参加できるのでDを見る。

少し考えて桁DPが出てくる。

ソートでO(NlogN)なのでok。

PCが起動しない

22:15頃になってやっと書き始める。

無事テストケース1と2が通る

3がバグる

DPの初期値設定を変えたら直った

コンテストが終わってしまったところでAC

Twitterを見る

嘘解法嘘解法騒がれているので話題のコーナーケースを投げると0を吐く

非本質的な＝のつけ忘れが原因みたいなので安心

どうやら正解法だったっぽい

時間もあるのでC以前を埋める

Cを見る

もう見た(JOIのとある問題で同じようなのを解いた覚えがある)

ソートして長いところを潰していく。

AC。

Bを見る。

またソートじゃん

はい。

Aを見る

Aとはいえ簡単すぎないか(個人の感想)、実質1点じゃんこれと思いながら投げる

当然AC

・感想

桁DPがすぐ思いついてすらすら書けたのは良かったと思います。

ソート多すぎないか？

2/3なので恵方巻き、つまり寿司ですが問題名にsushiがついていなかったですねそういえば。

1時間位で全完　レポートを書きましょう。

AtCoderで水色になっ(てしまっ)た話

1/27のNikkei Programming Contest 2019で水色になりました。

全体的に単調増加なので今後もこれを維持していきたいですね。

水色を目指す人のために経験を書いておきますが、ほぼ役立たないと思って読んでください。自分個人の偏見だけで書いているので。

・茶色まで

これはコンテストに慣れれば行けます。条件分岐・繰り返し・配列・文字列が普通に使えるようになればABCの200までは確実に解けるからです。

僕はここは特につまづかなかったですが、ここで伸び悩んでいる人は100・200点の過去問を埋めてコンテストになれることが大事かなと思います。

・緑まで

緑に早く行きたければ300点問題を解けるようになれれば良いと思います。昔のABCの300点はなかなか難しかったそうですが(埋めてないので知らない)、最近の300は大体計算量に余裕があるので全探索や愚直な実装で埋められる気がします(適当)。

C++使いの人はSTL(標準ライブラリ)の使い方を覚えましょう。queue,priority_queue,vector,mapやsort関数などを知っていると実装が楽になる場合が多いと思います。

・水色まで

緑までのことははっきり言ってそんなに覚えてないのでここからが本題ですね。

300点を早解きするのでも水になれますが、400ができた方が良いと思います。

なんとなく。

やったこととしては、

・蟻本の初級編と中級編を読みました。

・JOI(情報オリンピック)の過去問を埋めました

これくらいですが、特に後者のおかげで圧倒的に実力がついたと思います。

情報オリンピックの問題は割と素直にアルゴリズムが適用できる問題が多いです。難易度6～7を埋めて予選通過しました。このあたりはDP、dijkstra法、累積和(いもす法含む)などのテクニックを使う問題が多いです。

これのおかげで大体の感覚がつかめてきた感じがします(どうやって典型に落とし込むか、例えばソートしてから乗せる、だとかの感覚もここで身についたと思うので)

なので中高生以外の人にもJOI埋めはオススメだと思います。

自分は現在は難易度8～9を埋めています。本選対策として。難しい。

自分が水色になった回もDがトポロジカルソートで、JOI過去問で何回か使っているのですぐに解法の候補として浮かんだので。ちなみにその回のCが苦手なゲーム問題でしたがあることに気づけばやるだけだったので解けました。

ちなみにですが自分はAtCoderの過去問に関して言えばほとんど埋めてません。意欲旺盛で1日3～4ACするような競プロerもよく見かけますが、自分は努力の才能がないのでそんなことはできません、、、

RPSが低いのは一つは単純に精進をしていないからで、もう一つはJOIの問題(これは点数が100点として扱われるはず)を優先的に埋めてるからです。

200ACもしないで水色になって良いのか･･･という感じはありますが、逆に感覚さえつかめれば水色はそこまで難しいものではないと思います。

以上、全く参考にならなかったと思いますが、読んでくれてありがとうございました。

Nikkei Programing Contest 2019 参加記

参加記なので詳しい解法は省略…

コンテスト開始30分前にコンテストの存在に気づきながらお風呂へ

PCを立ち上げたのは10分前。

企業コンは入力フォームが多くて面倒ですがなんとかTLEしませんでした。

Aを見る。

100点なのでまあ当然やるだけ

2分でAC

Bを見る。

200なのでやるだけ。

考察難易度はAより低そう。

開始5分で300点を得る。

まあいつもどおりですね。

Cを見る。

苦手なゲームだったので無言で息を引き取る。

少し考えるが、Dを見ることにする。

Dを見る。

木で喜ぶ。

すぐにトポロジカルソートを思いつく。

トポソしたあとの処理もすぐに生える。

入力例の手計算がWAってたためなんだかんだ30分弱かけて書き上げる。

提出すると1発AC。コンテスト中に通した初の500なので嬉しい。

Cに戻る。

片方がある料理を食べたときにもう一方はその分を損するので結局ある料理を食べたときの利益は2人の和になる。

和でソートするという小学生並みの解法をひらめいて適当に書くがこれが正解らしくAC。ここまでで50分くらい。

EFはまあ無理でした。

たぶん(98％くらいで)水色到達！！！このことはまた今度書こうかなと。

JOI2018 本選2 「美術展」

表題の問題を解きました。

<問題概要>

N(<=500000)個の美術品があり、大きさと価値が定まっている。

そのうちのいくつかを選ぶとき、(価値の和-(大きさの最大値-大きさの最小値))を最大化せよ。

・方針

とりあえず、大きさの順に並べると、ある区間を選んだときに最大と最小が両端にあって良いので大きさでソートする。

価値の合計をS、最大・最小をAmax,Aminとすると求める値はS-(Amax-Amin)と表せる。

これはAmin+S-Amaxと変形できる(これ重要)

すると、ある美術品を最小値に固定したときに、S-Amaxを最大化すればいいことがわかる。(各美術品が最小値となる場合を考えるとO(N)かかる)

最小値を左から見ていくとき、はじめはSを全体の合計とし、だんだん見終わった部分の値を減らしていく(累積和ですね)とよさそう。

文章力がないので図にしてみる。

PC上で図を書くのが面倒だったので手書きで。

答えの大小関係はS-Amaxの大小関係に依存するので、これの最大値が各美術品が最小となる場合について取得できればいい。

また、この場合は美術品①を最小のものとしている。自分より小さいものを選ばないとすると、範囲がだんだん狭まる。

Q:指定された範囲の最大値を高速で求められるデータ構造ってなーんだ

A:SegmentTree

ということでこれをセグ木に載せましょう。これで前計算O(N)、ある美術品を最小としたときに値の算出がO(logN)で行えます。

あとは最小の美術品を変えたときに値がどう変化するかを追えばいいです。

こうなりますよね。でも、すべてのSを減算していると1回の遷移でO(N)かかってしまい、全体ではO(N^2)かかってしまうのでこれではだめです。

Sの値を変えずに答えを出すことができるんですね、これが。

最大値を求めたあとでそれから今までの累積和を引くことでO(1)ですね。

おしまい。手書き多すぎですみませんね。

今気づきましたが逆からやればセグ木いらないかもね。

提出↓

atcoder.jp