Toy と帽子と ADP BE

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

AtCoder Beginner Contest 127

AtCoder c++ competitive programming ABC

4完。平成ABCならやったー、だったのですが。そして、先週と先々週は500点問題がコンテスト中に解けていたのですが。

各問題

A - Ferris Wheel

年齢で場合分けすればよろし。

B - Algae

forとifの、いつものB問題。x2000+i+1を出すためにx2000+iを保存しておく必要があるのがミソです。

C - Prison

一番大きいLと一番小さいRの間にあるゲートが、どのカードでも通れるゲートです。

LとRの大小関係が逆転するときに注意。通れるゲートは0になります。（マイナスにはならない）

D - Integer Cards

Aをソート、BとCの組をC（の降順）でソートして、先頭から貪欲にCで上書きしていけばOKでした。

考察より実装に手こずりました。もっと簡単な解法があるのだろうと思いながら実装でねじ伏せた気になっていたのですが、editorialを見る限り、想定解に近そうで、ちょっと意外でした。

一応、汚いですけど私の解答→https://atcoder.jp/contests/abc127/submissions/5607337

（追記） YouTubeの公式解説を見てみると、やっぱりちょっと実装が力ずくだったっぽいです。priority_queueかー。

E - Cell Distance

問題の意味がぱっと見よくわからなかった（マンハッタン距離だなーということだけはわかった）ので、Fに逃げました。

F - Absolute Minima

こちらは、問題の意味はわかるし、TLEする嘘解答ならすぐ書けたのですが、計算量を減らす方法はわからずタイムアップ。

editorial を見ると、これは知識が足りてないですわ・・・。

まとめ

EFまで安定して攻略するには数学を含めた知識の底上げが必要！？

まあABCでは水パフォ維持で、微々たるものながらHighest更新したのでよし！

f:id:mdstoy:20190525231631p:plain

AtCoder Beginner Contest 126

AtCoder c++ competitive programming ABC

ABCEの4完、そしてDが20/22WAで固まってました。（コンテスト終了時点）

（追記）結局今回もUnratedという判断になった模様です。個人的にはかなりレートを失っていることになり正直痛いのですが、データは消えても実力は消えないという言葉を胸に今後も精進していこうと思います。

各問題

A - Changing a Character

K番目の文字に、大文字と小文字の文字コードの差分である32（'a' - 'A'）を足して、その文字列を出力すればOKです。 C++だとs[k - 1] += 'a' - 'A';こういう感じで。文字列操作の超頻出テクニックです。

B - YYMM or MMYY

editorialでは入力を素直に整数として扱っていて、その方がよさげですね。

わたしは一文字ずつ区切って文字として判定してしまいました。落ち着け・・・。

くそ格好悪い私の提出コードを晒します（戒め）→https://atcoder.jp/contests/abc126/submissions/5452774

C - Dice and Coin

出力例1を見れば確率の計算方法はわかりますよね？あとはそれをコードにするだけです。

何回連続で表を出せばいいかを求めるための計算量はO(logK)で、全体でもO(NlogK)なのでC問題なのに深く考えなくても間に合います。

D - Even Relation

何がしかの木構造で解くんだろうなということは容易に想像がつくのですが、知識不足でどうにもならず・・・。

E - 1 or 2

  • Ziが偶数のとき、Ax+Ayは偶数、Ziが奇数のとき、Ax+Ayは奇数
    • 前者の場合Axが1ならAyは1、Axが2ならAyは2
    • 後者の場合Axが1ならAyは2、Axが2ならAyは1
      • これはAxとAyが入れ替わっても同じ

というわけで、どちらかがわかればもう一方も必ずわかります。 さらに

1 2 1
2 3 2
3 4 2

こういうのがあった場合、1がわかれば2がわかり、2がわかったので3もわかり、3がわかったので4もわかります。

要するに、同じ連結成分のどれか一つの数がわかると、それに対応するものすべての数がわかるというわけです。

なので、Union-Findにすべて突っ込んで、出来上がった連結成分の数がそのまま答えです。

個人的にはD問題より分かりやすかった（というかそもそもD問題できてない）ですし、実際ABCEの4完の人が結構いる模様。

F - XOR Matching

問題を読んで、回れ右しました。

まとめ

木を、グラフを、勉強しないといけない！！

AtCoder diverta 2019 Programming Contest

AtCoder c++ competitive programming

残念ながらサーバートラブルの影響で今回はUnratedとなったようです。

もしRatedだったら、ABC帯の参加者にとっては、まさかの4完早解き競争になってた！？

各問題

A - Consecutive Integers

入出力例見るまで、問題の意味が頭に入ってきませんでした。酔いの影響か？

例えばN=8 K=3なら

12345678
123
 234
  345
   456
    567
     678

で6通りということですね。

B - RGB Boxes

これも問題の意味がすんなり頭に入ってきませんでした。やっぱり酔いの影響か？

二重ループを回してrとgを決めてから、それに対応するbが存在しうるかどうかを計算して求めれば間に合う典型のやつですね。

C - AB Substrings

  • 各文字列中にある"AB"を数える
  • 先頭の"B"と末尾の"A"を数えて、少ない方の数だけさらに"AB"が組めるので加算する
    • ただし、「"B"ではじまり"A"で終わる」文字列以外に先頭の"B"と末尾の"A"が一つもなかった場合、組める数が一つ減る
      • 循環してしまうので

という感じです。

私は先頭の"B"と末尾の"A"が一つもなかった場合にも、組める数が一つ減るのロジックが働いてしまい、1WAを出してしまいました。 考察はあっているのに実装でミスるとは・・・。on_

D - DivRem Number

ロジック自体は極めて単純で、個人的には1012からいかに枝狩りできるかの問題でした。 なんか数学的にシンプルな解法があるんだろうなぁとは思いつつ。（editorialにはもちろんそのシンプルな解法が書いてありました。）

で、ちょっと考えてわからなかったので、とりあえず結果を全部出力してみます。

// N=1000の場合（抜粋）

125/ 8:0
126/ 7:118
127/ 7:111
128/ 7:104
129/ 7:97
130/ 7:90
131/ 7:83
132/ 7:76
133/ 7:69
134/ 7:62
135/ 7:55
136/ 7:48
137/ 7:41
138/ 7:34
139/ 7:27
140/ 7:20
141/ 7:13
142/ 7:6
143/ 6:142

商が同じになる範囲について、余りは大きい数字から始まり商の数だけ減少していくことがわかります。 なので、1から順に計算して、商が変わったタイミングで余りを商で割ってみて

  • 割り切れた場合
    • お気に入りの数がありかつそれは計算で求まるのでその数字まですっ飛ばすことができる
  • 割り切れなかった場合
    • お気に入りの数はないので、商が変わるところまですっ飛ばすことができる

という方法で、大幅に計算量を削減することができました。

可視化するとこんな感じです。

（前略）
126/ 7:118      // 118 % 7 != 0 なので商=6まで飛ぶ
143/ 6:142      // 142 % 6 != 0 なので商=5まで飛ぶ
167/ 5:165      // 165 % 5 == 0 なので N / x = 5 かつ N % x = 5 となる x まで飛ぶ
199/ 5:5          // x が求められているので、xを答えに加算して商=4になるところまで飛ぶ、でもいいですね
200/ 5:0
201/ 4:196      // 以下同様
249/ 4:4
250/ 4:0
251/ 3:247
334/ 2:332
499/ 2:2
500/ 2:0
501/ 1:499
999/ 1:1
2257

まとめ

考察してわからなかったら実際にやってみるが重要だった回。

Unratedになったのは残念でしたが（個人的にはパフォ自己べを余裕で更新していたっぽいのでなおさら）、まあこんなときもありますよね。

AtCoder Grand Contest 033

AtCoder c++ competitive programming AGC

0完。AGCはやっぱりまだ怖い。

各問題

A - Darker and Darker

いやもうこれが全てです。

最初は実は愚直に実装して（当然TLE）、次に思いついたのが幅優先探索だったにもかかわらず、なぜ白いマスから黒いマスへの距離を測ろうとしたのでしょうか！？

いやはや本当にちょっと頭が沸いていたとしか・・・。

B - LRUD Game

一次元に落とせることは気づいて、後ろから見ればいいということにも気づいたのですが、押すか引くかの駆け引きをどう表現すればいいのかがわからずじまいでした。

解説を聞いて、自分は問題を点でしか見れていないなーと痛感しましたね。

しかし、単に四方向への貪欲が通るのかー。 先にそれやっとけばよかった気もしますし、それで通したところでなぁという気もします。 YouTube解説ではむやみに貪欲に飛びつくと後々伸びないよー的なことを言われていたので、やらないでよかったと思うことにしましょう。

まとめ

茶色まで落ちなかったので、今回はまあよしとしましょうか・・・。

f:id:mdstoy:20190505015541p:plain

AtCoder Beginner Contest 125

AtCoder c++ competitive programming ABC

全完（ただし4WA）。

今の自分にいえることはただ一つ。

落 ち 着 け

各問題

A - Biscuit Generator

切り捨て除算で T / A をすると生産された回数がでるので、それに一回あたりの生産枚数 B をかければよいです。

（2019-06-03 追記） +0.5というのは、閉区間であることを擬似的に表しているんですね。最近知りました。罠じゃなかった。

T も A も整数なので 0.5 を足そうが足すまいが結果には影響しません。なので式にに含めなくてよいです。むしろ含めると、小数を扱わなければならなくなるため処理が面倒なことになります。

つまり、罠ですｗ

B - Resale

それぞれの宝石に対して、X - Y を計算して、結果が正のものだけを合算すればそれが答えです。

forとifの、いつものB問題ですけど、ほんのちょっと問題文読み解くのが難しかった気がします。（私だけ？）

C - GCD on Blackboard

最適解かどうかはわかりませんが、私の解法は以下の通り。

配列を2つ用意して、片方は1からN-1までの累積GCDを、もう片方にはNから2までの累積GCDを入れていきます。 つまり、9 6 3 4 6という列があったとして、A[0]には9と6のGCDである3を、A[1]にはA[0]と3のGCDである3を、というふうに累積和っぽく格納していきます。 で、2つの配列をうまく組み合わせると、1からNのうちひとつだけが除かれた状態のGCDが取れるので、それらのうちの最大のものがそのまま答えになります。

ただし、注意が必要なのはN=2のときはGCDを取るのではなくて、単にmax(A1, A2)が答えになるという点ですね。

https://atcoder.jp/contests/abc125/submissions/5156890

なお、私の4WAのほとんどは、単なるソースコードの編集ミスです・・・。on_ これで順位を160くらい落として泣きそうです・・・。

D - Flipping Signs

基本的に操作によって負数の偶奇は変化しないですが、うまく位置を取ると増やしたり減らしたりは自在にできます。 なので、最初の列に負数が奇数個なら、最終的に負数を1つにでき、絶対値が最小のものだけを負数としてほかは正数として合算します。 最初の列に負数が偶数個なら、すべてを正数として合算します。

ただし、0があると話が別で、0に-1を掛けても0なのでこれはマイナスを吸収してしまいます。ので・・・

と思っていたのですが、合計を出す時に「負数が奇数個なら絶対値が最小のものだけを負数として」扱うことにしました。しかし、0が含まれている列の場合、それは0です。なので足そうが引こうが結果が変わりません。 つまり、結局のところ0の有無は結果には影響しないのでした。無駄なロジックを書いてしまった・・・。

まとめ

今回DよりCのほうが難しかったですよね？（editorialによると、DはDPが想定解だったっぽい？）

つまらないミスで4WAも出してしまいましたが、結果は初の水色パフォ！！ このまま水色になってしまいたい。

f:id:mdstoy:20190427230452p:plain

f:id:mdstoy:20190427230800p:plain

AtCoder Tenka1 Programmer Beginner Contest 2019

AtCoder c++ competitive programming ABC

f:id:mdstoy:20190420234051p:plain

緑にはなった。なったけど、今回はAB2完・・・。納得いかん。

各問題

A - On the Way

AとBの間にCが入っていれば"Yes"なのですが、A<Bという条件はない、というのが若干面倒なポイントですね。（複数条件が必要） 恥ずかしながらこれに惑わされてちょっと時間がかかってしまいました。

B - e e *ee *e

どうでもいいですが、この問題のタイトル、マークダウン殺しですね。面倒なので修正しません。

で、問題そのものは、ifとforを組み合わせるいつものB問題でした。

C - Stones

はい。

最初WAを出した後に考察し直して、上記のツイートのケースがあることに気づきました。 で、累積和で行けそうってところまでは気づいたのですが、テンパりまくって和のとり方ミスるし、境界線をどう取ればいいのかには気づけなかったし、結局タイムアップでした。とほほ。

わかってしまえばさくっと実装できるんですがねー。

→https://atcoder.jp/contests/tenka1-2019-beginner/submissions/5066701

まとめ

緑にはなった。なったけど。（二回目）　場合によっては「緑になるまでやったこと」も書こうかと思いましたが、今回はあまりに不出来だったのでちょっとモチベが・・・。

まあとにかく慌てないことですかね。危ういと思ったら、一度書きかけのソースコード全部消したほうがいいかもしれない、とか。

AtCoder Beginner Contest 124

AtCoder c++ competitive programming ABC

ようやく、全完。

REとかWAとかあるけど（とりあえず）気にしない。

f:id:mdstoy:20190413223154p:plain

各問題

A - Buttons

これは考えている暇があったら全通り並べたほうが速いと思って（3通りですしね）、前回の公式解説YouTubeで覚えたmax({a, b, c})を早速使いました。

つまりmax({A+A-1, A+B, B+B-1})を出力ですね。

B - Great Ocean View

これはforとifを組み合わせて使えれば解ける、いかにもABCのB問題、って感じのやつですね。

常に全部比較する必要はなくて、手前にある山で最も高い山との比較さえすればよいというところが肝要。

C - Coloring Colorfully

これは塗り替えた後の状態は偶数番号白/奇数番号黒か偶数番号黒/奇数番号白の二通りなので、両方にかかる手数をそれぞれ計算して、少ないほうが答えです。

こういう解法が浮かんでくるあたり、だいぶ競プロに慣れてきてるのかなぁと思ったり思わかなったり。

私の回答 : https://atcoder.jp/contests/abc124/submissions/4944713

実装中にも、もうちょっと効率よくできると思ってはいましたが、うっかりREとか出さないように紛れのない実装にした、つもりです。

D - Handstand

最終的に通しましたが、1REと2WAはだめですね。

実装の方針は

010011100

こういうのを、状態ごとにカウントした配列に落として

1, 1, 2, 3, 2

k の数に応じて和を取って、最も大きいものを答えとする、というもの。 たとえば上記の例でK=1なら

2, 6, 5

なので答えは6、 K=2なら

7, 8

なので答えは8、という具合。

カウントした配列の偶奇、最初が0なのか1なのか、あとKの数と0の区間の大小関係で細かい場合分けが必要な実装になってしまったのですが（そのへんのコーナーケースの不備がRAやWAの理由）、もっと効率のいい実装があるんでしょうね、きっと。（←まだ公式解説配信前）

追記

公式解説によると、0 or 1の切り替わる位置を記憶すればよいとのこと、たしかにそれだと無駄に和を取る必要がないですね。

あとは二分探索やしゃくとり法でも解けるとのこと。しゃくとり法は、確かに言われてみればそりゃそうだなー。

まとめ

しゃくとり法は、まだトレーニングしていないのでやらねば・・・。

なにはともあれ初の全完は嬉しいですね。方針がわりとすぐ浮かぶようになってきているのは大きいと感じます。

f:id:mdstoy:20190413230219p:plain

次回予告、「緑になるまでにしたこと」乞うご期待。（うそ）