AtCoder Beginner Contest 139

4AC2WA。

そして・・・

レートは前回比+1で、水色まであと1というミラクル！？

そんなミラクルいらんて・・・。

各問題

A - Tenki

SとTのi文字目が同じなら的中です。それを3日分確認するだけの簡単なお仕事です。

B - Power Socket

タップを差すたびに、一口消費してA口新たに増えるので、差し引きでA - 1増えていきます。そこから計算式を立てて求めるもよし、ループで一つずつタップを増やしていくもよしです。

私は実装がちょっとまずくて、B==1のとき0が返らないという恥ずかしいバグで1WA出してしまいました。

C - Lower

単純にループを回して、右隣が今いるマスの高さ以下なら移動数を増やし、そうでなければリセットします。リセットした時に、それまでの記録を上回っていれば保存しておきます。 最後まで終わった時に保存されている記録が答えです。

B問題っぽいですね？

D - ModSum

{1, 2, 3,..., N}を一つずらして{N, 1, 2,..., N - 1}という数列を作るのが最適です。 こうするとN % 1 + 1 % 2 + 2 % 3 + ... + (N - 1) % Nのように初項以外すべてで最も効率のいい「割る数 - 1」の余りが取れるわけです。

なお私はintで計算して無事1WAを出しました。本当に学習能力がないですね？

E - League

ひたすらループでなめていく愚直解でTLEをもらって、改善できずに終了でした。

F - Engines

単純に4方向に分けて考えて、例えばx正y正方向に進むなら、x負y正またはx正y負は足してみて得するなら採用みたいな方針でやると、だめです（だめでした）。 多分ちゃんとベクトル計算をしないといけないのだろうなとは思いましたが、死ぬほど幾何が苦手な私には無理ゲーでした。

まとめ

数学、数学か・・・。

しょうもないコーナーケースのバグか、うっかりintでオーバーフローのどちらかがなければ水色復帰していたというのはつらい。 ちなみに、このレベル帯ですと、1WAでパフォが100前後落ちるようです。本当につまらないWAには気をつけましょう・・・。

AtCoder 第一回日本最強プログラマー学生選手権-予選-

2AC1WA。

そして・・・

ぎりぎり緑に落ちたー。

各問題

A - Takahashi Calendar

愚直に月と日で2重ループを回して計算すればよいです。

私は恥ずかしながら、d1とd10が≧2であるという条件を見落としていて、7分かかってしまいました。条件はちゃんと読もう。

B - Kleene Inversion

まずA単体については愚直にループを回して転倒数の数を求めればよいです。これがK個あるのでK倍します。

Bの中のAについては、後ろに繋がっているAの中にある転倒数となり得る要素すべてが対象となるので、累積和である数以下の数を保存しておいて（editorialによると、そこまでしなくても全探索で間に合うそうですが）、それぞれの要素に対して数を求めて足し上げて、K * (K - 1) / 2を掛けます。（先頭のAに対しては後ろにK - 1個のAが、2番目のAに対しては後ろにK - 2個のAが・・・、という具合に (K - 1) + (k - 2) + ... + 1個ある）

上記の二つを足したものが答えです。（適宜MODを取るのを忘れない。あと、/2の部分に注意）

私はいろいろ考察ミスをしてしまい時間を溶かしたあげく、MODを取る際に括弧の位置を間違えて1WA出してしまいました。

C - Cell Inversion

考察すらまともにできず、タイムアップでした。

いま、これを書きながら解説放送を聞いているんですが、つい最近同じような問題がありましたね？うーん、復習不足・・・。

まとめ

細かいミスの積み重ねの結果、緑に落ちてしまいました。まあ仕方ない。次回からまたがんばります。

AtCoder Beginner Contest 138

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

そして・・・

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

各問題

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は10¹⁰⁰回と、充分な回数連結されるので、文字種は足りているけど長さが足りずに構築できないということは考える必要がありません。

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

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

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

F - Coincidence

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

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

まとめ

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

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

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で決めてしまいたい。

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より先に考察を始めてしまったので順位的にめちゃくちゃ損をしました・・・。やっぱり前から解くのが無難なんですよねぇ・・・。

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

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

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

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

E - Max GCD

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

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

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

（追記）

これ、結局自力ACできた
minとmaxを取り違えるとか変数を取り違えるとかの細かいバグをいくつか仕込んでいた模様・・・
ある程度実装が重くなることが予想できた時点で、速度より確実性を重視すべきということなんだろうhttps://t.co/xzHC1xJDDR

— Toy (@mdstoy) 2019年8月5日

F - Enclosed Points

チラ見しただけ。

まとめ

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

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

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