Toy と帽子と ADP BE

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

AtCoder Beginner Contest 143

ABCD4完、1WA。

しかし、Eがいけると思って先に考えて無駄に時間を使ってしまったので、順位がえぐいことに・・・。

各問題

A - Curtain

基本はA - B * 2ですが、これがマイナスになった場合は代わりに0を出力します。ifで分けるでもいいですが、max(0, A - B * 2)の方がちょっとだけ楽。

B - TAKOYAKI FESTIVAL 2019

何も考えず、2重ループを回しておいしさの積を足し続けるだけです。

C - Slimes

特に変な条件はないので、文字列を先頭からなめていって、違う文字が出てきたらカウントアップする、でOKです。

D - Triangles

単純に3重ループを回すとTLEします。(しました)

追記

3重ループでTLE、しません。

https://atcoder.jp/contests/abc143/submissions/8051533

どうやら私は不要な処理をごちゃごちゃ書いていたせいで定数倍マシマシになっていてTLEしてしまったようです。もったいない・・・。

(追記ここまで)

なので、aとbの2重ループにしてcは二分探索(c++ならlower_bound)で許容できる上限を探して、個数を計算して求めます。もちろんあらかじめソートが必要です。

E - Travel by Car

まず下準備として、C > Lのときはその道は使えないので除外した上でグラフを作ります。 それに対してワーシャルフロイドで最短経路を計算します。

ここで私は、「最短経路を復元」したらいいと思ったのですが、これがWAでした。 なぜなら、たとえばLが50のとき、30の道を4本使うと給油は3回ですが、41の道を3本使うと給油は2回で済むのです。 つまり、最短経路を通ればいいという話ではなかったのです。

結局、私は正しい経路を探す方法がわからずタイムアップでした。

どうやら、経路を探すためのグラフを別に作ってもう一度ワーシャルフロイドをすればよかったらしいです。なるほどなぁ・・・。

F - Distinct Numbers

みてません。

まとめ

素直に前から解いていくのがベターって最近自分で言っていたのに、またやらかしてしまいました。

レートも冷えたし、今日はさすがにちょっと前向きな材料が見つからんですね。まあ、次回からよほどのことがない限り前から解いていくと心に誓ったということで。

f:id:mdstoy:20191019230944p:plain

AtCoder Grand Contest 039

ABの2完。3WA。

Cも考察はいい線いってたっぽいです。

各問題

A - Connection and Disconnection

想定解とは違う変な解き方をしてしまったようです。以下、自分の考察です。

まず、S単体で変更箇所がいくつあるかを探します。言うまでもなく、変更が必要な箇所は同じ文字が連続している箇所です。

次に、Sを二つ連結して同じことをします。接合部分が違う文字(Sの最初と最後が違う文字)なら最初に出した回数かけるKで終わりですが、同じ文字(Sの最初と最後が同じ文字)だった場合に連続箇所が「ずれる」ことがあるためです。 例えばaaaの場合、K=1なら1回ですが、K=2aaaaaaなら3回になります。 直感的に(おい)、以下繰り返しになるだろう、つまり上記の例だと1+2+1+2+...になるだろうと踏んで、コードを書いて提出したところ、最後の一つがWAになってしまいました。

必死でコーナーケースを探したところ、abaみたいなのはK-1が正解であり、上記のロジックでは拾えないことがわかったのですが、それをうまく吸収することができず、仕方無しにメチャクチャな場合分け(SSSSの場合の回数を求めて、SSの倍になっているかいないかで判断する)を書いて無理やり通しました・・・。

B - Graph Partition

結論からいうと、すべての頂点を起点にBFSで各頂点に集合番号を振っていって、矛盾が発生すれば-1を出力し、矛盾が発生しなければ求めた集合の個数のうち最大のものを出力すればいいです。

自分は最初BFSではなく脳死再帰関数を書いて時間を溶かしてしまい、その後、勝手読みで入次数が最小の頂点を起点にすれば最大が求まると思い込み、提出したところでWAをもらい、全探索でいいじゃないかと気づき修正したところ修正漏れがあってもう一つWAをもらってしまいました。

また、最初、最大値という条件を見落として、例3がなんで4になるん???ってずっと悩んでいたのはここだけの秘密です。on_

あと、二部グラフうんぬんというのは問題をみた瞬間わかりましたが、二部グラフに関する実装はまだ勉強していないため気づかなかったことにしました(おい

C - Division by Two with Something

1を引いて2で割るという操作は、右に一つシフトすることと同値、2で割って2N−1を足すという操作は右に一つシフトして最上位に1を立てるのと同値です。 それを元にシミュレートすると、通常は操作に2N回かかることがわかりました。また、1010101のように1と0が交互に出現するものは2回で終わることもわかりました。

とりあえずその方針で実装していたのですが、ぎりぎり間に合わず・・・。コンテストが終わってから実装ができましたが、うまくいく例といかない例があったので、結局ダメでした。

結局のところ、考察が中途半端だったようで、editorialやYouTube解説によると、2N回かからないものが単純に一つずつ交互だけじゃなくて、周期性がある場合にも発生する、ということのようです。

まとめ

500点問題を久々に通して、レート大幅回復を達成できました。Cもある程度考察を進めることができたので、これはもう大躍進と言ってもいいのではないでしょうか!?(いつものポジティブ)

それはさておき、また水色復帰が見えてくるところまで戻ってこれたので、この調子で行きたいですね。

f:id:mdstoy:20191006010113p:plain

Xubuntuにaptでchromeをインストールする

これもうやるたびにググっていて、10回は軽く超えているような気がするので備忘録としてここに書いておきます。

listに加えた後にapt updateをするのを忘れずに。

$ curl https://dl.google.com/linux/linux_signing_key.pub | sudo apt-key add -
$ echo 'deb [arch=amd64] http://dl.google.com/linux/chrome/deb/ stable main' | sudo tee /etc/apt/sources.list.d/google-chrome.list
$ sudo apt update
$ sudo apt install google-chrome-stable

AtCoder Beginner Contest 142

f:id:mdstoy:20190928225952p:plain

↑戒め。

4完、3WA、1TLE。

Dまで11分で解けてたのに、作ってあった素因数分解の関数にいろいろまずいところがあって、そこから23分+ペナ20分を溶かすという情けない結果になってしまいました。

各問題

A - Odds of Oddness

「1からNまでの間の奇数の個数」÷N、をやるだけです。答えを実数で出さなければならないことに注意することと、Nをintじゃなくてdoubleで受け取って計算しようとすると結果がおかしくなることに注意します。(ちょっとハマりました)

B - Roller Coaster

ひとりずつ基準値をクリアしているかどうか確認するだけです。forとifを使えれば解ける、This is B問題ですね。

C - Go to School

「教室にAi人の生徒たちがいた」というのはつまり、その生徒がAi番目に登校したことを表します。Aiとiを紐付けてからAiでソートすれば登校順に並ぶので、あとはソート後のiを順に出力していけばいいです。

D - Disjoint Set of Common Divisors

AとBの最大公約数を取って、それを素因数分解して、素因数の種類(と、1の分で+1)が答えです。 例えば入力例1ならgcd(12, 18)が6で、素因数分解して2*3で、1, 2, 3が互いに素、という具合です。

ここまで11分でできていたのに、冒頭で述べたとおりの有様でかなりの時間を無駄にしました・・・。

作ったライブラリはちゃんとテストしましょうね・・・。

E - Get Everything

DPなのは容易にわかったのですが、どのように状態を定義すればよいのかを見つけられず・・・。

F - Pure

トポロジカルソートとか閉路検出とかでググってなんとかしようとするも、時間切れでした。

まとめ

前述の通り都合43分のロスで、パフォ250くらい持っていかれました。痛恨・・・。 あと最近Eが解けてない・・・。たまにはEまでいけないとジリジリとしか回復できないですね。

まあライブラリのバグを見つけられたことと、Dまで実質11分で解けていたことで、今日はよしとします。 下げなくていいレートを下げてしまったのでよくないんですけどね。on_

f:id:mdstoy:20190928233406p:plain

AtCoder Grand Contest 038

久しぶりの0完。

各問題

A - 01 Matrix

先週参加したyukicoderに似たような(?)問題があったので、それを元に実装して投げてみたところWAをもらいました。(それはそう

で、改めて違う構築法で満たせるようなケースがあるかどうか考察し直してみたところ(いや、最初の解答を投げる前に考察しろよって話ですが)、0で条件を満たす場合と1で条件を満たす場合が混在するケースがありうるということがわかりました。例えば 3 5 2 1のような。

あとはそれを一般化して実装すればいいだけの話なのですが、一般化できず終了してしまいました。

そして、終了後editorialをみて崩れ落ちましたよね。

f:id:mdstoy:20190922011452j:plain

実は机上の考察で、ここまで作れていたのです。そこまでやっておいて、なぜそれが真実であることに気づかないのか・・・。on_

B - Sorting a Segment

BCDの中で一番可能性がありそうだったBをAと並行して考えていましたが、結局正しく考察するには至らず・・・。

まとめ

やっぱりAGCは怖いですね・・・。

レート激減して、一発で水色復帰しようと思うと青パフォが必要になるところまで落ちてしまいました。 ただ、今までの傾向として、レートを大幅に落とした次の回はそれを上回る幅で回復してきているので、次回もそうなれるようにがんばります。

f:id:mdstoy:20190922013816p:plain

AtCoder Beginner Contest 141

4完。Eが怒涛のTLE地獄・・・。

各問題

A - Weather Prediction

if文をみっつ並べればよいです。対象が文字列なので、格好つけて配列を使って回したりすると逆に面倒くさいです。

こういう問題で一番怖いのはタイポだったりします。問題文からのコピペ推奨。

B - Tap Dance

問題の読み替えをするとちょっと楽になります。つまり、奇数文字目に'L'が入っているか、偶数文字目に'R'が入っている場合は"No"、そうでなければ"Yes"です。

ところで、なんで問題文をDDRに絡めずにタップダンスにしたのでしょうか?そこがちょっと不満です(え?

C - Attack Survival

愚直にシミュレートすると終わらなくなるのは明らかなので、これも視点をちょっと変えてみます。 最終的に、Q - 正解数がマイナスされるポイントなので、各参加者の正解数を保存しておいて、参加者ごとにQ - 正解数がKを下回っていれば"Yes"、K以上なら"No"となります。

D - Powerful Discount Tickets

大きい数を2で割るほうが効率がいいことは明らかです。なので、一番大きい数を2で割る→その結果一番に躍り出た数を2で割る、を延々(M回)繰り返せばいいです。 例えばc++ならpriority_queueを使えば簡単に実装できます。

E - Who Says a Pun?

4重ループ(重なり合わないような二つの範囲の始点と終点)を回してfindしてTLE地獄でした。

editorialをみると、Z-Algorithmとかローリングハッシュとかあって、あーそれ系の問題かー、となりました。要復習・・・。

F - Xor Sum 3

何かが見えたような気がしましたが、気のせいでした。

まとめ

Z-Algorithmとかローリングハッシュって何ヶ月か前にもみたなー、復習不足だなーという。復習大事。超大事。

水色パフォで、レートは微増ながら水色復帰はならずでした。

f:id:mdstoy:20190915232057p:plain

AtCoder Beginner Contest 140

3完。DとFの見合いで最終的にFで突っ走ったのが結果的には立ち回りミスだったかもしれません。でも見えた気がしたんだよなぁ・・・。

各問題

A - Password

これは単純にNの3乗です。

B - Buffet

問題文の通りシミュレーションすればよいです。満足度Cの加算条件に気をつけるくらいでしょうか。

C - Maximal Value

A1はB1、AnはBn、それ以外のAiはmin(Bi-1, Bi)となります。まあAからBを作るときの裏返しですね。

D - Face Produces Unhappiness

私は、反転した時に同じ向きでつながる人数が最大になるような場所を反転させる、でしたが(それでも間違いではないのかもしれませんが)、愚直に実装するとTLEが見えているので少し考えて実装を断念しました。 editorialをみると、やはり私の考察は的外れでしたか・・・。

E - Second Sum

一瞬考えましたが、すぐスルー。

F - Many Slimes

机上で作りうる最大の数字を生成するようにシミュレーションしてみると、パスカルの三角形が浮かんできたので、集合Sの要素の個数を大きいものから累積したものがパスカルの三角形の累積和を超えなければYes、としてみましたが、おおよそ半分までACでそこから殆どがWAとなりました。結果WAなのでこの方針でいけるのかどうかもわかりませんが、仮にいけたとしても、あとひと押しかふた押しが必要だったようです。

まとめ

Dを考え続けるべきだったのかFにチャレンジすることが正しかったのか、未だにわからないです。

水色復帰がまた遠のいてしまった・・・。まあCまでがすんなり解けても、Dが解けないと水色は遠いということがはっきりわかる結果でよかったかもですね。(ポジティブ

f:id:mdstoy:20190907230901p:plain