ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AtCoderで黄色になりました

青になってから半年と少しがたち、ようやく黄色になることができました。
振り返りをします。自分が書きたいことを書いているので、黄色になるための秘訣!みたいな記事ではないです。ご了承ください。

やったこと、おこったこと

コンテストで0完を経験した

GCJの3回ある予選のうち1回目と、Tenka1 Programmer Contest 2019、そしてAGC035で0完を経験しました。
特に、後半の2つに関しては、100~300点あたりをそこそこのスピードで解くのが得意だと思っていた自分にとってはショックでした。

令和ABCが始まった

当時青だった自分にとっては、ゆるふわで参加していたABCが再びratedになるのではじめはあまり好きではありませんでした。
結果的には、回によって大当たりから大外れまで様々でした。ですが、ratedコンテストの頻度が格段に高くなったので、その分レートがはやく伸びたと思います。
f:id:emtubasa:20191205215447p:plain
個人的には、E問題が自分にとって得意(もしくは、似たような問題を経験したことがある)かつ、F問題がかなり難しい回だと大当たりを引く、といった感じでした。

このおかげもあり、7月あたりから、はやくも黄色になれる可能性が出始めていました。

ICPC国内予選を突破

チームメンバーのおかげで、国内予選を突破することができました。お世辞にも自分が貢献したとは言いづらく、アジア予選でその借りを返そうと決意しました。

emtubasa.hateblo.jp

生コンの予選に落ちる

実力相応の力を出せば通ると思っていた予選に落ちました。
この時、かなり悔しくて、仲のいい友人に励ましてもらいました(それだけ本気になれていて羨ましいと言われました)。
泣きすぎて夜はあまり眠れませんでしたし、翌日に行われた、大学の練習会も欠席するほど落ち込んでいたのを覚えています。

JAG夏合宿、会津合宿に参加

JAG合宿には初めて、会津合宿には2回目の参加でした。
JAG合宿の問題は難易度が高く、かなり苦戦しましたが、会津合宿の方は、成長を実感することができました。

JAG夏合宿2019参加記 - ツバサの備忘録

会津大学競技プログラミング合宿2019参加記 - ツバサの備忘録

ICPCアジア予選に出場する

言い訳のできないほどの大失敗をしました。

ICPC 2019 Asia Yokohama Regional参加記 - ツバサの備忘録

EDPCを埋める

長らく放置していた後ろの5問を解き、完走しました。解けるときはそこそこ難易度の高いものでも解けるのですが、解けないときは全く解けないので、まだまだ訓練が必要だと感じています。

黄色になる

結局、なんとなくの精進を続け、時間が解決してくれました。
きちんと黄色になったというよりかは、ずるずると引き摺られた感覚です。

新しく学んだこと

会津やJAG合宿等で新しく学んだものや、長らく放置していたもの、令和ABCのF問題で登場した知識がメインでした。記憶が正しければ、
中国剰余定理、掃き出し法、凸包(および複素平面上での幾何の扱い)、ラグランジュ補間、Li Chao Tree、最小費用流、遅延セグ木、強連結成分分解、Suffix Array
といった感じです。このなかで、ratedコンテスト中に実際に使用したのは、遅延セグ木、凸包ぐらいでしょうか…
また、ModIntや行列、抽象化したセグ木を写経他の方のコードを参考にして整備したりもしました。
ライブラリの実装に関しては、これとかこれをよく参考にさせていただいてます。

コンテスト中の戦略やメンタル面について

自分は、毎回のコンテストで常に上振れを引こうと狙うタイプです。特に、一定のパフォーマンス以上で黄色になれる、というコンテストでは、今解いている問題を解いてもパフォーマンスが上がらず黄色になれない、と分かった時点で次の問題を解こうとしてしまいます。
加えて、前半の、自分なら時間をかけずに解けると思い込んでいる問題でミスをしたり詰まった際、急に焦り始めることが多いです。このメンタルの中で問題を解いている際は、かなりバグをうんでしまったり、誤読、嘘解法の提出をします。
結果、普段の実力を出し切れずにレートを溶かしてしまうことが多いです。
自分が橙を目指すには、大爆死をしないための守りの戦術や、焦りすぎない、メンタル面の強化も必要になってくる気がしています。

学内の競プロerについて

先輩方

自分が競プロを始めてもうすぐ2年になりますが、ずっとお世話になっています。自分が始めたとき、黄色の先輩方が雲の上のにいるような存在で、何年かかっても追いつけるような気がしませんでした。が、なんとか自分もそのとき憧れていた色になることができました。
安定性や、上振れを引いたときのパフォーマンス等ではまだまだかなわないので、引き続き目指していきたいと思っています。
あと、やっぱりICPCのWFに出場した先輩がいる、というのはとても誇りです。このような環境はなかなかなく、かなりの強みだと思っています。

後輩

いくつかの記事で言及していますが、後輩たちの精進量が半端なく、あっという間に追いつかれそうになっています。その熱意がすごく、刺激になるので、自分がなんとか精進を続けていられる理由の一つだと思っています。先輩後輩というよりかは、一ライバルとして見ている方が近いのですが、それでもやっぱり先輩として負けられないとも思っています。来年のICPCも予選を勝ち取るのは僕です。

同学年

正直な所、自分の学年はあまり競プロが盛んではありません。これは自分にも原因があり、そこまでめりこんでいない人に精進を強要してしまったような節があったと思っています。ですが、何人かは競プロにハマっている人もおり、質問を受けたり、一緒に競プロの話をするのは楽しいです。
来年ICPCに出ると宣言しているチームもあったりするので、対決するのが楽しみです。

最後に

色変をするたびに、自分はまだその実力がない、と言っているような気がします。AtCoderの橙は、この記事を書いている段階では自分の大学にいません。それだけレベルが高く難しい位置だと思っています。が、橙の方々の精進量をみると、やっぱり明らかに差がついているため、できないと言って諦めるのは違うと思っています。
加えて、最近自分は時間がないと言い訳をしがちです。本当にやりたいと思っているのなら無理やりにでも見つけていると思います。まだ大学3年生なので、時間は十分あると思っています。楽しむことを忘れずに、引き続き精進を続けていこうと思います。

ABC033 D - 三角形の分類

問題
提出コード

解法

直角三角形と鈍角三角形について、それぞれ直角、鈍角な角は1つの三角形につき1つです。それ以外は全て鋭角となるので、

  • 直角三角形→直角の個数

  • 鈍角三角形→鈍角の個数

  • 鋭角三角形→N(N-1)(N-2)/6から上2つの個数を引いたもの

が答えになります。
ある一点iに注目します。その点と他の点をそれぞれ結ぶと、N-1本の辺ができます。
その中のある一本の辺を選んだ際、残りのN-2本の辺の中から選んで直角(もしくは鈍角)ができるかどうかは、その2辺のなす角が90度であるかどうか(90度以上であるかどうか)を調べればよいです。
ここで、そのなす角は、
|(注目している一本の辺と、x軸のなす角)-(新たに選んだ一本の辺と、x軸のなす角)|
となっています。この、x軸とのなす角について注目すると、この値で辺を昇順でソートしておけば、二分探索により、90度(90度以上)の角の個数をO(logN)で調べることができます。
あとは、点iについて全探索をし、全ての点について同じ方法で個数を調べると、全体でO(N^{2}logN)で解けます。

感想

この問題の想定解がなるほど~と思った記憶があったので無事解けました。

Educational DP Contest / DP まとめコンテスト Z - Frog 3

問題
提出コード

解法

dp[i] = i番目の足場へ行く最小コスト
とします。すると、
dp[i] = min(dp[j] + (h_{i} - h_{j})^{2} + C) (j \lt i)
となります。
これを式変形すると、
dp[i] = min(dp[j] + h_{j}^{2} - 2h_{i}h_{j}) + h_{j}^{2} + C
となります。h_{j}^{2} + Cは最後に足して問題ないことがわかります。
a_{j} = -2h_{j}, b_{j} =dp[j] + h_{j}^{2} とすると、
dp[i] = min(a_{j}h_{i} + b_{j}) + h_{j}^{2} + C
という式になり、調べたいのは、
a_{j}x + b_{j}x = h_{i}の際の最小値
となります。
これは直線の式になっているので、
たとえばCHT アルゴリズムで検索をすると下のような記事が、

http://satanic0258.hatenablog.com/entry/2016/08/16/181331

また、Li Chao Treeで検索をすると下のような記事が出てきます。

https://smijake3.hatenablog.com/entry/2018/06/16/144548

あとは、これらのアルゴリズムを用いて、

  • h_{i}でクエリを投げる(得られた最小値をxとします)

  • a_{i} = -2h_{i},b_{i} = x + 2h_{i}^{2} + Cの直線を追加する

という操作を繰り返すと、h_{N}のクエリの答えxに、h^{2} + Cを加えたものが答えになります。
h_{1}のみ、クエリを投げずにa_{1} = -2h_{1},b_{1} = h_{1}^{2}の直線を追加します。

感想

上記のアルゴリズム達は、直線を管理するアルゴリズム、ということだけ知っていたので、もしかしてこれかな?と思い検索をかけるとぴったりハマったので嬉しかったです。

Educational DP Contest / DP まとめコンテスト Y - Grid 2

問題
提出コード

解法

包除原理を用いて解きます。
dp[i][j] = j個以上の壁を通り、i番目の壁に到達するような通り方の場合の数
とします。ここで、壁について、行、列の順で昇順ソートしておくと、i番目の壁を通る際に、i+1番目以降の壁を先に通ることはありえなくなるので、うまく計算することができます。
また、スタート地点を0番目の壁、ゴール地点をN+1番目の壁、とすることで、初期化はdp[0][0] = 1とすることができます。
dp[i][j] = \sum dp[k][j-1] \times _{r_{i} + c_{i} - r_{k} - c_{k}} C _{r_{i}-r_{k}} ( ただし、i \gt k, c_{i} \gt c_{k})
r_{i} \gt r_{k}は、初めにソートしたときに満たすようになっています。
右側のコンビネーションの項は、k番目の壁からi番目の壁に行く行き方です。
これを計算すると、答えが(偶数個の壁を通り(H,W)へ行く行き方)-(奇数個の壁を通り(H,W)へ行く行き方)
となるので、dp[i][j]jの部分を、0,1の2通りに集約することができます。こうすることで、計算量がO(N^{2})におさまり、
dp[N+1][0] - dp[N+1][1]
になります。

感想

包除原理は普段解けないことが多いのですが、割とスッキリ解けたのでよかったです。

Educational DP Contest / DP まとめコンテスト X - Tower

問題
提出コード

解法

現在、積まれているブロックの重さの総和をGとします。
ここに、2種類のブロックi,jを、どちらの順番で新しくに置くかを考えます。

  • iの方がjより上にくる場合
    G \leqq s_{i} \cap G + w_{i} \leqq s_{j}

  • jの方がiより上にくる場合
    G \leqq s_{j} \cap G + w_{j} \leqq s_{i}

1つめの条件は、結局2つのブロックを乗せることにした時点で満たしていなければならないので、無視します。
ということで、それぞれの条件の2つ目を比較すると、
G \leqq s_{j} - w_{i},G \leqq s_{i} - w_{j}
となり、s_{j} - w_{i}s_{i} - w_{j}のうち大きい順番の方が、Gの許容範囲が大きくなります。
s_{j} - w_{i} \leqq s_{i} - w_{j}の場合、jiの上に乗せたほうがよいです。
この条件を式変形すると、s_{j} + w_{j} \leqq s_{i} + w_{i}となるので、
結局はs_{i} + w_{i}の昇順でブロックを並べると、その順番で上から積んでいくのが最善になります。
あとは、基本的にナップサックと同じで、
dp[i][j] = i番目のブロックまで見て、重さの総和がjになるようなブロックの選び方をしたときの、価値の総和の最大値
として、
dp[i + 1][j] = max(dp[i][j], dp[i][j - w_{i}] + v_{i})
(ただし、j \lt w_{i} もしくはj - w_{i} \gt s_{i}の際はdp[i][j])

を計算すればよいです。
答えは、dp[n][j]の最大値、初期化は全て0です。

感想

この問題で似たような考え方をしたので、あっさりと解くことができました。
が、証明は難しいです…(後付けで考えました)

Educational DP Contest / DP まとめコンテスト W - Intervals

問題
提出コード

解法

dp[i] = i文字目を"1"にした場合に、[1,i]で得られる得点の最大値
を考えます。
すると、
iが間に含まれているものを除いた区間達について計算した場合の、[1,i-1]で得られる得点の最大値に、iが間に含まれている区間の得点の総和が、dp[i]の値になります。
これを上手く計算するには、

  • dp[x] = max(dp[y]) (y \lt x)を計算する

  • x = r_{i}を満たす全てのl_{i},r_{i},a_{i}について、dp[z] (l_{i} \leqq z \leqq r_{i})a_{i}を加算する

という操作を、xが小さい方から順番に繰り返していけば良いです。
このようにすることで、それぞれの区間が重複して加算されるのを防ぐことができます。
答えは、dp[i]の中で最大のものを計算すればよいです。

感想

区間の重複加算を防ぐ方法を思いつくのに時間がかかりました…セグ木は便利ですね!

ICPC 2019 Asia Yokohama Regional参加記

ということで、チーム CoprimEとして、ICPCのアジア予選に参加してきました。
チームメイトはTsuzu君、mi君です。

1日目

~リハーサル前

コーチのご厚意で一部奢っていただきました。


リハーサル

Tsuzu君が環境構築、僕がA、mi君がBを読みました。
Aはやるだけなので僕がそのまま通しました。
Bはほぼ同じ問題を僕が解いたことがあったのですが、とりあえず2人も実装してみようということで実装しました。が、二人とも実装が詰まったので自分がバトンタッチして通しました。
Cは非想定らしい、解法っぽいものを残り5分ぐらいで思い浮かんだのですが間に合わず終了しました。


リハーサル後

観光をしました。

ABCにも出ましたが、Fが解けず黄色前半パフォだったため、黄色には届きませんでした。


2日目

本番

コンテスト開始直前になって、急に開始時間が5分はやまりました。まわりを眺めると、okimotiチームのrisujirohさん(だったはず)がトイレにまだ行っていたようで、大変そう…と思いながら問題を解き始めました。

コンテスト開始後は、リハーサル同様Tsuzu君が環境構築、僕がA、mi君がBを読みました。
Aは自分がそのまま実装、BはTsuzu君が実装してACしました。
その後、まわりを眺めつつ、問題をE,G,Hに絞り進めていましたが、Hの実装をまわりのチームがACし始めた直後ぐらいに始めたにも関わらず、最後までバグを取り切ることができませんでした。
自分はコードを2回、1から書き、Tsuzu君も1回1から書き直していました…
結局、コンテスト後に試したところ、自分は1行を変えただけで通りました。
同時に進めていたGもバグを取り切れず、結局2完52位で終了しました。

コンテスト後

Googleブースにあった、入力例のサンプルのみが与えられてそこから問題をエスパーする、というものを最後までやっていました。最後まで解けなかった上答えが答えだったのでかなり悔しかったです…チームメンバーはいろいろなブースをまわって楽しんでいたようです、賢い。

3日目

オフィスツアーです。疲労もあり結構疲れていました…

(最後はMicrosoftさんを見に行ったわけではないです)

感想

強豪チームがバンバン問題を解いていく様子を生で見ることができたり、普段は行けないような場所に行けたりしたので楽しかったです。

コンテスト前に、普段競プロをあまりやっていない同学年の友達に声をかけてもらったり、コンテスト中に反応をしていてくれたみたいで嬉しかったです。が、きちんと練習をしていればもっと上を目指せるチームだったはずなので、応援してくれた方々や、国内予選を戦った他の早稲田のチームには申し訳ない気持ちでいっぱいです。
来年はチームがどうなるかまだまだわかりませんが、チャンスがあればまたアジア予選に出場し、今度こそ納得のいく成績を取れるようにしたいです…
今、自分の大学の1年生や2年生で競プロ活動が活発になっていて、精進量がずば抜けている人もちらほら見かけます。自分が現状全く精進をしていないのもあり、このままだと抜かされる(もう負け始めている?)気がしているのですが、だからといって後輩たちに枠を譲るつもりは全くないので、また1から頑張ろうと思います。


負けません。


最後に、ICPCの運営をしてくださった方々、誘った際に快く承諾してくださったTsuzu君とmi君、そしてコーチを引き受けてくださったryoissyさん、ありがとうございました。