Chanyuhのブログ

競プロ、スマブラなど 書きたいと思ったら書きます

WUPC2020 参加記

WUPCに単身で参加しました。本来は記事を書くつもりはなかったのですがあまりにも愚行に走ったので自戒を込めて本番の状況を書きます。

 

開始直前

開催するサイトがAOJであることに気づきAOJにログインしようとしましたが何故か失敗。さらにパスワードを変更しようとしたもののできないという旨のツイートを発見したので渋々別垢を作成しました。今思うとこの時点から不穏でした。

 

0:00~0:05

A問題を通しました。特に語ることもなくAC…と言いたいところですが1回CEしました

f:id:p_Chanyuh:20200912185250p:plain

正直これ誰でもCEするだろ

 

0:05~1:10

地獄の始まりでした。

f:id:p_Chanyuh:20200912185502p:plain

 制約をなんども確認し何度コードを見直しても通らないのでジャッジ無能説を唱えていました(人間の屑)が全人類通しているのでそうではないとなりました。

 その後心が折れてCに行きましたが焦りに焦っていた私はこの時全くわからず、Eに行きました。メビウス関数を振り回せばどうにかなる問題だったので無事ACできました(約数の個数を低く見積もっていて2WA)。

 

1:10~1:55

Bに戻り、この辺りから0/32なのが怪しいことに気づいて出力が合っていない可能性を考えprintfで書き直しましたがダメでした。泣きながら通している人が多そうなC、M、Fを解きました(Eが通せていたのでメンタルはまだ安定していた)。

 

 

1:55~2:30

全ての力を振り絞ってBを通す時間でした。まずpythonで書いてみましたがダメ。その後出力が本当に原因なのかを確かめるため、sample 1の答えを出力するだけのプログラムを提出し1/32を得ました。

f:id:p_Chanyuh:20200912190929p:plain

このコンテストで一番情けない提出

ここで出力が原因であることを確信し、AOJのHello Worldをやったり(焦りすぎてcin >> nを消していなくて1WA)、「AOJ 出力」でググったり、AOJで空白区切りで提出する問題を探そうとしたりしました(何故か全く見つからなかった)。あらゆる手を尽くしてもダメで諦め、twitterを見たところ、

- (AOJ初めての方へ)出力の最後に余分なスペース出力をするとWAになるので気を付けて下さい.

という文を見つけ、急いで書き直して提出しACしました(11WA)。この注意書きはAOJ初めての方だけではなく僕の命も救ったのです。感謝の思い絶えません。

 

2:30~5:00

ここから先は特に面白いイベント等もないので特に印象的だった問題について書きます

G

1回ずつしか使わない場合でDPした後、怪しい貪欲をしてしまった

すぐ個数制限なしナップザックを思いついたのでよかった

J

DAGの到達可能性クエリでググったら論文みたいなのが出てきてそれを読んでた(ばか)。制約見返したら逆辺にすると必ずトポソ前に行く(到達できる点は増えるのみ)ので探索回数が辺の数で抑えられる、特にすき

I

1が1個でもあれば最後1だろ!w→WA

→1が端以外にあれば最後1だろ!w→WA

→1が階段状の領域以外にあれば最後1だろ!w→AC(情けない通し方しかしてないな…)

L

蟻本で見たことあるので実装するだけだった、実装したら残り1分になってしまい、サンプル試さず提出したら奇跡的に通った(うれしい!)

 

結果

10完TIME1780で38位となりました。事故はありましたが、着手した問題は全部解けたので結果としては満足しています。非常に面白い問題ばかりで大変楽しいコンテストでした。主催者の皆さん、ありがとうございました!

 

いいたいこと

AOJは余計なスペースを入れると、WA!

 

 

Atcoder黄色になるまでにしたこと+α

初めまして、Chanyuhと申します。ABC177でありがたいことに黄色になることができましたので、人生初の色変記事を書いていきたいと思います。今までこういった記事を書いたことがない(もっというとまともな記事を書いたことがない)ので、自分語り自分の立場及び競プロ遍歴を振り返りつつやったことについて記載していきます。

 

 


私について


私は東北大学医学部医学科に通う3年生です。私のコンテストグラフを見ると間隔が極端に空いている期間があると思いますが、これは基本的にテスト期間に一致しています。ただし、実際競プロを捨てなければいけないほど忙しかったかというとそうではなく、ある程度ちゃんと試験勉強しつつ競プロのコンテストに出続けることは不可能でないと思います。ただ私は2年まで他にもサークルをやっていた点、賞金が出る試験で友人とノリで最優秀を目指した点(結果は学生代表にはなったもののお金はもらえませんでしたが……)、そして複数のタスクをこなすのが不得手な点などからコンテストに出ないようにしていた期間がありました。総じて私については「時々忙しい期間があるシングルタスクの人」と認識していただければと思います。


以下、私の競プロ遍歴となります。


2018年11月〜2019年2月


ちょうど大きな試験が終わり気分で競プロを始めました(それ以前のプログラミング経験は皆無です)。入学以降数学に飢えていたこともありどハマりし、開始1週間くらいずっと旧ABCのCを埋めていました。当時はpythonを使っており、書き方を学ぶ上でこちらのサイトにお世話になりました(https://www.python-izm.com)。このころはプログラミングなんもわからんの状態だったので、コードテストでスマホコーディングがメインでした(授業中にも隠れてやりやすいし)。
その後慣れてきたあたりからD埋めを始めました。このあたりで必要な知識が足りないことに気づき、記事を参考にUnionFindなどの基礎知識を身につけていきました。またこのころはわからない問題が知識不足によるところが大きかったので割とすぐ解説ACをするようにしていました。個人的に解説ACは適切に使う分には良いと思ってます(時短に有効なので)。
その後コンテストに出始め、運良く6回(約1ヶ月)で水色まで行くことができました。特にABC115ではバイト終わりにコンテストの存在を思い出してスマホから参加し、夕食を食べながらDを通して全完できるなど初心者としては快調な滑り出しではないかと思います。これ以降もあらゆる時間に競プロをしていたので問題がどんどん埋まっていき、1~2月には確か700埋めあたりに手を出していた記憶があります。ただ、問題点としてその段階に来てもなお解説ACの頻度を落としておらず、まるで何も得ないままただ解法を見るだけの作業と化していたのは反省点です。また電車内考察などで解けたと感じた問題を実装せずに放置したことが良くありましたが脳内と実装では当然大きな違いがあるので愚かだったと反省しています。


2019年3月〜7月


競プロの春休み!などと思っていたら用事と競合しないコンテストがほとんどありませんでした(かなしみ)。その後春休みが終わり前述した賞金試験の勉強に傾きつつもある程度コンテストには出ていました。運のいいことにレートが上がり続けて青まで行くことができたのでそこでコンテストを一時中断ししばらく試験勉強に専念しました。
勉強と並行しつつの精進として試験の3日前以外は必ず1問は解くようにしていました。問題は過去に解説ACしたものや実装をサボっていたやつにして、電車内で考察をまとめて家で書くだけという形にすると時間をとらないのでオススメです(たまに沼りますが……)。


2019年8月〜10月


夏休み、このころは新ABCとなっていたのでコンテスト不足もなく競プロ三昧でした。このあたりでpythonからc++に乗り換え、VScodeを使い始めました(理由としては速度もありますが、std::setを使いたくなったという点が一番大きいです)。最初は慣れなかったものの長い目でみると明らかにパフォーマンスが上がったのでこの選択は良かったと思っています。
このあたりのコンテストとして、日本最強プログラマー学生選手権の予選で謎の力を発揮し橙パフォを出したのは今でも覚えています。なお本選では陰キャを拗らせすぎて誰とも会話せず懇親会に出ずに帰宅しました(翌日試験だったのでと言い訳していましたがかなり後悔しています)。その後は可もなく不可もなく、レート1800あたりを維持していました。


2019年11月〜2020年1月


試験とサークルの繁忙期が重なった結果一切コンテストに出ませんでした。正直この期間をもう少し競プロに割いておけば……と思います。この時期はあったコンテストを見て面白そうな問題を休憩がてら解くということをしていましたが、面白そうな問題という主観的な基準で選んでいたばっかりに内容が偏り得意分野と苦手分野の差を広げてしまいました。強くなる練習法して効率的なのは「埋め」だと今になって思います。(このあたりまでは記憶が曖昧なのであまり具体的なことを書けていません、申し訳ありません)


2020年2月〜8月


復帰戦でいきなり過去最低パフォ(初回より低い)を出し悲しみに打ちひしがれていました。敗因も怪しい貪欲に走るという一番やってはいけないものだったので大反省です(この回については後に具体的に書きたいと思います)。その後は春休み+オンライン授業だったので大量に精進できる、はずでしたが「大乱闘スマッシュブラザーズSP」にハマってしまい精進をおろそかにしてしまいました(スマブラerの方がいましたら是非フレコ交換しましょう)。

精進については流石に問題数に限界を感じdiffの高めな問題についてCodeforcesやYukicoderを利用させていただくようになりました。その一方でどちらもコンテストには出たことがなく(なんで?)またバチャなども一切やっていませんでした。私の精進スタイルが「気が向いた時にやる」といった感じだったのですが、実際お風呂でのゆるふわ考察とコンテスト中の緊張感のある考察では全く違いますし解くまでの時間も重要ですのでその点では実戦経験の不足が実力の停滞につながっていたなあと反省しています(こいついつも反省してるな……)。

 

f:id:p_Chanyuh:20200830115403p:plain

(これどうやって全体写すんだ?)
黄色になった時点での精進グラフはこのような形です。基本的に青黄埋めをしてましたが解法を覚えているものは意図的に忘れるまで放置しています。たまに解ける橙や赤があるので余裕があるときはそういったものを探す旅に出ていました。

 

この期間に20回くらいコンテストに出て、ついに昨日のABCで黄色になることができました。ほとんど青パフォばかりだったので上振れを感じますが、結果的に目標としていた位置まで行くことができて非常に嬉しく感じています。

 

 

過去のコンテスト反省会

 

黄になるまでの半年間で反省点が多く今後の精進やコンテスト中の立ち回りに大きく影響を与えた問題を3つ紹介したいと思います。(ネタバレ注意!)

 

ABC153-E Crested Ibis vs Monster

atcoder.jp

先に紹介した大失敗回で、通すのに71分(+1ペナ)かかっています。具体的に何をしていたのかというと、

・制約を見間違えてO(N)で解かないといけないと思っていた

・嘘貪欲に走った

をしていました。1つ目の点についてはまあ、そういうこともあるよね……という感じですが、2つ目については貪欲が嘘だと60分くらい気づかずその解法に固執してしまったという点で愚かだったなと今でも思います。冷静に考えるとこの問題がO(N)で解けるならばナップザック問題もO(N)で解ける、ということにコンテスト後気づきました。この回で学んだことは

・嘘貪欲に走らない(当たり前体操の歌詞にありそう)

見たことある問題パターンと照らし合わせて貪欲で解けていいのか考える

この2点です。特に後者は一般に証明が難しくなりがちな貪欲の正当性をある程度正確に裏付ける、または否定する重要な手段となると感じています。またこの学びを得たことにより、問題を解いたときどのような抽象的な構造が背景にあるかを考えること、多くの問題パターンに触れることの重要性を理解することができました。故に大失敗回ではありましたが得たものの多い問題でした。

 

ABC159-F Knapsack for All Segments

atcoder.jp

この辺りでは対青diffへの勝率が割とよく、「青diffまではいけるっしょ〜」みたいなヘラヘラした気持ちでコンテストに望んでいた結果、この問題で大敗を喫しました。解法ネタバレになりますがこの問題は最初に採用する要素の位置をa,最後に採用する要素の位置をbとすると条件を満たすsubsetに対して(a+1)*(n-b)を足し合わせるだけでOKで、この考察自体はコンテスト中にできていました。しかしこの計算をナップザックDPに適応させる方法がわからず結局解けないままコンテストを終えてしまいました。この問題を通して、ナップザックDP一つとっても自分がいかに浅い理解しかしていないことを実感し、先に述べたABC155-Eと合わせて個々の概念を抽象化して把握し応用範囲を広げるということを意識しつつ精進に臨むようになりました。またこの回で見たmaspyさんのツイートをきっかけに形式的冪級数について学び始め、今では以下の赤diffをコンテスト中ではないものの自力ACできる程に使えるようになりました。ありがとうございます。

atcoder.jp

 

ABC165-F LIS on Tree

atcoder.jp

コンテスト中に解けず、解法を見たとき絶望した問題ランキングNo.1です。根を端点にもつパスしか考えなくて良い、かつLISはセグ木を使えば解ける(pushとpopも容易)であることから思いつくべきだったという反省もありますが、この回での反省点はコンテスト中の立ち回りにあります。

というのも、この問題を少し考えてわからず、一度聞いたことのあるデータ構造(?)であるHL分解を使えば解けるんじゃね!?となりHL分解の記事を追いまくるという愚の骨頂を犯してしまったのです。結果的にHL分解をペタッ!したにも関わらず今回の問題にどのように適応するのかわからず(というか今もわかってないのですが……)、泣きながら(誇張)コンテストを終える運びとなりました。一切の理解がないデータ構造に頼るという愚かさから現代に徒然草があれば仁和寺の法師の隣あたりに載せられていそうですが、これに似た経験をされた競プロerの方は以外といるのではないかと推察しています。これ以降私はコンテスト中に

コンテスト中の問題は自分の知っている知識で全部解けると思いこむ

ことを徹底しています。足りない知識は精進中に補えばいいのであってコンテスト中は自己の知識に完結した方が雑念が少なくて良いのではないかという考えからです。実際、昨日のABC177-Fでは一瞬遅延セグ木(持っているがコンテスト中は使ったことなし)が頭をよぎりましたがこの回を意識してそれを捨てた結果setを使った解法を思いつくことができました。

(見返してみるとABCだからこれで通用してるっていう説はあるかもしれませんが……)

 

最後に

 

黄になるまでに気づいたこと、思ったことであって特に言いたかったことについて書きます。参考になれば幸いです。

 

・忙しくてコンテストに参加できなくても復帰の意志があればたまに問題を解くと良い

 これは単純に復帰戦でパフォを落とすと悲しいので……競プロの良いところとして実装はともかく考察は任意の場所でできるので、移動時間や合間の休憩時間を活用すると忙しくとも精進だけならできます。コンテストに参加できないのは致し方ないことなので罪悪感を抱く必要はないと思います(と僕は自分に言い聞かせていました)。

 

・レートをモチベに繋げるのであれば広い範囲の問題を精進するのが良い

 これも自戒込みなのですが、一時期(形式的冪級数にハマったあたり)から数え上げの問題しか精進しなくなる時期がありました。この期間のおかげで結果的にEverything on it(銅diff)を自力ACできるなど確実に力はつきましたが、それ以外の分野がおろそかになり結果として次のコンテストはレートを落とすこととなりました。一点集中する==他は無精進になるなので、短期的なレートの上がりには繋がりにくくそれでモチベを下げては元も子のないと感じました。したがってある程度幅広い問題に日頃から触れることは重要であると感じました。

 

医学生の方は試験にコスパ重視で挑めば競プロとの両立は(多分)できる

 ピンポイントな話になってしまい申し訳ありません。私は先に申した通り試験期間は競プロと一定の距離を置いていました。これは単純に私が複数を並行できないということもありますが、それなりに試験勉強をガチっていたというのも理由としてあります。低学年のうちは試験の多くは過去問および重要な点をおさえることで合格点まで達することができると感じています(大学ごとに差異があるのであくまで主観ですが)。高得点を狙うとなると極端に深く資料を読み込むなどの時間的拘束を余儀なくされ、その分両立(特にコンテスト出場)が厳しくなります。正直僕はもう少しこの3年間を競プロに振っても良かったと感じています。以上のことから自分の目指す成績や課外活動などと相談し、より良い競プロと医学のバランスの取り方を見つけていっていただければ幸いです。

 

 長くなりましたが以上でこの文章を締めさせていただきたいと思います。最後に黄色になるまでの過程において、わかりやすい解説記事を書いていただいていたけんちょんさん、maspyさんを始めとした皆さんや幾多もの解法、知見ツイートにお世話になりました。この場を借りて感謝申し上げたいと思います。これまで競プロ垢をほとんど稼働していませんでしたがこれを機にツイートを増やしていきたいと思いますので、よろしくお願いします。

 それでは、いつになるかわかりませんが「Atcoder橙になるまでにしたこと」でまたお会いしましょう、それでは!

エイシングプログラミングコンテスト2020 E

atcoder.jp

 

このタイプの貪欲を見出すのが苦手というか安定しないので、書き留めておきます。

この問題を少々読み解くと、次のようになります

 

 N個のものを一列に並べる、i番目のものはx_i番目以降に配置するとスコアa_i(>0)を得られる。この時得られるスコアを最大化せよ

 

この時注目する点は以下の2つです

 

・条件を満たした時+a_i,満たさない時±0である(罰金はない)

→ある位置に入れるものを考えていて条件を満たすものがない場合は、採用しないとして良い

これより、貪欲をするとして満たすものがないときに何を採用するのかということを難儀する必要はないとわかります。

 

・手前から順番に見ていくことにすると、だんだん条件を満たすものが増える(減らない)

→これにより手前から順に見ていけば、ある場所で使えなかったものでも消えることがないので、一番高いものを取るとして損をすることがありません(たぶん)

 

このことから手前から採用することの正当性が直感的にわかります。逆にこういった問題において、上の2点を満たすような見方をすると正当な貪欲になる可能性が高いことが言えます、覚えておくと貪欲で見通しが立ちやすいかもしれません。