Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Beginner Contest 138

5完2WA。今回は比較的難易度が低かったようですね。

そして・・・

f:id:mdstoy:20190818230332p:plain

ねんがんの みずいろれーとを てにいれたぞ

各問題

A - Red or Not

条件通りにif文を書くだけです。

B - Resistors in Parallel

これまた条件通りに計算していけばいいです。入力例のところで分数の計算がしてあるので戸惑うかもしれませんが、逆数は1 / Aで求められますからそれを粛々と計算していくだけです。

C - Alchemist

価値の低い具材二つを選んで合成していくのが一番高いです。それを例えばC++ならmultisetを使えば楽に実装できます。

私はmultisetを使うべきところでsetを使ってしまい1WA出してしまいました。うーん、詰めが甘い・・・。

どうでもいいですが、珍しく整数ではなく実数を扱う問題が2問続きましたね

D - Ki

  • 木を構築します
  • 操作で示された頂点(だけ)に値を加算していきます
  • 根から再帰で降りていって親の値を子に伝播させていきます

終わりです。

これDじゃなくてCなのでは?

E - Strings of Impurity

まずtに含まれていてsに含まれていない文字がある場合、当然構築できないので-1です。 sは10100回と、充分な回数連結されるので、文字種は足りているけど長さが足りずに構築できないということは考える必要がありません。

あとは、tの文字列の先頭の文字から順にsを検索していって、文字数を積んでいくだけです。 注意するのは、検索開始位置は前回のヒット位置の後ろからになることと、単純なループで回すと安定のTLEなので効率のいい検索関数を使うことくらいですね。

私はついうっかり二重ループ解を投げて1TLEでした。(学習能力皆無)

これもEじゃなくてCなのでは?

F - Coincidence

f:id:mdstoy:20190818225918p:plain

「何らかの」規則性があることは、上図のとおり実験によりわかりました。

その規則性を式に落とす時間も実装する時間もありませんでした。まあしゃあない。

まとめ

ついに念願の水色レートに到達しました!! うれしい。とにかくうれしい。 しかし、まだ青パフォーマンスは1回しか取ったことがないので、さらに上に行くには精進の仕方を大きく変えていかなければならないようです。

「水色になるまでにやったこと」は近いうちに書こうと思っています。 45歳の現役職業プログラマがやったこと、は大抵の競プロerには参考にはならないでしょうけどw、それだけに自分には若者とは違う何かがあるかもしれないと思っているので。(ないかもしれないけど

f:id:mdstoy:20190818231219p:plain

AtCoder Grand Contest 037

1完、12:11。AGCではベストリザルトでした。

各問題

A - Dividing a String

違う文字が並んでいるところは、もちろん分割できます。

同じ文字が並んでいる場合、もう一文字取ってくれば、文字数が1と2になり文字種にかかわらず違う文字列になるので分割できます。 ここでポイントなのが、一度そのように2文字にした場合、その後ろは「どの文字が来ても」1文字で分割できます。

2文字で切る位置を工夫して、分割数を増やせる可能性も少し考えてみましたが、2文字で切った後の「どの文字が来ても」1文字で分割できるという条件が強いので多分大丈夫だろうと思い、前から貪欲に分割していく実装をして投げると通りました。

(解説を読むと、漸化式とか動的計画法とか書いてあるので、もしかしてこれ嘘貪欲だったかもしれない??)

まったくの余談ですが、上記の文章を読み直していて、「文字」という文字がゲシュタルト崩壊を起こしました・・・。

B - RGB Balls

さっぱり見当がつかなかったので、パス。

C - Numbers on a Circle

嘘貪欲しか思いつかず・・・。(大きいもの優先で後ろから引き算していく)

最後に記念提出してみましたが(おい)、案の定TLE->WAでした。

D - Sorting a Grid

制約がゆるいので、ごりごり実装したらなんとかなったりしない?と思って挑んでみるも、サンプルは通っても後はWAだらけでした。 そりゃ1100がそんなに簡単に解けるわけはないですよね。

E, F

見てません。

まとめ

Aが嘘貪欲だったのかどうかが気になります・・・。

だがしかし、嘘でも何でもAGCのベストリザルト更新で、レートもHighest更新しました。次回水パフォ中位で昇級なので、次回何度めかの昇級戦です。明日のABCで決めてしまいたい。

f:id:mdstoy:20190817235802p:plain

AtCoder Beginner Contest 137

3完1TLE1WA。もういやだ。もうだめだー。

各問題

A - +-x

計算して比較するだけです。c++だとmax({A + B, A - B, A * B})と書けます。

B - One Clue

黒であり得る範囲はX - K + 1からX + K - 1のあいだで、それを出力するだけです。

C - Green Bin

まず受け取った文字列は比較のためにソートすればよいです。

そこから最初単純に2重ループを回して無事TLEしました。(あかん

なので、文字列を入れた配列をソートして、同じものが一箇所に固まるようにしてから数え上げました。

もう一つのWAは単なる実装ミスでした・・・。

D - Summer Vacation

絶妙にTLEする解答と、時間は間に合うようになったけど答えが全然合わない解答(それ解答といえるの?)しか書けませんでした。

最初、日付ごとに報酬をpriority_queueに入れる(vectorで管理)という実装でやってたんですけどどう見ても時間計算量が足りなくて止めてしまいました。 editorialによれば、一つのpriority_queueを持って制約のきつい方から考えればよかったということのようです。

考察自体は外していなかったので、これは痛恨・・・。

E, F

見てません。

まとめ

前回もそうですが、実装のほうがネックになりつつある現状がつらいです。

あと、Dいけそうだからといって、Cより先に考察を始めてしまったので順位的にめちゃくちゃ損をしました・・・。やっぱり前から解くのが無難なんですよねぇ・・・。

なんとか緑パフォで踏みとどまって、まだ次回青パフォなら入水圏内なので致命傷には至らず。次回も頑張ろう。

f:id:mdstoy:20190810231408p:plain

AtCoder Beginner Contest 136

4完1WA。Eの解法はわかったのに最後まで不具合がなくならないという情けない結末。

各問題

A - Transfer

問題文よりC - (A - B)が答え、としませんでしたか?私はしました。on_

これはC < A - Bのケースが考慮されていませんのでWAです。この場合は容器2が空になるため答えは0にしなければなりません。ああ・・・。

しかも入力例3がまさにこのケースだという。いつもは必ず全サンプルを確認するのに、ちょっと手抜いたとたんにこの有様ですよ。

B - Uneven Numbers

editorialの解法がえげつないですな・・・。

私は場合分けして解きました。見てもらったほうが早いと思うので、提出コードだけ貼っておきます。

https://atcoder.jp/contests/abc136/submissions/6687434

C - Build Stairs

右から見るのが確実かと思います。左を見て、同じかそれ以下ならそのまま左に移ります。左が1つ高ければそれを一つ下げてから移ります。左が2つ以上高ければ、下げようがないので"No"です。

左端まで無事遷移できれば"Yes"です。

D - Gathering Children

まず、

  • 子供はRLとなっているところに集まってきます
    • 移動回数が10100とべらぼうに多いので、最終的にすべての子供がRLの位置で左右移動を繰り返すことになると考えてよいです
  • LRとなっているところで区切ることができます
    • Lより右にはいけませんし、Rより左にもいけません

なので、例えばRRRLLLRRLLの場合、最初のRLの部分に6人の子供が、次のRLの部分に4人の子供が来ることになります。

で、RとLのどちらに落ち着くかは、移動回数が偶数であることから容易にわかります。

E - Max GCD

考察でわかったこと(求めたい値をXとする)

  • 操作によってすべての要素の和は変わらない
  • 操作後のすべての要素を割り切る値Xがある場合、すべての要素の和はXの倍数になる
    • 上記より、Xはすべての要素の和の約数
      • 制約がN<=500,A<=106なので、すべての要素の和はそんなに大きくならない
      • そもそもある数の約数の総数はそんなに大きくならない
        • 約数をすべて列挙して総当りできそう
  • ある数に対しての操作の回数はA mod Xを引くか、X-(A mod X)を足すかどちらか
    • modを計算して、ソートして、あるところまで引いてあるところから足す、をやって、引いた分と足した分とが相殺できればおっけーなのでは?
      • この足し引きについては累積和の利用で計算量は問題なさそう

editorialを見てもこれで合ってるっぽいのですが(ほんまか?)、実装にバグがあったらしくいつまで経ってもサンプルが通せないままタイムアップとなりました。情けない・・・。

(追記)

F - Enclosed Points

チラ見しただけ。

まとめ

何度も反省しているような気がしますが、相変わらず落ち着きがたりません。ていうか、考察より実装力がネックになってるのは正直不本意・・・。

レートは微増で、次回こそ真・昇級戦です。(いつまで昇級戦やるの?) まあ最近のパフォで安定していれば、焦らずともあと2回ほどで昇級できる見込みなんですけどね。

f:id:mdstoy:20190804234534p:plain

AtCoder Beginner Contest 135

3完。

Dが無理だと思ったので早々に見切ってEに集中したのが完全に裏目に出ました。どうやって構築するんですかあれ!?

Cまで軽快に解いて調子いいと思ったらこの仕打ちでぐんにょりです・・・。

各問題

A - Harmony

AとBの差が奇数のときはIMPOSSIBLE。そうでないときはAとBを足して2で割ればOKです。ようするにAとBの中間点を取るということで。

B - 0 or 1 Swap

これは{1, 2, ..., N}を並び替えた数列(数字が連続している)、というのを利用して、単純に前から見ていって場所と数字があっていないところを探すのが早いんじゃないでしょうか。 数字が連続しているため、前後の大小関係を見る必要は実はありません。

C - City Savers

あー、editorialによると、前から貪欲でいいらしいです。私は考察に自信がなかったので、前から貪欲と後ろから貪欲を両方やって大きい方を取りました。てへ。

D - Digits Parade

苦し紛れに13の倍数の判定方法とかをググったりしましたがまったくわかりませんでした。まあ|S| <= 10^5なのでそんな正攻法ではいかんともしがたいです。

editorialによれば、DPだそうです。DはDPのD、言われてみればそりゃそうですね・・・。

E - Golf

Kが偶数のとき、距離は偶数単位でしか詰める(あるいは開ける)ことができません。なので、Kが偶数かつX+Yが奇数のときは構築不可能です。

それはわかったので、後は構築すればいいのですが、その方法はさっぱりわかりませんでした・・・。

F - Strings of Eternity

見てません。

まとめ

DPかー。そういえばそんなものもあったな・・・。(本当に完全に頭からDPのことが抜け落ちていたらしい)

3完にもかかわらず水色手前のパフォが出て、かろうじてレートは微上昇。次回も一応昇級戦です。いい加減しんどいぞ・・・。

f:id:mdstoy:20190727231309p:plain

AtCoder Grand Contest 036

1完3WA。まあAGCですし。

各問題

A - Triangle

二次元平面上の(0, 0), (x1, y1), (x2, y2)を頂点とする三角形の面積は|x1 * y2 - x2 * y1| / 2で求められます。(私はググりました)

Sが与えられて面積はS / 2ということなので、S = |x1 * y2 - x2 * y1|ということになります。あとはそれを満たすようなx1, y1, x2, y2を適当に求めればいいです。

私はSの平方根を求めて端数を払った後+1してそれをx1とy1として、次にS - x1 * y 1 == x2 * y 2を満たすようにx2, y2を決めました。 (最初の平方根を切り上げではなく、無条件に+1したためS=1018のとき109+1になってしまってWAをひとつ余計に出してしまいましたが・・・。)

公式解説によると、(0, 0), (1000000000, 1)と置いちゃうんですね。

B - Do Not Duplicate

TLE解しか書けずじまいでした。

周期があると思って実装していたのですが、実装がヘボいのか、周期が思ったより長いものがあるのかその両方か、といったところなんでしょうか?

公式解説によると、ダブリングなるものを使うそうで・・・。ほふー。

C以降

見てません。

まとめ

  • ダブリングを勉強する

AGCで初めて水色パフォを出してHighest更新。次回青パフォなら昇級できるところまで来ました。

早く水色になりたーい。

f:id:mdstoy:20190722003808p:plain

AtCoder Beginner Contest 134

ABCEの4完。Dはバグが取り切れずー。

各問題

A - Dodecagon

問題文に沿って、3 * r * r を計算するだけです。

こんなシンプルな問題が出たの、久しぶりでは?

B - Golden Apple

一人の監視員が監視できる本数は2 * D + 1です。そこからN本の木に対して何人監視員が必要になるかを割り算で求めるだけです。答えを切り上げることに注意。(つまり、intでの/除算が切り捨ての言語はちょうど割り切れる時に気をつけないといけないことに注意。)

え、これA問題でもおかしくないのでは?今回簡単セットなのかな?

C - Exception Handling

数列の中の最大値を、複数の項が持っている場合、いずれかの最大値を抜いても他の最大値が残ります。なので、どの項を除こうが最大値は常に同じ(数列中の最大値)です。 最大値が単独の場合、その項を抜いた場合だけは二番目に大きい数が最大値になります。

最大値とその項番は、入力を取得する時に容易に保存しておけますし、二番目に大きい数は数列をソートすれば容易にとれます。(editorialの方針1もその方法ですね)

D - Preparing Boxes

iが大きい方から見ていけば、すべての箱に対してボールを入れるか入れないかを決定することが可能です。 D問題なのに計算量についてはそれで問題ありません。i == 1のときはN個見ないといけませんが、上半分については自分自身しか見る必要がありませんからね。

とか言いつつ、私は実装をバグらせてしまい、コンテスト中にデバッグしきれませんでした。on_

(追記)

デバッグした結果はこれでした。

そんなミスするか常識的に考えて!?on_

E - Sequence Decomposing

editorialにはLISってありましたが、私はそれ系の知識を持ち合わせていないので、ごりごり実装しました。(勉強しないと)

説明はしにくいんですけど、実装は単純なのでとりあえず見てください。(えー)

https://atcoder.jp/contests/abc134/submissions/6467438

要するに、待ち受けしている数字に繋げられるなら繋げる(その際できるだけ大きい方に繋ぐ)、そうでなければ自身を新しい待ち受けにする、を繰り返して、最終的に待ち受けしている数字の個数が答え、としました。

(追記:YouTube解説と全く同じ考え方でした! なんか嬉しい)

ところで自分はvectorで実装したんですけど、こういうこときにmultisetを使うんですね。

あと、ソート済みのvectorに対しては、push_backして改めてsortするより、挿入位置を探してinsertするほうが速いということを身をもって知りました。

ダメな実装

            if (x == q.begin()) {
                q.push_back(a);
                sort(ALL(q));
            } else {
                q.erase(x - 1);
                q.push_back(a);
                sort(ALL(q));
            }

ましな実装

            if (x == q.begin()) {
                auto x = upper_bound(ALL(q), a);
                q.insert(x, a);
            } else {
                q.erase(x - 1);
                auto x = upper_bound(ALL(q), a);
                q.insert(x, a);
            }

F - Permutation Oddness

まったく考察できず。

まとめ

  • コンテナに関する知識をアップデートした
  • LISとかそういう系統の知識が全く無いので勉強しないといけない
  • 最後慌てすぎた・・・

まあ一月ぶりにHighestを(2点だけですが)更新できたので、とりあえずよし。

f:id:mdstoy:20190721010501p:plain