Toy と帽子と ADP BE

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

AtCoder Beginner Contest 129

4完。まだ緑コーダーなのだから満足してもいい成績だとは思うのですが、Eはなんとかしたかったと思う自分がいる。

罪深いぜ令和ABC・・・。

各問題

A - Airplane

かかった時間に移動の順序は関係ないので、要するにP+Q, P+R, Q+Rの3パターンのうち最小のものを取ればいいです。

B - Balance

累積和を取ると、i番目までとi+1番目からで分けたときS1とS2はそれぞれsum[i]sum[N] - sum[i]になるので、それらの差の絶対値を端から順に取っていって最小となるものが答えです。

Bで累積和!?と思ったけど、愚直に計算しても間に合うのね。

C - Typical Stairs

i段目に上がる方法は「i-1段目に上がる方法」+「i-2段目に上がる方法」で求められるので、それをDPで回していくだけです。 壊れている段については上がる方法がないので無条件に0になることに注意です。

CでDP!?と思いましたが、漸化式が単純(ていうかフィボナッチみたいなもの)だからあり、なのか?それにしてもMODもありますしねぇ・・・。

で、単純な漸化式とか言いながら、私はすぐに思いつけず、先にDをやりました。on_

D - Lamp

まず、縦と横で累積和チック?に見渡せる範囲を保存していきます。 例えば#...#.#..という並びに対しては{0, 3, 3, 3, 0, 1, 0, 2, 2}みたいな感じで。

それから、あるマスに対して縦と横の見渡せる範囲を足して、重なり合う範囲がひとマスあるので1を引けば見渡せる範囲がわかるので、すべてのマスに対してそれを求めていって最も大きいものが答えです。

editorialでは縦横の二通りではなく四方向で見える範囲の保存をするような解説がされてましたけど、そっちのほうがまっすぐ捜査するだけで済むので実装がシンプルでバグらせにくいかもしれません。

E - Sum Equals Xor

考察の結果、editorialで言われているところの、「どちらの数についても 1 であるような桁」が存在しない、まではわかりました。

で?

どうすんの?

というところでタイムアップでした。Lを超えないようにという条件がつくので今の私には無理ゲー。

F - Takahashi's Basics in Education and Learning

ちらっと見て、そっ閉じ。

まとめ

やっぱり数学力とDPが今の最大のボトルネックなんですよねー。後者はDPの問題を解きまくれば慣れていくでしょうけど、前者はさすがにつらい・・・。

水パフォは維持できているけど、もうひと伸びがないと水色コーダーにはなかなかたどり着けないですね。

f:id:mdstoy:20190609234427p:plain

AtCoder Grand Contest 034

Aしか通せませんでした。BはTLEどまり。悔しい。

各問題

A - Kenken Race

まず、二人の移動する範囲に岩が2つ以上連続して置かれている場合は飛び越えられないので当然"No"です。 以下、そのようなことがないとして考えます。

すぬけ君がふぬけ君を追い抜く必要がない、つまりC<Dのときは、ふぬけ君を先に動かせばなんの障害もないので必ず"Yes"です。 すぬけ君がふぬけ君を追い抜く必要がある場合は、追い抜くために3マス分の空き地が必要ですので、ふぬけ君の移動範囲内にそれがあるかどうかを探します。

AGCの400だからこんなんでいいのかってびびりまくってたんですけど、これだけでよかった・・・。 境界値でミスらないかどうかがちょっと心配だったんですが、それもなくてよかったです。

B - ABC

まずは愚直に再帰で実装してTLE。まあそりゃそうですね。

で、先読みしてAABC、ABCBC、ABCABCに場合分けでしてどれだけ積み重なるか、ってやろうとしたのですが実装間に合わず。この方針があっているかどうかもわからず・・・。

ちなみに後ろから読んでましたけど、editorialを見ると前から読んでよかった?

(追記) 解説ACしました。

https://atcoder.jp/contests/agc034/submissions/5769876

うわー、難しく考えすぎてましたねこれは・・・。

C以降

見てません。

まとめ

スッキリしない結果ではありますが、AGCのB:600が通せなかったことを悔しがるくらいのレベルになったと思うことにしましょう。

なんだかんだでレート1000超えましたし。

f:id:mdstoy:20190602233322p:plain

AtCoder M-SOLUTIONS プロコンオープン

ABDの3完でした。ついにRatedで500点を通しました!!いや、3回目のはずなのですが←しつこい。

というわけで、自分の中での最低限のノルマは達成したのでまずはよかったです。

各問題

A - Sum of Interior Angles

恥を忍んで言います。内角の和の公式をぐぐりました。いきなりとんでもないタイムロスで、ABの2完だととんでもなく寒いことになるので、これを埋め合わせるためにCかDのACというプレッシャーがさらに強くなることに・・・。

B - Sumo

これは単に'x'が8個以上あれば"NO"、7個以下なら"YES"ですね。

B問題としては簡単すぎるような気がしますが、forを使うのが想定されるからBの200点ということなのか? まあ相撲を知っているか知らないかで考察にかかる時間が若干違ってくるかもしれませんね。

C - Best-of-(2n-1)

期待値計算も分数のmodも今の知識ではどうしようもないというやつでした。

D - Maximum Sum of Minimum

紙に木を書いていろいろ考察したところ、どうも根から順番に大きい数を振っていけばいいっぽいように見えたので、とりあえずそのまんまBFSで実装してみたところ(配列の添字のミスで1WA出した後)通っちゃいました。証明?知らない子ですね。

E - Product of Arithmetic Progression

これは多分なんか式変形で計算量が落とせるんですかね?と思ってちょっと考えてみましたが、手も足も出ずでした・・・。数学力のなさよ・・・。

F - Random Tournament

うーん、ふんわりとしたイメージは最後の最後に湧いたんですが(自分の両側から、勝てる可能性のある人が上がってくるかどうかがわかればよい)実装する時間はなく。もっとも正しく実装できたかどうかもわかりませんが。

まとめ

数学力なぁ・・・。

しかし、500点を通したし、パフォーマンスはHighestを更新したので大満足です。明日は鬼門のAGCですが、500点もコンテスト中に通せる率が上がってきているので、0完ってことはないでしょう。ないはずだ。多分ないんじゃないかな。

f:id:mdstoy:20190601234414p:plain

AtCoder Beginner Contest 128

3完。寒い。

でも、先週と先々週は500点通したんですよ!?(しつこい)

各問題

A - Apple Pie

問題文通りに、林檎を砕いて破片にして、元からある破片と足して、破片の総数を2で割れば答えです。

B - Guidebook

市名をソート、各市ごとに点数の降順でソート、でいいんですが、実装が面倒くさかったです・・・。

https://img.atcoder.jp/abc128/editorial.pdfでは、pair<pair<string,int>>での解説が載っていましたが、私はmap<string, priority_queue<pair<int, int>>>でやって、勝手にソートしてもらいました。ただ、そのせいでむしろ面倒くさくなったかも。うーむ。

C - Switches

bit全探索でいけるということはすぐわかったのですが、純粋に実装に時間がかかりすぎました。

D - equeue

制約から全探索できることはわかったのですが、マイナスの価値の宝石をうまく捨てる方法がわからずじまいでした。今回BとCの実装にめちゃくちゃ時間を食われたのも痛かったですね。

EとF

問題をチラ見する余裕もなかったです・・・。

まとめ

わしの実装力、どこ行った?!

でもパフォーマンス1103でレートも下がらなかったので、今回はそもそも難易度が高かったようですね。

f:id:mdstoy:20190526231736p:plain

AtCoder Beginner Contest 127

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

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

残念ながらサーバートラブルの影響で今回は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になったのは残念でしたが(個人的にはパフォ自己べを余裕で更新していたっぽいのでなおさら)、まあこんなときもありますよね。