DDCC2024 参加記

参加の記念にメモ程度ですが残しておきます

予選

しれっと応募が始まって予選の一週間くらい前には終わっているので忘れないようにしましょう

過去問を見てもらうとわかるんですが、謎の入力形式になっています

終わるまで気づかなかったんですが、そのままソースコードに貼ることを想定していそうです(文字列が""で囲んであったり、vectorなどにしやすそうなものが{}で囲んであったり)

これをいちいちパースしているとそれだけでも時間がかかるので、特に非就活枠の人はあらかじめどう取り組むか決めておいた方がいいと思います

手元実行をするタイプですが入力のサイズがかなり小さいので、AtCoderのコードテストで全然いけます

予選問題(覚えている範囲で)

Q1 なんか愚直でいける簡単な問題でした、覚えてません

Q2 時刻の足し算を要求された気がします、ド典型なんですがめんどくさい

Q3 N(N≦10)個の点が与えられて、巡回セールスマン問題の逆(最大化)みたいなことをやりました、点をまたいではいけないというルールがあったんですが、制約が優しいので順列全探索 + 距離を愚直に判定で通りました

Q4 体感1600diffくらいのナップサックDP亜種、何種類か荷物のカテゴリが分けられているのでそれぞれについてDPで最適解を求めて、それを合体させるみたいなことをすると解けました

パースに時間がかかった + コロナ明けで瞬発力がなかったのもあって90分くらいかかってしまいましたが就活枠なら通過していました

全完すれば就活枠なら通過は確定でそうでなければ早解き勝負ぽかったです

本戦

就活枠+遠方なので、移動費と前日分の宿泊代が支給されました(ありがとうございます)

宿泊はDISCOさんから指定された会場に近いところに泊まりました

ダブルの部屋で広くて楽しかったです

今年の問題も2021,22と傾向は同じで、穴とバーのあるパチンコ台のようなものを操作して球を入れていく装置実装問題でした

1. シミュレーション

そこまで時間がなかったので、とりあえず直線的に射出するプログラムを書きました

最上位が27000点くらいで、自分が18000点くらいでした

-昼食-

お弁当を自由に選んでねと言われたので、牛とろろ弁当みたいなのにしました

賛否両論というところのお弁当だそうで、食材として苦手なものも割と食べられておいしい店ってすごいな～と思いました

nok0さんやmilkcoffeeさんたちと談笑していました

2. 実機確認1

スコア計算もまともに読めていなかったので、スコア計算をもとに改善を考えます

横方向の傾きは考慮すると頭がバグりそうだったので縦方向の傾きとバーの向きで加点できるようにしました

実機確認はシミュレーションのコードを使うのでまあそうだよな～という結果でした

あとあと考えれば、シミュレーションであまり点を取らなくても傾き方だったり反射だったりのデータを得ていた方がよかった気がします

3. 実機確認2

とりあえず簡単な穴には入りそうだったので、そうでない穴に入れる方法を考えて反射を実装してみました

ただ反射の計算が意外と面倒で実装するだけでほとんどまるまる使ってしまいました

多少時間が余ったので軸の向きをギリギリにして点数を上げられるようにしました

確認フェーズは2のコードを使うんですが、バーに当たって入っていないものがあったのでそこを何とかしようと思っていました

-会社説明・見学-

DISCO主催の大会なので会社説明と見学が計1時間弱くらい？ありました

福利厚生というか職場の中にリラックスできそうな空間があるのすごくうらやましいなと思いました

病院にもダーツとプールを置きましょう

4. ファイナル

エンタメ色が強めの大会で演出や実況解説の存在にびっくりしていました

適当にしゃべったインタビューが放映されてそういうことか...となりました

ファイナルの結果はカスで、直前に実装した反射がうまくいかなかったのと軸の角度を攻めすぎて入らなかったのでボロボロでした

実機確認1まででやりたいことの80%くらいは実装しないといけなくてそこから微調整するのがよさそうだったんですが、そもそも時間が足りずやりたいことができませんでした...

そもそも上位陣がほとんど反射を使わず傾きで戦っていたので、単純に戦法をミスっていたんだなと思います(これ知ってるかだけでも情報アドバンテージになりそう)

あとは表彰式をやって終了という感じでした

nok0さんが優勝していてマジですごい

来年機会があればリベンジしたいです

DISCOさん楽しい大会をありがとうございました

医学部CBT 参加記【IRT 750↑】

いつも競プロの記事を書いていますが、せっかくそれなりに頑張ったので残しておこうと思います

守秘義務とかがあってあまり細かいところは述べてはいけないので、勉強ペースとか解き方テクニックとかが主になります

問題の物量で殴って高得点！という感じなので効率はよくないかもしれません

結果

IRT 750+ちょっとでした(おそらく95%くらい？)

やったこと

まず前提としてCBT以前にどの程度勉強しているかが、対策にかかる時間・内容に影響してくると思います

普段の学校の勉強はそこそこやっていて、GPAだと学内3~5位くらいです

使用した教材

・QB CBT (メイン)

・Q Assist

・問トレ

・(病気がみえる) ←たまに確認する辞書的なポジション

スケジュール

完璧に仕上げるまではいかなくても、せっかくやるならそれなりの点数をとって受かろうというくらいの気持ちで準備しました

もっと点数を積むには、もっと時間を割かないとだめだったかなと思います

3年1月 ~ 4年7月：授業が忙しいのでテスト勉強中心、テスト勉強がひととおり終わったらその範囲のQBをとりあえず解く

力試しに解いていた感じで、そのときの得点率は70~80%だったと思います

この段階ではQBの問題をまとめたりはしていません

4年8月~9月：夏休みで時間があるのでQBの基礎を解く + 授業が始まったらゆったり臨床科目(↑で解いている)をもう一回解いてみる + (9月)同じ範囲の問トレをする

このときにやったこと

・基本的にQB + 問トレを解き進める

・Q Assistは得点率が低かったり、自分の中で分かってなさがやばいところを見る

・わからないところはとりあえずまとめノートに雑多に記録する

・授業は半分くらい聞きながらひたすら問トレをしていました(こっちはまとめノートなしで知識の確認)

====この時点でQBの進捗2000問くらい====

4年10月上旬：臨床が解き終わりかけたので、そこから公衆衛生・多選択などを解く

4年10月中旬：1週間弱で4連問をががーっと解く、MEC模試を解く(10/10くらい)

この時点で基礎医学2周 + 臨床2周(てきとうな1回 + ちゃんとやる1回) + 公衆衛生以降1周の状態

4年10月下旬：まとめノートで復習しつつ、QB模試を受ける(10/23)

模試はQBと先輩からもらった2,3年前のMEC模試を解きました

模試の感想

・MEC : 知識問題にたまに難しいのはあるけど基本的には知識で瞬殺できる簡単なのが多い、特に多選択が超簡単であんまり参考にならなかった

・QB : うってかわって知識瞬殺は少なめ、雰囲気で推測できるけど自信ないみたいな問題がかなり多い、自分の結果はかなり2択が上振れてる(が、2択などに絞れてる状況に持ち込めてるのが学習の成果ともとれる)

結果：どちらも94%くらいでした

4年11月：ある程度の知識は身についているのでまとめノートの見直し + 5日くらいで問トレを全部解きなおした

前日は自分が間違えたQBの問題をひととおり解きなおした

11/7が本番です

最終的にやったこと

QB： 基礎 + 臨床3周、公衆衛生以降 2周

Q Assist : 苦手なところだけ見る　循環・産婦人科を主に見ました

問トレ：全体2周

模試：QB + MEC

テクニックなど

勉強のしかたは人それぞれだと思うので、QB, 問トレで演習している中で大事だなと思ったテクニックや雑多なコメントを書いておきます

※あくまで試験で点数をとることを目的としているので、医学的に正しいかは知りません

①臨床問題では年齢がめちゃくちゃ大事です、かなり絞れるので見ないとすごく難しくなります→直感でもいいのでざっくりの好発年齢がわかるとよいです

②体系的な理解が大事なのはそうですが、どうしてもテスト問題にする都合上特徴的なキーワードや病態で決め打てる問題は多いです

代表的な臨床問題だと、だいたいエピソードも共通しているのでそういうところから攻めるのは良いと思います(ex. 何週間か前にこけた→ほぼ慢性硬膜下血腫)

③4連問でしっかり点を取ろうと思うと、1問目の時点で具体的な鑑別診断が挙がることが望ましいです

それができると、症状も具体的に考えることができるので、選択肢を絞りやすくなります

④産婦人科はとりあえずエコーで解決！！(正直迷ったらエコーでいいです)

⑤QB・問トレどっちも一定数かなり難しい or 細かい問題が入っています

個人的にはQBの基礎は難しすぎるのでは？と思っています

難易度判定はなかなか難しいと思いますが、ひたすら問題を解く or 勉強している友達に聞くなどすると、大事な知識か細かい知識か分かる(はず)

→ここができるとできないとで効率はかなり変わると思います

　重要そうな問題はがんばって、そんなーみたいなのは適当でいいです

結構時間かけてるけど点数が微妙だなみたいな友達の話を聞いていると、全部同じ強さで勉強していてパンクしているというのが多い気がします

⑥問トレの必要性ですが、QBのあとに復習するという意味なら使う価値はあると思います

個人的には難易度はQBよりやや簡単と思います(が、そうでないという意見も多い)

変な問題がたまにあるのはそうですが、それはQBもいっしょ

⑦個人的な考えですが、1周目から知らないことを全部メモすると膨大になるので、1回てきとうに解いてなんとなく理解してから、もう1回解くときにまだ覚えていないことをちゃんとメモするのがいいかなと思います

最後に

QBと問トレをぶん回せばなんとかなるという感じでやってきて、まあまあいい感じの点数になりましたが、もっと高得点を取るには病気がみえるとかの網羅性が高い勉強が必要なんじゃないかなと思いました

ある程度の水準に到達するまでは、100%を目指しすぎず知識を少しずつ積み上げていって「なんとなくわかる！」という範囲を広げていくのがいいと思います

それなりに大変な試験ですが、うちの大学ではQB1周が間に合った人はほとんど合格していたのであまり気負わず頑張ってください！

第四回最強プログラマー学生選手権決勝 参加記

参加してきました

コンテスト以外のことも書きます

Day0

たまたま午後の授業がなかった(夏休みは1カ月前に終わっている...)ので、15:00くらいの飛行機で東京へ

編入前の友人と会ってハンバーグを食べて英気を養う

データサイエンティストになりそうと言ってたので、AtCoderをやってほしいな～と思いながら...

前も誘って緑くらいで忙しくてやめちゃってたので復帰してほしいけど、大学院がすごく大変そうだった

その後は友達の家に泊めてもらってゆっくりねた

Day1

気合入れようと思って友達とお昼から焼肉を食べた、おいしかった

泊まっていたのは大塚だったので山手線で田町まで

ちゃんと場所が見つかるか不安だったけど、近くの建物にkaedeさんがいて案内してくれた

会場で受付をして、スポンサーのサントリーさんから飲み物をもらって着席

半分ちょいくらい人がいたのでちょうどいい時間だな～と思いながらゆっくりした

席にはクリアファイルとかシールとかがあって置いてあった

みんなそれなりに早く来ていてakenshoさんがびっくりしていた

ちゃんと来ているのに遅刻オッズ1位のnoimiさんかわいそう

スケジュールに開会式って書いてあったからどんなものかなと思っていたけど、ふつうにchokudaiさんがしゃべってゆる～く終わった

特にやることもないのでライブラリとかをみながら時間を待ってコンテスト開始

A Apple Addiction

300点ね～、OKと思っていたけど開いてみると、典型だけど明らかに300ではなさそうな問題が置いてあります

気持ちを落ち着けながら考察を進めていると、周りが爆速でタイピングし始めてびっくりします

考察はそんなに重くなくて、どうせdp[i] := i番目を食べたときのmaxなので、遷移を詰めていきます

長さKはかぶってもよくK以上に言い換えられるので、そのまま伸ばす or 新しく長さKの区間をとるのどちらかをすればよく、

dp[i] = max(dp[i-1] + A[i], max(dp[0] ~ dp[i-K]) + sum[i-K+1 : i] )

という遷移になります

なんかうまいことできそうだな～と思うんですが、セグ木で自明にできるのでmaxのセグ木を使って遷移を書きます

多少バグらせるけど直すとサンプルも普通に合うので提出してAC

(AC 22:03)

B Max Degree Sum

600はさすがに解かないとまずそう + 解けそうなので次はBに行きます

最初とっかかりがなくてどうしようと思いますが、いろいろいじっていると

・両方の端点がk以下

・片方の端点がk以下

・両方の端点がkより大きい

の優先順位で結ぶのがよさそうだと思います

両方の端点がk以下となる辺はどんどん増えていって消えることはないので、これをとりあえずつなげていくUnion Findを準備します(木にしないといけないので閉路を防ぐ)

これで「両方の端点がk以下となる辺」の数はわかるので、この辺数 × 2が答えに加算されます

ほかに答えに関係するのは「片方の端点がk以下となる辺」です

これは「k以下の頂点から伸びている辺」なので、k以下の頂点から1手で到達できる頂点を列挙しておきます

ここにある頂点にはとりあえず伸ばすのが最善なので、到達できる頂点数分増えるのかな～と思って実装します

これは実装するとサンプルが合いません

もう少し考えると、同じ頂点に複数本伸ばしても閉路にならないことがあるなと思います

今までは「到達可能な頂点」を考えていましたが、逆に「到達不可能な頂点」を考えると、その頂点と連結にするために1頂点につき1本辺が必要なので、「到達不可能な頂点」の数を引けばいいかな？と思います

実装するとサンプルが合うので提出するとWA

後半パートがちょっと怪しそうなのでもう少し考えます

上の実装は、到達できない頂点以外は「片方の端点がk以下」の辺を使うことを前提としています

ただ、手元でグラフを作っているとその前提を満たせないケースがあります

そのような場合は「両方の端点がkより大きい」辺で結ぶことになります

このような辺の数は、k以下の頂点から伸びている辺をすべて使った別のUnion Findを用意しておき、その連結成分数をみる(=1でなければkより大きい頂点同士で連結にするしかない)ことでわかります

これをまとめて

(両方の端点がk以下で使う辺) × 2 + (木にするためにまだ必要な辺) - (1手で到達できない頂点の数) - (2つめのUnion Findの連結成分数 - 1)

で求めることができます　これでAC

(AC 46:20)

E Min Subtraction

Cを解こうか悩んだんですが、もうかなり解かれていて賞金を狙うには900必須(ワンチャンABD, ABEでいけない？)と思ったので、どっちかというと解けそうだと感じたEをやります

まず1回の操作で少なくとも1つは0になります

おきもちとしては、左から右に進めていくように連続して0をつくっていけると結構得する + 最終的に両方0がつくれるとアツいと思います

操作を始める場所を決め打つと、偶奇を分けたときに開始位置からの和の大小関係が単調増加 or 単調減少になっているといいことがわかります

このあたりをうまく使おうと思っていたんですが、始点が変わると大小関係も簡単に変化してしまってどうしようもなくなってしまいました

クリティカルっぽい考察も生まれなかったので賞金はあきらめてCを解くことにしました(1時間~1時間30分くらい消費)

C Power Convergence

700だし苦手よりな数学問だしな～と思って避けていたんですが、Eが虚無すぎたのでCを解くことにします

とりあえず移項すると x^k (x-1) ≡ 0 (mod N)になるので、うまくできそうな気がします

すぐに気づかなかったんですが、よくよく考えるとxとx-1は互いに素になるので、mod Nで0(Nで割り切れる)になるためにはNの素因数をxとx-1に割り振る必要があります

そうすると以下のような条件を満たす数を見つけることになります

・xとx-1は互いに素である (常に満たされる)

・x-1はNの素因数のうちいくつかを持つが、Nの素因数の指数以上でなければならない

(12 = 2^2 × 3なら、 2^1はダメで2^2でないといけない)

・xはx-1に含まれないNの素因数を持たなければいけない

(こちらはk乗するので、指数が足りていなくてもOK)

ざっくり考えると、x-1側を決め打つとxに含まれないといけない素因数がわかるので、x-1を決め打とうと思います

これは、x-1がAで割りきれる = xをAで割るとあまり1、xはBで割り切れるという2つの条件になるので、CRTを使うと該当する数を求めることができます

具体的なものも書いておきます

N = 12とすると、 N = 2^2 × 3なので考えられるパターンは以下の通りです

・x-1が1で割り切れる xが6で割り切れる -> f(x) = 2

・x-1が1で割り切れる xが12で割り切れる -> f(x) = 1

・x-1が3で割り切れる xが2で割り切れる -> f(x) = 2

・x-1が3で割り切れる xが4で割り切れる -> f(x) = 1

・x-1が4で割り切れる xが3で割り切れる -> f(x) = 1

・x-1が12で割り切れる xが1で割り切れる -> f(x) = 1

※x-1が2で割り切れるというのは、素因数2があまってしまうのでダメ

これらそれぞれについて、CRTで該当する数を求め和を取ればいいのですが、実はかぶりがあります

・x-1が3で割り切れる xが2で割り切れる -> f(x) = 2

・x-1が3で割り切れる xが4で割り切れる -> f(x) = 1

このようなものを数えようとすると、xが2で割り切れる数にはxが4で割り切れる数も含んでいるので、いい感じに処理しなければいけません

＝＝＝コンテスト中ここまで＝＝＝

これは典型的な問題で、大きい方から除原理のように解いたり、約数の高速メビウス変換をしたりなどで、重複を取り除けます

除原理をすると、x-1を決め打つパートがあるので、見た目的には約数の個数をDとしてO(D^3) になるかもしれませんが、適切に枝を刈るとO(D^2)になる(と思います)

(AC --:--)

コンテスト後

Cを解ききれず、う～んと思いながら企業プレゼンを聞いた

普通に内容はおもしろかったけど、ヒューリスティックの方が大事そうだなと思った

そもそも今のところ入学枠の都合で一般企業への就職がダメなので、そういう人で申し訳ないなと思いながら聞いた

表彰式は観客としてワクワクしながら見てた

tatyamさんでも10位なのか～と思っていたら、vwxyzさんが6位ですごーとなった

vwxyzさんの名前が呼びにくそうだった

3~5位はいつもの強い人たちだな～という感じで、1,2位は順位表的にpotatoさんとSSRSさんの争いぽかったのでどっちなんだろと思っていたら、SSRSさんが優勝していた

初観測したのでこんな人なんだと思ったけど、感想とかしゃべってもらって人柄をざっくり把握したかったな～

懇親

ご飯を食べながら懇親会で何人かお話しした

Twitterで見たことある人じゃないとしゃべりづらい...

karinohito, sotanishy, nok0, zkou, nawa, AngrySadEight (敬称略) + UNICORNやALGO ARTISの社員さんと話した

ALGO ARTISの人になんであんなに優秀な人ばっかりなんですか？って聞いたら、全力の引き抜き + 盛んな社内勉強会でレベルアップというのを聞いて、すごくいい環境だな～って思った

懇親会後はnok0さん、zkouさん、karinohitoさんと4人でガストに行った

ハイライト

・緑~水色のころコードを見ていると、同じBFS記事をコピペしていて無意味すぎるコメントが一致

・zkouさんがnok0さんに「これ解けないのやばいよ～」と詰められているのを観測

・ABC見ながら「Dやばいよね」ってみんなでわちゃわちゃする

みんなFPS分野が強くてぼくも逃げてられないなと思った

22:00すぎくらいまで色々話して解散

浜松町にホテルを取ってたので向かって就寝

春にはオンサイト(UTPCとか？)ありそうで学校も休みなので、競プロしに行こうかなと思ってます

交流してくださった方、開催してくださったAtCoder社そのほかありがとうございました！！！

ARC165 参加記

A~C 3完 66:05 247位

B通されすぎてやばかったけどCを瞬殺してプラス

A Sum equals LCM

ARCはAからちゃんと考察しないといけない

Sumの部分については、+1を繰り返すことでLCMを変化させずに1ずつ調整できるので、問題は「LCM=N, Sum ≦ Nにできるか？」に言い換えられます

これは、LCM = NとしたときにSumを最小化してくださいということなので、最小化を考えます

Nを素因数分解して、N = 2^3 × 5^2のようになったとすると、2^3, 5^2は必ず必要で、逆にそれだけ存在していればよいです

つまり、Sumを最小化しようとすると、素因数ごとに必要なものを足していくことになります

これを愚直にやるとO(√N)で通ります

もう少し考察すると解説みたいに素数のべき乗か否かになるけど、そこまでしなくてOK

(AC 4:57)

B Slinding Window Sort 2

通されすぎ～～～～

一つ一つ考察していきましょう

まず、選んだ区間は昇順ソートするので、もともとの数列より辞書順で小さくなることはありません

なので、「どこまで損をしないようにできるか？」の勝負になります

とりあえずいろいろ考えていると下の2つに気づきます

・一番後ろの区間を選ぶのはそれなりに強そう → P1 ~ PN-Kまでは動かさなくてよいからそこまでで損するパターンすべてに勝てる

・区間の中身が単調増加になっているものがあれば、そこを選ぶともとの順列と変わらないので最適となるものの1つ

ここまででそれなりに解けていそうですが、{3,2,5,4,1} (K = 3)のようなケースで困ります

これは最後の区間で操作すると、{3,2,1,4,5}になります

しかし、最善なのは[2:4]で操作した{3,2,4,5,1}です

このようなパターンはなぜ起こるか考えます

まず、最後の区間([3:5])を選んだ時にそれ以前のところは変化しない必要があります

よって、[2:4]の例だと、[2:2]にあたる区間は以下の条件を満たす必要があります

・単調増加である

・区間内の最大値 < 区間外の最小値である

解説ではこれを満たす最も左の区間にすれば最善であると示していますが、それが示せなかったのでもう少し工夫をしました

「区間[i:i+K-1]と区間[j:j+K-1] (i < j)を比較した時、どちらが辞書順で大きくなるか？」をO(logN)程度で求められればよいので、それを考えます

先ほどの議論と同様に、[i:i+K-1]で操作した方がよいのは、以下の条件が成り立つときです

区間がかぶっていない時

・[i:i+K-1]は単調増加

区間がかぶっている時

・[i:j-1]は単調増加

・[i:j-1]の最大値 < [j:i+K-1]の最小値 

よってこれを実装すると、最適なものの1つであるiが求まるのであとはそこの区間でソートしてあげればよいです

(AC 50:14)

C Social Distance on Graph

こっちのほうが簡単だと思ったけど...

2色に塗るということでまず二部グラフだったらどうなるか考えます

直感的には二部グラフで同じ側にあるものを同じ色で、違う色にあるものを違う色で塗るのが最善な気がします

↑では同じ色のところに到達するまで2手かかりますが、そうでないとすると1手で到達する箇所ができてしまうので損するだろうなと思うので、二部グラフの時は解けた(ということにします)

では、二部グラフでない一般のグラフの時を考えます

二部グラフで最善っぽい解が出ているので、二部グラフに帰着させたくなります

二部グラフに帰着させるためには、いくつか辺を取り除かなければいけませんが、その辺は同じ色同士を結ぶ可能性があるので、wiが大きいものから取り除いていくのが最善になります

よって二分探索を用いて、「重みK以上の辺を取り除いたときに二部グラフになるか？」を求めればよいです

これを満たす最大のKがわかったならば、答えはmin(K, 取り除いたグラフでの最小値)になります

取り除いたグラフでの最小値は単純で、二部グラフであることは保証されているので、それぞれの頂点についてつながっている辺の重みをソートして、小さいもの2つの和を計算すればよいです

(AC 66:05)

D Substring Comparison

めっちゃ2-SATみたいな見た目してる～

→うまく辺つなげばいけそうだけど思いつかない...

→2-SATじゃありませんでした (完)

全然解けなかった...こういうの解けると強いな

総括

ARCちょっとずつ勝てていい感じ

ABC314 参加記

7完 92:25 84位

2連続2桁でいいかんじ

発想+感想中心でCから書きます

C Rotated Colored Subsequence

よくあるやつ、各文字ごとにみればOK

左シフトと右シフト間違えて時間ロス...

(AC 18:39)

D LOWER

更新するやつ典型その1「最後だけわかればいい」

前からみて解いたんですが、「文字の変更」「大文字・小文字の変更」の2つが最後にいつ起こったか管理しておけば解けます

「大文字・小文字の変更」がそもそもない場合がコーナーになるかもなので注意

実装としてはそんなに変わらないと思うんですが、

更新するやつ典型その2「後ろから確定させる」

を使っても解けますね

(AC 29:12)

E Roulettes

期待値DPの鉄則「ゴールから考える」

これに尽きます

とりあえず期待値DPをすると考えると、

dp[i] := 今のポイントがiのとき、Mポイント以上になるために必要な金額の期待値 

と定義したくなります

遷移を考えてみます

ルーレットのどの目が出るかはわからないので、「どのルーレットを使うのが最善か？」を考えることになります

そうすると、あるルーレットを使った時の期待値を遷移先から計算できます

たとえば、1と3が出るルーレットなら

dp[i] = (dp[i + 1] / 2 + dp[i + 3] / 2) + Ci

になります

このdp[i]が最小になるルーレットを見つけてあげればよいです

ここまでできれば水diffくらいあると思うんですが、今回は0が入っているのでもう少し複雑になります

たとえば、0と3が出るルーレットなら先ほどの例と同様に

dp[i] = (dp[i + 0] / 2 + dp[i + 3] / 2) + Ci

になるんですが、dp[i+0] つまり dp[i]がわかっていないので右辺が計算できません

このように両辺にdp[i]が出てくる場合は、典型処理としてdp[i]を移項させます

dp[i] - dp[i]/2 = dp[i+3] / 2 + Ci

1/2 dp[i] = dp[i+3] / 2 + Ci

dp[i] = 2(dp[i+3] / 2 + Ci)

と式変形することができるので、これで求めることができます

(AC 41:18)

F A Certain Game

むずかしかった...

解説にある通り「Union Find の過程をマージする木」を使うと簡単な問題に帰着できるのですが、思いつかなかったので自分なりの解法を書きます

まず、操作をかみ砕くと

「大きさaの連結成分に含まれる各頂点にa/a+bを足す、bも同様」

ということになります

各頂点にそのまま足していくと2乗のオーダーになってしまうので回避する方法を考えます

発想としては、逆から見てあげることで「それぞれに足す」というのを「結んだ2つの頂点に足す」に簡略化できるかな～という感じです

まず、辺をマージするときにそれぞれの代表元を記録しておき、UnionFindでマージします

これを逆にたどることで各頂点に足すべき値を伝播させていきます

具体例をだすと

1-2, 2-3と結ぶ場合には

・代表元1, 2にそれぞれ 1/2, 1/2を足す -> マージした後の代表元は1(になったとする)

・代表元1, 3にそれぞれ 2/3, 1/3を足す -> マージした後の代表元は3(になったとする)

を逆からたどります

dp[i] := その時点での頂点iの答えと定義します

・dp[1], dp[3]にそれぞれ 2/3, 1/3を足す

・dp[1], dp[2]にそれぞれ 1/2, 1/2を足す、さらにdp[2]には本来足すべきだった2/3(=1/2を足す前のdp[1])を足す

というような操作をしました

解説よりは複雑ですが、実質的にやっていることは同じになっているはずです

Submission #44525435 - AtCoder Beginner Contest 314

(AC 71:24)

G Amulets

単純なところから考えていきます

K=0はさすがに自明なので、K=1を考えます

モンスターiを倒せるかどうかは、1~iまでのモンスターの体力をタイプごとにわけて、

「1~iまでのモンスターの体力の総和」- 「最大となるタイプの体力の総和」がHより大きくなるかを判定すればわかります

つまり、i番目までに登場したモンスターで「それぞれのタイプの体力の総和」がわかれば、その最大値を引けばいいことになります

これはvectorなどを使えばO(N)でできそうですが、Kが大きくなった場合を考えていきます

結局、i番目までに登場したモンスターで「体力の総和が大きいタイプ上位K個」がわかれば、その和を計算することで判定することができます

これはmultisetなどを使って実装できます

上位K個を入れるmultiset A, 下位M-K個を入れるmultiset Bを用意しておいて、それぞれのモンスターに対して該当するタイプを更新していけばよいです

これで、Kを固定したバージョンが解けるのですが、ほぼ同じでK = 0, 1, ... , Mが解けます

もしK個で無理になったら、そのときに上位K個のmultisetを上位K+1個に変更していきます

倒せるモンスターの数には単調性があるので、K個で突破できるものはK+1個でも突破できて、ダメになったところから考え始めるとしても問題ありません

(AC 92:25)

総括

F完全に忘れていた典型だった

ABC309 参加記

6完 38:32 + 1ペナ 185位

イコールの有無で30分溶かしてかなしい

A Nine

3で割った商とあまりで位置が特定できるので、愚直に判定すればいいですね～

WA(え？？？)

上下も入れてました...

(AC 4:46)

B Rotate

これむずかしくない？250点

時計回りに通るマスを列挙します

右向き・下向き・左向き・上向きの順でたどります

列挙したマスについて、1個先のマスに移していくことを丁寧にやるとできます

(AC 13:12)

C Medicine

350点でまた重実装かと思ったらそんなことはなかった

i日目に飲む薬の数は広義単調減少なので、値が変わるところだけ調べればよいです

(日数、個数)のpairをソートして、順にみていけばOK

最初からK以下なのがコーナーっぽいけど優しいのでサンプルにある

(AC 16:16)

D Add One Edge

条件がちょっと複雑そうな見た目ですが、簡単に言うとN1個の頂点からなる連結グラフとN2個の頂点からなる連結グラフがあって、この2つは連結でないということになります

1からN1+N2に動こうと思うと、1からAに行く、AからBに行く、BからN1+N2という3ステップになることがわかります

よって求めるべきdは「1から最も遠い点の距離」 + 1 + 「N1+N2から最も遠い点の距離」になります

ここまでくると、BFS / Dijkstraなどの最短経路を求める手法を適用してあげればよいです

(AC 24:19)

E Family and Insurance

これっぽさを感じた

D - Ki

各保険ではある頂点iから下に向かって対象者が広がるので、根をスタートして子に向かう方向で計算していくとよさそうだなと思います

公式解説と同じことしか言うことがないのですが、あと何代先まで補償できるか？という値をもってDPすれば解けます

(AC 28:53)

F Box in Box

典型詰め合わせセット

まず前提として、{hi, wi, di}はソートしておいてよいです

今回の hi < hj のような大小関係があるものを数えたい・求めたいときの典型テクニックとして、「ソートして大小関係を自明にする」というものがあります

今回ではhiをもとにして、それぞれの組をソートするとhi < hjという条件を直接調べずとも、i < jという条件とほぼ同一視できます(同じ値はうまく処理するとして)

i < jという条件は、普通にfor文を回すと「今まで出てきたものだけ見ればよい」ということになるので、かなり扱いやすくなります

これで一次元落とすことができるので、二次元のverを考えていきましょう

つまり以下の問題を考えます

wi < wj かつ di < djを満たす(i,j)の組は存在するか？

これはいわゆる「平面走査」というテクニックで解けます

Segment Treeをつくって、それぞれの葉ノードにwiを対応させます

葉ノードの値は、そのwiにおけるdiの最小値とします

こうすると、wi < wj かつ di < djを満たすかどうかの判定は

seg.prod(0 ~ wj) < dj であるか？ (prodはSegment Treeでの区間の演算)

で行うことができます

ということで、hiでソートしたうえでどんどんとSegment Treeにおける葉ノードを更新していけば、3つの条件すべてを満たすものが存在しているかわかります

2D Segment Treeとかで数え上げもできるのかな？(よくわかりません)

(AC 38:32)

G Ban Permutation

めっちゃこれ

C - Almost Sorted

上のネタバレになっちゃいますが、i-X ~ i+Xのどれを使ったか？を情報として持つといいんだろうと思います(制約が明らかにそう言ってるので)

普通に考えるとdp[i][bit] := i番目まで見て使ったものがbitであり、条件を満たすものの通り数としたくなります

しかし、「bitの範囲のものを使わない」としたときに使える個数が何個残っているかわからないので遷移ができない気がします

そこで

dp[i][j][bit] := i番目まで見てj個以上違反箇所があって、使ったものがbitである通り数

と定義します

「j個以上」というのが不思議かもしれませんが、これは包除原理を使うことを前提としているためです(j個違反するのが確定していると考えることもできます)

誤った記述だったので修正しました(参考)

包除原理をするときは「合計で i 個以上」ではなくて「特定の i 個を選んでそれらが hoge (選んでいないものについては何も言っていない)」であることを意識するのが重要

— SSRS (@SSRS_cp) 2023年7月10日

dp[i][j][bit] := i番目まで見てj個違反箇所として決めていて、使ったものがbitである通り数

と定義します

遷移は公式解説の通りです

自分がやらかしてたんですが、問題文の条件は|Pi - i| ≧ Xなので、違反する条件は|Pi - i| < X(イコールが入らない)ことに注意しましょう

(AC 111:11)

総括

実装で無駄に詰まるのかなしすぎる

ARC163 参加記

3完 97:23 506位

テスト勉強で出るつもりじゃなかったんですが、問題見てみたらC解きたかった＆思ったよりテスト勉強の進捗がよかったので15分くらい遅れて参加

C->A->Bで通したのでAC時間が変なことになってます

A Divide String

ARC-Aによくありがち

もし2個より多く分割できたときt1 < t2 < t3 ... となっていますが、そのようなときにt1 < (t2 + t3 + ... )が必ず成り立ちます

なぜなら t2に何を足しても辞書順でt2より小さくなることはないからです

よって、条件を満たすなら2つに分割する解が存在するので、切れ目をどこに入れるか全探索すればよいです

(AC 90:55)

B Favorite Game

問題名の由来、なんだろ

ある区間があって、その中に含まれるものの個数を増やしたいという問題です

どういう操作ができるか考えると

・区間を広げる(縮める意味はない)

・外にあるものを区間内に持ってくる

の2つになります

A = (1,3,5,5)のようなものを考えるとわかりやすいかなと思うんですが、区間の外にあるものを2個以上持ってくるなら、そもそも区間を広げてあげたほうがよいです

というかそもそも、外にあるものを1つ区間内に持ってくる操作回数と同じ操作回数で区間を広げることができるので、「区間を広げて損することはない」です

よって、A1, A2のみ動かせばいいということになります

ここまでくれば、A1,A2を除いたものをCとすると、Cをソートした配列で長さMの区間をすべて調べればよいです

区間を固定すると操作回数は max(0, A1 - C[i]) + max(0, C[i+M-1] - A2)で表されるので、この最大値を計算すればOKです

(AC 97:23)

C Harmonic Mean

判定込みの構築で、ちょっと苦手なタイプではありますが頑張ります

まず自明なところを処理すると、N=1 は A=(1)で満たします

N=2は無理です(1/3以下を2つだと1にたどりつかない & 1/2を使うともう一つも1/2)

N=3,5があるので少なくとも奇数はつくれるんだろうなと思います

いきなり大きなNのときの解をつくるのは難しそうなので、N=3,5の解をもとにして作ることを考えます

N=3を参考にすると、1/2 = 1/3 + 1/6になるのでこれを使ってみます

たとえば、1/3 = 1/6 + 1/12, 1/6 = 1/12 + 1/24のように分解していくと、1つの分解でNを2増やすことができます

ただ実際にこれでプログラムを動かしてみると、重複がない場合100個にも到底届かないようなものしか構築できません

よくよく考えると、これで表されるのは 1/2^a 3^bの形で表されるものですが、この個数を愚直に全探索で計算してみると(たぶん)276個になるので、制約的にどんなに天才でも達成できないことがわかってしまいます

解決策としてはもう少し複雑な形(1 / 2^a 3^b 5^c 7^d など？)を考えるか、ほかの手段を考えるかになりますが、前者でうまくいくビジョンがあまり見えなかった(tatyamさん解説に解法あり)ので他の手段を考えます

さっきの手法だと答えに使いたい数の分母が指数的に増えていって困ったので、あまり増えないようにしたいなと思ってみると、そういえば1/6 = 1/7 + 1/42にできたなとなります(え？)

こう考えると、1/k = 1/(k+1) + 1/k(k+1)に変換できるので、これを使えないかなと思います

直感的には小さいものを分解すると、すでにつくっていたものとかぶりやすいかな？と思うので、一番大きな値を分解していって、かぶらない＆10^9を超えないならば貪欲に分解することにします

実際にこれでプログラムを回すとN=500でも問題なく、1回の操作でNが1だけ増えるのでN=3~500で構築できることがわかります

(AC 88:20)

総括

Cこんなに通されるのか...みんな構築に強すぎる