備忘録代わりに精進記録を載せていくつもりです。分けて考えるTweetということで、今回は各問題についての簡単な解法と、その感想です。解けていない問題もいくつかあるので、ご容赦ください...運営側としてどんなことをしたか、についてはこちらの記事をご覧ください。提出コード早稲田の先輩方と言えば、やはりこのチーム名ではないでしょうか。Finalもあるみたいなので、頑張ってほしいです!今回のコンテスト唯一の簡単枠。後ろから貪欲に見ていけばよい、というものです。提出コードパズル問題です。基本的な方針ですが、マス全体の最大値を考えます。全てのマスを全部0にしたいのですが、これはどこかのマスに5が存在する、もしくは最初からすべて0であるかのどちらかが成り立っていないといけません。その条件を満たしているかどうかを調べます。この後は、上の2種類のうち、前者のみについて考えていきます。全てのマスの最大値が4以下である場合、5である場合、6もしくは7である場合、8である場合、9である場合でまず場合分けが行われます。5の場合は1回の操作で、6,7の場合は2回の操作で、8の場合は3回の操作で、9の場合は4回の操作で全てのマスを0にすることができます。これは、全てのマスの最大値が5になるように調整する回数+全てのマスを選択して0に置き換える1回、の合計となります。これにはコーナーケースが存在します。1行N列、もしくはその逆のパターンです。5が書かれているマスが端以外に存在すると、その左右のマスを1回で選択することができなくなってしまいます(5より大きい数が存在している場合に5を選択すると消えてしまうため)。それぞれの部分に分けて計算していく必要があります。最後に全部のマス目に対して操作を行うことで、全てのマス目が0となります。こんな感じの場合分けを行うと、無事ACすることができます。条件が少し細かいので、バグを抱えやすいかなと思います。解ける人は解けそうだけど、気づかない人は沼にはまりそうな問題です。提出コード全然思い浮かばなくて、結果先輩に解法を教えてもらいました。中から任意に2つ頂点を持ってくれば、この頂点のペアは距離が2以下になっています。中に入れても問題ありませんし、入れなくても大丈夫です。いうことで、基本的にグラフを木とみなしてdfsをしつつ、その戻り際にペアを作成していくことで、うまく答えを作成していきます。再帰関数を用意します(solve()とします)。引数が次に見る頂点の番号です。戻り値を以下のように設定します。根とする部分木の処理が終わっていればすると、solve関数では次のようなことをすればよいです。戻り値として返すとすると、だいたいはうまくいきます。戻り値として返すパターンです。このとき、最初の頂点のみ処理が終わっていないので、このままだと問題の条件を満たすことができません。そこで、最初の頂点については、どこかしら隣り合った任意の頂点とペア、もしくはトリオを作成するようにコードを書き加えてあげれば、無事にACすることができます。この問題、思いつくのも理解するのも解説するのも難しい気がします。ついて考えていきます。1つでも存在していれば、その区間は問題の条件を満たしません。対して上の条件を満たさないならば、これは解の候補になります。答えを求めることができます。これを高速化しなければ、この問題を解くことができません。確認と更新の部分に注目します。最大値だけをピックアップして確認するだけで、あっという間に行うことができます。これを実現するために、セグメント木を利用すればよいです。回になるので、このような計算量になります)。これです(最新作のやつ探したんですけどなかったです...オンラインの専用部屋かどこかでボイスを聞けた記憶があるので、聞きたい人は是非)。いうことで人生初の自作した問題です。自分が公開した際は、想定解が高速化する前のものでした。気づいたらすごい高速化されていたのでびっくりしました...wせっかくなので、自分の好きなもので問題を作ろう、とした結果がこれです。スマブラ要素がどこにもない...初めは、相性の段階をもっと多くして、ポイントのようなものを計算していくような問題にする予定でしたが、単純に解き方が思いつかなかったのと、相性の表現が伝わりづらい(スマブラをやってる方々なら微有利、微不利といった単語が通じますが、一般的には通じなさそうです)ので、やめました。提出コードまずは、180度という部分に注目しつつ、実験をいろいろします。なりたつことがわかります。区間が回文になっている、ということです(これは列でも同様です)。個数を調べればよく、回文判定をするのにManacherやローリングハッシュ等を用いれば、時間内に答えを求めることができます。ハッシュの衝突には注意しましょう。大学の実話から生まれた問題でした。この問題で一番楽しかったのは、サンプルケースの3つ目を書いているときです...ちなみにこんな絵を描きます。何の絵かは想像にお任せします。自作したとき、個人的にはこれめちゃくちゃ面白い!となったのであわてて提案しました。先輩方に瞬殺されてしまったので少し悔しいです(流石です)。やるべきことに気づく+必要な知識が揃っていれば瞬殺です(そのため、最初はC問題に配置されていました)が、肝心な必要となる知識が普段は見ない(と言いたいのですが、数日前に数問、この知識が必要な問題があったみたいです)ので、この位置になりました。提出コード最小カットを考えます。「戦闘場面から次の戦闘場面への道のり」にすべて分解します(出発地点から最初の戦闘場面、そして最後の戦闘場面から終着点の部分は捨てます)。辺を張るという操作を行います。あとは、sからtへフローを流し、最小カットを考えれば答えとなります。提出コード定食の種類がとてつもなく少ないので、すでに準備した定食の種類を、ビットで持つことにします。ビットがたつとします。あるとき、そこから先に発生する不満度の合計の最小値とします。定食を準備するとどれぐらいの不満度が発生するか、を高速に求める方法がわかればこの問題を解くことができます。含まれない)となります。前計算で求めることができればよい、ということになります。これは、累積和を使い、入力された定食の注文の情報を後ろから見ていくことで前計算が可能です。これを自力で解けたのは結構うれしいです。考察自体もかなりさらっとでき、実装もすんなりいったので、大満足です。提出コード完全な解説ACです。部員の方が少なかったとします。数列に縮めておく必要があります。縮めた後の数列に記録されるレートは、となります。答えればいい、となるのですが、これだとテストケースによっては前計算で時間がかかりすぎてしまいます。以上であった際は素直に定義通り計算するようにすると、どちらも時間内で解けるような計算量で抑えることができます。一度行った計算は二回目以降行わないようにメモをするのも忘れないようにしましょう。詳しくはこちらのツイートなり、後日アップされるであろう解説PDF(に書いてある...と思います)を読んでいただければと思います。https://twitter.com/yamerarenaku/status/1104721694919290880ということでとりあえず現時点で解けているのはA~G(+H)の7問です。全体の感想む、難しいです...A,B,Gは自力で解くことができましたが、他はヒントや解説をもらってから解く形になりました。結構な初心者お断りコンテストになってしまっていそうです。どの問題も個人的には面白いと思っています!コンテスト後の感想Aいきなり普段のABCで300点ぐらいの問題だったので、配点だけ見て参加して解けなかった人には申し訳ないと思っています。ここのACの人数を見ると、かなりの人が参加してくださったみたいなのでうれしいです。B虐殺問題になりました。コーナーケースに気づかないと永遠に死にます。見ているぶんには面白かったです。C自分が全く歯がたたなかったので、結構な割合で解かれていたので悔しいです。D高速化の方法に気づくかどうかが肝だったので、もしかしたらE,Gあたりより後ろに会った方がよかったかもしれませんね。E回文に気づきさえすればあとはググれば解けます。2冪modで出している方が結構多かったのでごめんなさい(数日前に衝突させるテストケースが追加されました)F思ったより解かれていなかったです。G200点の中では、かなり解きやすい部類だと思います(AtCoderの問題に近い気がします)。実際、結構な人数が200点の中でGを最初に解いていました。メモをしないと落ちるという情報だけ知っていましたので、そのTLEだけをみて遊んでいました。I,Jわからない、すごいの二言につきます最後に参加してくださった方、ありがとうございました!自分もH以降が解けたら、またここに追記していきたい...です。典型+久々につかう知識問題。電車の中で思いついたので慌てて書きました。(1)注目記事はてなブログをはじめよう!emtubasaさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。