AOJ 2608 - Minus One
解法
、
それぞれを始点とする任意の頂点への最短距離をあらかじめ求めておきます。
から頂点
への最短距離を
,
から頂点
の最短距離を
とします。また、
と
の距離を
とします。
頂点に辺を張った際、仮に
の順に頂点を通り、問題の条件を満たすとすると、
となるはずです。
ということで、となる
の個数を
ごとに、同様に
となる
の個数を
ごとにあらかじめまとめておき、
となるような
のペアについて、それぞれの個数の積を計算し、その総和を求めれば答えとなります。
また、このとき、が同じ頂点になることはありません(その際、
となり、これは
から
の最短距離が
となってしまい、
が最短距離であることに矛盾します)。同様に、
が重複して数えられることも似たような考えからありえません。
AOJ 2003 - Railroad Conflict
解法
経路は線分で、入力が与えられた時点で全て決まっているため、選ぶことができるのはどの箇所を地上に、どの箇所を地下にするか、です。
新しくつくる路線が既存の路線と交差する地点もはじめから決まっているので、それらはあらかじめ計算することで求めることができます。
すると、その交差する地点それぞれでは、地上にするべきか地下にするべきかがわかります。
新しく作成する路線の線分上にその交点を並べたとき、ある点とその隣の点で地上にあるべきか地下にあるべきか、が異なる箇所がありますが、その部分では出入口を作らなければなりません。逆に、そのほかの箇所で出入口をつくる必要はありません。
よって、新しくつくる路線と既存の路線の交点を調べ、それを並べて端から見ていき、地上と地下が入れ替わる箇所の個数が答えになります。
AtCoderで黄色になりました
青になってから半年と少しがたち、ようやく黄色になることができました。
振り返りをします。自分が書きたいことを書いているので、黄色になるための秘訣！みたいな記事ではないです。ご了承ください。
黄色になりましたーー！！！ pic.twitter.com/XTVUlTpEVF
— ツバサ (@emtsu_ba) 2019年12月1日
やったこと、おこったこと
コンテストで0完を経験した
GCJの3回ある予選のうち1回目と、Tenka1 Programmer Contest 2019、そしてAGC035で0完を経験しました。
特に、後半の2つに関しては、100~300点あたりをそこそこのスピードで解くのが得意だと思っていた自分にとってはショックでした。
令和ABCが始まった
当時青だった自分にとっては、ゆるふわで参加していたABCが再びratedになるのではじめはあまり好きではありませんでした。
結果的には、回によって大当たりから大外れまで様々でした。ですが、ratedコンテストの頻度が格段に高くなったので、その分レートがはやく伸びたと思います。
個人的には、E問題が自分にとって得意(もしくは、似たような問題を経験したことがある)かつ、F問題がかなり難しい回だと大当たりを引く、といった感じでした。
このおかげもあり、7月あたりから、はやくも黄色になれる可能性が出始めていました。
ICPC国内予選を突破
チームメンバーのおかげで、国内予選を突破することができました。お世辞にも自分が貢献したとは言いづらく、アジア予選でその借りを返そうと決意しました。
学生コンの予選に落ちる
実力相応の力を出せば通ると思っていた予選に落ちました。
この時、かなり悔しくて、仲のいい友人に励ましてもらいました(それだけ本気になれていて羨ましいと言われました)。
泣きすぎて夜はあまり眠れませんでしたし、翌日に行われた、大学の練習会も欠席するほど落ち込んでいたのを覚えています。
JAG夏合宿、会津合宿に参加
JAG合宿には初めて、会津合宿には2回目の参加でした。
JAG合宿の問題は難易度が高く、かなり苦戦しましたが、会津合宿の方は、成長を実感することができました。
会津大学競技プログラミング合宿2019参加記 - ツバサの備忘録
ICPCアジア予選に出場する
言い訳のできないほどの大失敗をしました。
ICPC 2019 Asia Yokohama Regional参加記 - ツバサの備忘録
EDPCを埋める
長らく放置していた後ろの5問を解き、完走しました。解けるときはそこそこ難易度の高いものでも解けるのですが、解けないときは全く解けないので、まだまだ訓練が必要だと感じています。
ということでEDPC完走しましたー！！
— ツバサ (@emtsu_ba) 2019年11月21日
長かった… pic.twitter.com/AQnCM4REaB
黄色になる
結局、なんとなくの精進を続け、時間が解決してくれました。
きちんと黄色になったというよりかは、ずるずると引き摺られた感覚です。
新しく学んだこと
会津やJAG合宿等で新しく学んだものや、長らく放置していたもの、令和ABCのF問題で登場した知識がメインでした。記憶が正しければ、
中国剰余定理、掃き出し法、凸包(および複素平面上での幾何の扱い)、ラグランジュ補間、Li Chao Tree、最小費用流、遅延セグ木、強連結成分分解、Suffix Array
といった感じです。このなかで、ratedコンテスト中に実際に使用したのは、遅延セグ木、凸包ぐらいでしょうか…
また、ModIntや行列、抽象化したセグ木を写経他の方のコードを参考にして整備したりもしました。
ライブラリの実装に関しては、これとかこれをよく参考にさせていただいてます。
コンテスト中の戦略やメンタル面について
自分は、毎回のコンテストで常に上振れを引こうと狙うタイプです。特に、一定のパフォーマンス以上で黄色になれる、というコンテストでは、今解いている問題を解いてもパフォーマンスが上がらず黄色になれない、と分かった時点で次の問題を解こうとしてしまいます。
加えて、前半の、自分なら時間をかけずに解けると思い込んでいる問題でミスをしたり詰まった際、急に焦り始めることが多いです。このメンタルの中で問題を解いている際は、かなりバグをうんでしまったり、誤読、嘘解法の提出をします。
結果、普段の実力を出し切れずにレートを溶かしてしまうことが多いです。
自分が橙を目指すには、大爆死をしないための守りの戦術や、焦りすぎない、メンタル面の強化も必要になってくる気がしています。
学内の競プロerについて
先輩方
自分が競プロを始めてもうすぐ2年になりますが、ずっとお世話になっています。自分が始めたとき、黄色の先輩方が雲の上のにいるような存在で、何年かかっても追いつけるような気がしませんでした。が、なんとか自分もそのとき憧れていた色になることができました。
安定性や、上振れを引いたときのパフォーマンス等ではまだまだかなわないので、引き続き目指していきたいと思っています。
あと、やっぱりICPCのWFに出場した先輩がいる、というのはとても誇りです。このような環境はなかなかなく、かなりの強みだと思っています。
後輩
いくつかの記事で言及していますが、後輩たちの精進量が半端なく、あっという間に追いつかれそうになっています。その熱意がすごく、刺激になるので、自分がなんとか精進を続けていられる理由の一つだと思っています。先輩後輩というよりかは、一ライバルとして見ている方が近いのですが、それでもやっぱり先輩として負けられないとも思っています。来年のICPCも予選を勝ち取るのは僕です。
同学年
正直な所、自分の学年はあまり競プロが盛んではありません。これは自分にも原因があり、そこまでめりこんでいない人に精進を強要してしまったような節があったと思っています。ですが、何人かは競プロにハマっている人もおり、質問を受けたり、一緒に競プロの話をするのは楽しいです。
来年ICPCに出ると宣言しているチームもあったりするので、対決するのが楽しみです。
最後に
色変をするたびに、自分はまだその実力がない、と言っているような気がします。AtCoderの橙は、この記事を書いている段階では自分の大学にいません。それだけレベルが高く難しい位置だと思っています。が、橙の方々の精進量をみると、やっぱり明らかに差がついているため、できないと言って諦めるのは違うと思っています。
加えて、最近自分は時間がないと言い訳をしがちです。本当にやりたいと思っているのなら無理やりにでも見つけていると思います。まだ大学3年生なので、時間は十分あると思っています。楽しむことを忘れずに、引き続き精進を続けていこうと思います。
ABC033 D - 三角形の分類
解法
直角三角形と鈍角三角形について、それぞれ直角、鈍角な角は1つの三角形につき1つです。それ以外は全て鋭角となるので、
直角三角形→直角の個数
鈍角三角形→鈍角の個数
鋭角三角形→
から上2つの個数を引いたもの
が答えになります。
ある一点に注目します。その点と他の点をそれぞれ結ぶと、
本の辺ができます。
その中のある一本の辺を選んだ際、残りの本の辺の中から選んで直角(もしくは鈍角)ができるかどうかは、その2辺のなす角が90度であるかどうか(90度以上であるかどうか)を調べればよいです。
ここで、そのなす角は、
となっています。この、x軸とのなす角について注目すると、この値で辺を昇順でソートしておけば、二分探索により、90度(90度以上)の角の個数をで調べることができます。
あとは、点について全探索をし、全ての点について同じ方法で個数を調べると、全体で
で解けます。
感想
この問題の想定解がなるほど～と思った記憶があったので無事解けました。
