ひらめの日常

プログラミングと読書と

Educational Codeforces Round 63 D. Beautiful Array

Beautiful Array

問題はこちら

codeforces.com

自分が気づいたところ

まず最初に,xが負の時は最小区間和を選んできてそれをx倍する.xが正の時は最大区間和を選んできてそれをx倍する.とすれば最大値が求まると考えた.ここでセグ木とかをググり始める... だが,区間和を取ってきて,その区間和のindexも取ってくるのはどのようにして実装すればいいかわからなかった.

次に,累積和を尺取りのように持てば区間和の最大・最小を検出できるのではないかと考えたが,これもACにはならず.

解説を読んで

TwitterでDPだという文面を見たので,実装は見ないで自分で書いてみた.状態の遷移は以下の通りにできると考えた.

ここでは3の状態がポイントで,一回*xをする→そのまま足すという遷移をした場合は,もう一度*xをして足すことはできない(連続した区間にのみ*xできる)ためにそれを新たに状態として持つことにした.

dp[i+1][0] := i番目をそのまま足す
dp[i+1][1] := i番目を*xして足す
dp[i+1][2] := 使わない(0にリセット)
dp[i+1][3] := i番目までに*xをしたことがあり,i番目のものはそのまま足す

状態遷移はそれぞれを場合分けしてイテレーションを回していく.詳しくはコードを見ると早いと思う.

Submission #53197896 - Codeforces

こちらの解説を見るとどうやら状態数は3つでいいらしい??(後ほど実装したい)

cinnamo-coder.hatenablog.com

こちらの解法が似ているらしいので後ほど解きたい.

atcoder.jp

自分の詰まったところ

  • そもそもDPという発想がコンテスト中に浮かんでこなかった.
  • 遷移の歴史によって,次に行える遷移が違うがそれをどう実装するかについて.

学んだこと

  • 遷移規則が複数あるが,列挙できる → DPという発想.
    • 連続区間を 使う/使わない などはかなり典型例になるのでは??
  • 状態を増やすことによって遷移規則を表現できることがある.

Tenka1 2019-C Stones (300)

Stones

問題はこちら

atcoder.jp

自分が気づいたところ

  1. 全ての石が黒 or 白になると勘違いをし, WA
  2. 左端から ... と白が続いている時は無視し,そのさきは全て黒 or 白になると勘違いし,WA
  3. 右端から ### と黒が続いている時も無視できることに気づくが,黒→白に変更することを実装せず,WA * 2
  4. なぜか1, 2, 3を合体させた実装を提出し,WA
  5. ここでようやく ...##というならびになるような境界をずらし,累積和を使って計算してくことに気づくが,境界条件をミスってWA

ということで,結果としては6ペナ1完でひどいことになりました. f:id:thescript1210:20190421071658p:plain

Submission #5069132 - Tenka1 Programmer Contest 2019

自分の学んだこと

  • 早解きのモードになっていたので,簡単な実装で何回もWAを連発してはいけない.
  • 境界条件をずらして行くときに,全てが黒 or 白の場合もきちんと考慮すること.
  • 自分のヒューリスティックな解法が証明されたものでなければ,きちんと状態を列挙して解を求めに行くこと.

Codeforces Round #552 (Div. 3) E. Two Teams

Two Teams

問題はこちら

codeforces.com

自分が気づいたところ

愚直解は,毎回使っていない最大値を検索→幅  kを探索し,使っていないものをk個チームに属させるというもの. 計算量としては,  n=O(10^{5}) なのでそのまま実装すると  O(n^{2})になるので間に合わない.

そこで,一回使ったものは取り除いて考えることができるようなデータ構造を考えれば良いと気づいた.

ここで,すでに使用したindexを扱う問題としてこれを解いたなーと思いながらも,帰着させることはできず.

B - Minimum Sum

AGC005-B 「Minimum Sum」 (400) - Mister雑記

解説を読んで

解説はこちらを参考にさせていただいた(いつもありがとうございます...!). cinnamo-coder.hatenablog.com

ある要素から右方向にあって、まだチームが決まっていない選手の最小のindexを持つことでこれは達成できる。左方向にも同じものを作っておく。

そこで,以下のように実装し,随時これをupdateする実装をした.

set<int> s : 使用してないスキルの集合
l[i] : i番目の人から,左方向でまだチームが決まっていない選手の最小のindex
r[i] : i番目の人から,右方向でまだチームが決まっていない選手の最小のindex

https://codeforces.com/contest/1154/submission/52917361

自分の詰まったところ

l[i], r[i]が端に到達した時の扱い方として,-1を立てるという方法にしたが,ここでバグを発生させていた.一回きちんと落ち着いて手で書いてからやった方が良い.

純粋にindex周りを扱うデータ構造の実装が遅い.

学んだこと

  • 最短の距離にあるものをそれぞれupdateしていくとうこと.
  • 値がdistinctな時には,array[それぞれの値] = index という構造を使うことでindexの復元が容易であるということ.

Codeforces Round #551 (Div.2) C Serval and Parenthesis Sequence

Serval and Parenthesis Sequence

問題はこちら 問題文難しくないですか...

codeforces.com

自分が気づいたところ

括弧を扱う問題では,stackを用いると綺麗に書けるなと思い実装.しかしコンテスト時間内に問題文を解読できなかった...

解説を読んで

このブログとかが簡潔かつ分かりやすかった. perogram.hateblo.jp

使える(の数をカウントしておく(=cとする).

?が現れたとき,c>0の場合貪欲に(を使う.なぜなら,なるべく(を左に持っていった方が途中で正しい数式になってしまう可能性が下がるから.c==0の場合は,(を使っても文字列全体として正しい数式になることはないので,)を使う.

そして,括弧の管理はstackで行う.s[i]=='('の時はstackにpush.s[i] == ')'の時は,stackが空でなければpop.といったようにする.stackが空になるということは,その時点で()の数が等しい.→正しい数式になっている.

これを踏まえると求められている条件は,「出力文字の途中でstackが空にならない.かつ,最後にはstackが空になる」であるので,それに従って貪欲に解を構成できるか試す.

https://codeforces.com/contest/1153/submission/52734359

自分の詰まったところ

  • 問題文の解読.
  • 変に左右の括弧の数を数えて累積和とかやってた.
  • 不正解となり得るパターンをどのようにして判定するか.

学んだこと

  • 片方を使える分だけ貪欲に使っていくと,もう片方とのマッチング可能性は下がっていく.
  • stackを使わなくても,( → +1, ( → -1という風に変換してあげればもっと簡単に計算できる.

JOI2018/2019-D 日本沈没(難易度6)

日本沈没

問題はこちら

atcoder.jp

自分が気づいたところ

小課題1に関しては,愚直にシミュレーションしていけば求まるが,満点をもらうことはできない.

  A _ {i-1} \gt A _ {i} \lt A _ {i+1} のように,谷になっているものに注目した.すると,問題は「谷となっているところのうち,一番低いところ  b と,左右の崖のうち低い方 l の間の区間  b \leq s \lt l が,一番重なっているところはどこか」という風に言い換えることができる.

...しかし区間の重なりと捉えたところで計算量が落ちるわけではないのでよく分からない...

解説を読んで

状態ごとに捉えてみる.具体的には,「注目している陸地が一つ沈んだ時に島の数はどうなるか?」について注目する.すると,注目している陸地の左右に注目するだけで変化を捉えることができる.考えていることは近いが,自分は谷に注目していたので処理が煩雑になっていた...

JOI 2018/2019 予選 問題4 解説

そこで,陸地をsortして順番に海面を上げていき,陸地の数の増加を数えれば良い.計算量はsortがボトルネックとなり  Nlog(N)

Submission #4936590 - JOI2018/2019 予選ページ

自分の詰まったところ

  • 陸地が同じ高さで連続している時に,余分に引き算をしていたので,入力を読み込む時に連続しているものは弾くことが必要.
  • 全ての陸地が0の時にバグが発生すので,陸地の入力の最初と最後に高さ0を入れることで解決.

学んだこと

  • 注目するものを転換するということは大事だと思った.一つのものに注目していて解法が出ない時,その対照的なものに注目すると答えにつながる可能性がある.
  • 状態ごとに捉える(i-1回目からi回目への遷移でどのように答えが変化するか)ことが苦手なので,トレーニングが必要.
  • 重複は入力の時点で弾く.
  • コーナーケースに対しては,入力の両端に自分で何か加えるとうまくいくことも多い(lower_bound()の時などが思い返される...)

ABC045-D すぬけ君の塗り絵 (400)

すぬけ君の塗り絵

問題はこちら

atcoder.jp

自分が気づいたところ

 H=O(10^{5}), W=O(10^{5}) なので,全てのマス目を調べていくのは間に合わなさそう.そこで,黒く塗られているマス目だけに注目することにした.

一つの黒いマス目が影響を及ぼすマス目は,周囲の9マスだけである.これを考慮すると, 3\times3のマス目の中心になり得るマス目は最大でも  N\times 9 になるので,間に合いそう.よって, 3\times3 の中心のマス目として考えられるものに対して周囲の黒いマス目を数え,すでに見たマス目はmap<pair(int, int)>で管理することによってACした.

実行時間1946 ms...

Submission #4911309 - AtCoder Beginner Contest 045

学んだこと

  • 他と違うものに注目する(?)
  • unordered_mapのキーにpairは入らないけど,mapのキーには入る.(pair内部にhashは用意されていないが,比較関数は定義されているので)

ABC095-D Static Sushi (500)

Static Sushi

問題はこちら atcoder.jp

自分が気づいたところ

最大でも反対方向に向きを変える動きは一回だけなので,反転する場所を一つ決めてそこから反転した後の最大値を求めることを考えた.

これだと,計算量は反転する場所が  O(N),反転後の最大値探索が累積和を使うと O(N)O(N^{2}) になるので,部分点はもらえる.

Submission #4898403 - AtCoder Beginner Contest 095

しかし,ここから計算量をどうやって落とすのかが理解できなかった.

解説を読んで

「最大値を保持」しておけば良い.ということがわからなかったので,以下のブログを参考にした.

blog.livedoor.jp

最大値をdpの値として持っておいて,逐次更新していく.

自分の詰まったところ

取得カロリーの累積和を事前に計算しておき,dpの更新時に距離分の消費カロリーを引く.自分は逐次差分  x(i+1) - x(i) を追加していく方法だったが,これだと例えば一個飛ばして更新が発生した時に正しく消費カロリーが計算されない.

Submission #4900921 - AtCoder Beginner Contest 095

学んだこと

  • 最大値dpという考え方.「iまでの最大値」という値の持ち方をすることで計算量が下がる時がある.
  • 往復可能なものについては,折り返しが何回起きうるかを考えてみる(だいたい1回で十分な時が多い).