AtCoder Beginner Contest 184 参加記

2020/11/22に開催されたAtCoder Beginner Contest 184に参加しました。

atcoder.jp

21日のARCでは大きくやらかしてしまい、無念の茶落ちを喫してしまいました。

今回はレート下げた分をすこしでも取り戻すべく、気合いを入れて臨みました。

今回の結果

で、、今回の結果ですが、3完という微妙な結果で終了しました。

ABC184結果

ABC184結果

が、なんとパフォーマンスはそこそこ良好の緑パフォだったので、前回下げた分は少し取り戻せました。

最近のABCの傾向では、4完でも茶パフォというのが結構あったので少し意外でしたが、まあ結果オーライです。

振り返り

Cまでそこそこ順調でした。Eは惜しかったです。

ABC184提出結果

ABC184提出結果

A問題

A - Determinant

問題文のとおり計算するだけです。問題なくAC。

B問題

B - Quizzes

これも問題文のとおり計算するだけ。問題なくAC。

C問題

C - Super Ryuma

最近のCにしてはだいぶややこしい問題。以下の考察で実装を進めました。

  • ナナメは無限に移動できるので、2手で座標の和の偶奇が等しいマスには行ける
  • よって、目標がどこであろうと最大手数は3手となる
  • 0手と1手は簡単に求めることができるため、問題は2手のケースの判定
  • 現在位置から3マス動いたところを全て列挙し、そこから1手で移動できれば2手
    移動できなければ3手を答えとする

考慮漏れが心配でしたが、投げてみたらなんとか一発ACでした。

D問題

D - increment of coins

 確率の期待値計算問題。

ぶっちゃけ全然計算方法がわからんかったんでパスしました。。

また解説ACします。

E問題

E - Third Avenue

 あ、これBFSで迷路探索するやつだ!ということで、これならなんとかなるかという思いで、残り時間を全てE問題に賭けて実装に取り組みました。

で、なんとかサンプル通るまで完成したので投げてみたら、これがまさかのTLE。。

少し工夫して投げた2回目も無念のTLE終了で結局ここでタイムアップとなりましたー。

コンテスト後の解説を読んでみたら、ワープをする際の考慮が全然足りなかったとのこと。これがACできてれば、かなりレートが跳ねてたと思うので非常に残念です。

F問題

F - Programming Contest

 コンテスト中は諦めて全然見れてませんでしたが、TLをみてみると、なんと典型問題だったようですね。ま、時間があっても解けてたかどうかはわかりませんが。

これまでの実績

前回のレート暴落からの半値戻し。緑復帰までもうちょいです。

コンテスト実績

コンテスト実績

総括

前回のレート暴落から、少し取り戻せたのでなんとか気持ちが楽になりましたが、油断してると来週また暴落を喰らってしまうかもしれません。今後は毎日精進の時間を作るように努力します。

また、次回も頑張ります。

AtCoder Regular Contest 108 参加記

2020/11/21に開催されたAtCoder Regular Contest 108に参加しました。

atcoder.jp

やっとこさ緑になったと思ってたら、前回のABCで久々のレート下げ。早速茶落ちのピンチを迎えました。

今回はなんとか緑パフォを死守すべく、2完は確保しようという気持ちで臨みました。

今回の結果

で、、、、今回の結果は無念の1完終了でした(泣)

ARC108結果

ARC108結果

こらあかんわと思ってましたが、結果を見るとなんと超久々の灰色パフォーマンス。。

レートは暴落し、無念の茶落ちを喫してしまいました(T_T)

振り返り

ARC108提出結果

ARC108提出結果

A問題

A - Sum and Product

多分、まともに全パターンやるとTLEになるやつ。工夫が必要だと思い色々悩んだ結果、二分探索でやればいいんじゃね?という結論にいたりました。

で、ここからが慣れない自力の二分探索を実装。デバッグしながら試行錯誤してたら、サンプルが通ったのが、開始40分経過した頃でした。

 

んで、投げてみたら、P = 1のケースで引っかかりWA。。orz

 

結局、微修正してACできたのが開始48分後でした。

コンテスト終了後に解説を確認すると、結局Nを1から\sqrt{P}まで全探索すりゃいいんだということに気づいて愕然としました。もう少しシンプルに考える必要がありましたねー。

B問題

B - Abbreviate Fox

 まずは単純にJavaのStringBuilderクラスを使って、文字列sから"fox"が見つからなくなるまで検索、削除していくという実装をしました。

で、これで通ればいいんだが、結局投げてみたら案の定のTLE。。

ここから、色々再帰を使うか、スタックをどう使うかとか色々思案しましたが妙案が思いつかず時間だけが過ぎていく。結局、うまい実装ができずにこの問題でタイムアップとなりました。。

コンテスト後に解説とかTLとか見ると、スタックに普通に積んでみたり、別の文字列に値を追加しながら"fox"を削除するなど色々簡単なやり方があったのだということに気づいてこれまた愕然としました。

C問題

C - Keep Graph Connected

Bから少し浮気してみたが、一読ではわからず、とりあえず諦めました。

D問題

D - AB

問題すら見れてません。

E問題

E - Random IS

問題すら見れてません。

F問題

F - Paint Tree

問題すら見れてません。

これまでの実績

ボロボロの内容で文句なしの茶落ちです。ギリギリの惜しいところで落ちるとかではないので、逆にスッキリしたかもしれません。

コンテスト実績

コンテスト実績

総括

今回は、あまり難しく無いはずの問題をこんこんと考え込んでしまい、ドツボにハマってしまいました。最近アルゴリズムの勉強が多くて、実際のコンテストで出される全探索の問題を解いている数が不足しているのが原因なのかもしれません。

緑パフォ以下の問題を解きまくるような練習に取り組もうかと思います。

また、次回も頑張ります。

AtCoder Beginner Contest 183 参加記

2020/11/15に開催されたAtCoder Beginner Contest 183に参加しました。

atcoder.jp

前回のコンテストで、やっとこさ入緑。今回のコンテストでは、なんとかレート下げを食らわない程度で頑張ろうということで、最低4完、目標それ以上という感じで臨みました。

今回の結果

で、、今回の結果ですが、なんとか終了ギリギリで4完に滑り込みましたー。

ABC183結果

ABC183結果

しかし、4完したもののタイムが悪く、無念の茶パフォ。。

これまでずっと上昇傾向だったレートも微減を喰らってしまいました(泣)

振り返り

Bで大きくやらかし。他にも小ミスが続いて4完確保がやっとでした。。

ABC183提出結果

ABC183提出結果

A問題

A - ReLU

JavaのMax関数を使って、Max(0,x)を返すだけでACできました。

B問題

B - Billiards

 問題を最初に読んだとき、「なんか三角関数とか使うんかいなー?」とか考えてしまい、なかなか思考がうまくまとまらない。

ではということで、サンプルから何かの法則性がないかという事で考えてみる。すると、これって、S_x + \frac{G_x - S_x}{G_y + S_y}が答えになるんじゃね?という考えに至った。しかし、実装してみるとサンプル1と2がOKで3がNGになってしまい、そもそも考え方が全然違うということを思い知らされる。

そんなこんなで30分以上この問題に費やしてしまい、このままでは1完の終わりになってしまうということで、いったんこの問題をスキップしてC問題に向かいました。

 

で、CとDをなんとかACしてから改めてこの問題を検討してみると、x座標がG_x -S_x分動くときに、y座標がS_y + G_y分動くということから、x座標は、S_xG_xの間をS_yG_yの比率で案分したらOKなんじゃね?ということで実装してみたら、やっとこさACが取れましたとさ。終了ギリの7分前の出来事でした。

C問題

C - Travel

 Nの最大値が8と小さいので、DFSですべてのパターンを探索するコードを組んだ。テンプレート的なものがなく、イチから組んだので結構時間がとられたものの、なんとか一発AC。

D問題

D - Water Heater

 いもす法を使って累積和をとり、あとはそれぞれ供給できる湯量と比較するだけ。

なんとか一読で解法が思いつく問題でよかった。なんとか実装も間に合い一発AC。

E問題

E - Queen on Grid

問題を一読して、DPを使ってなんとかできそうという感じはあったが、如何せん残り20分程度しかなかったので、飛ばしてたB問題に着手することに。この問題は致し方なく諦めて、コンテスト後にACすることにしました。

F問題

F - Confluence

一読しましたが、コンテスト中はここまで解く余裕がなかったので、早々に退散。

コンテスト後に確認したら、なんとか実装がメンドそうだがノーヒントでいけそうな感じがあるので、解説なしACをしようかというところです。

これまでの実績

前回入緑したばかりなのに、いきなり茶落ちのピンチ!

次回はなんとか良い結果を残さねば。

コンテスト実績

コンテスト実績

総括

今回は全体的に難易度が低めだったようですが、Bで結構やらかしてしまい、それが後々まで尾を引いてしまいました。やはり、まだまだ問題を解く数がこなせていないのが原因だと思います。

今後は意識して精進の時間を作るように努力します。

また、次回も頑張ります。

AtCoder Beginner Contest 182 参加記

2020/11/8に開催されたAtCoder Beginner Contest 182に参加しました。

atcoder.jp

最近レートの上昇傾向が続いており、そろそろ入緑が見えているところです。

今回も4完以上であれば最悪レート下げが無いかなぐらいの気持ちで臨みました。

今回の結果

で、今回は個人的には上出来の5完達成!

ABC182結果

ABC182結果

そして、レートの方は大幅上昇。念願の入緑を達成できました!

振り返り

序盤で少しつまづきましたが、なんとかギリ5完達成しました。

ABC182提出結果

ABC182提出結果

A問題

A - twiblr

2 \times A + 100 - Bを計算すればOK。

問題なくAC。

B問題

B - Almost GCD

A_i \le 1000のため、2〜1000それぞれについてGCD度の数を求めて、それらの最大値を出せばOK。

の、、はずだったんですが、実戦では、こんなに愚直だとTLEするかもという疑念が頭をよぎり、なんとか効率化できないかというところを検討することに。

 

で、A_iの最大値の平方根を限度に計算してみたら、これがWA。。

 

じゃ、A_iを2で割った数を限度に計算してみたら、これがまたWA。。

 

 結局、素直にA_iの最大値を限度に計算して、やっとこさACが取れましたとさ。

C問題

C - To 3

「3の倍数 条件」でググってみたら、どうも各位の数字の和が3の倍数であればOKとのこと。ということで、以下の解法で実装してみることに。

  • 各位の数字の和Sを計算する。それが3の倍数なら、0が答え。
  • Sを3で割った余りが1の時、1,4,7のいずれかがNにあれば、それを引くと3の倍数になるので1が答え。そうでない場合、2,5,8のいずれかがNに合計2つあれば、2が答えになる。
  • Sを3で割った余りが2の時も同じ要領。2,5,8のいずれかがNにあれば、1が答え。1,4,7のいずれかがNに合計2つあれば、2が答え
  • これに該当しない場合は-1が答え

という要領で解いたらAC取れました。

 因みに、コンテスト後のTLをみると、bit全探索というキーワードが結構でてたんですが、その発想には至りませんでした。

D問題

D - Wandering

これは、愚直に計算するとTLEになるやつ。累積和を使って工夫をしていく。

サイズNの配列を2つ用意し、それぞれA_1 ~ A_iまで動いたときに

  • 最終的に正の方向にどれだけ動いたか。
  • 途中で、最大正の方向にどれだけ動いたか。

という結果をあらかじめ計算しておく。あとは上手い具合に計算してACが取れました。

E問題

E - Akari

 残り30分ぐらいで臨んだこの問題。

問題を一読して思いついた解法。とりあえずH \times Wサイズの2次元マップを作って、そこに電球とブロックを配置。あとは横方向を左右に、縦方向を上下に走査して、光を伝播させる要領でやればOK。

あとは実装してAC。と、、おもったが、なぜかサンプルが通らない。

とりあえずソースを見てみると、横に伝播した明かりが後で下にも伝播する下手くそ実装でバグっていたことが発覚。

もう残り時間も10分切ったぐらいでこの有様。惜しいとこまで行ってるのでなんとかならんかと知恵を絞ってみたら、縦方向に走査する用のマップと横方向に走査する用のマップを作って後で合算すりゃいいんじゃねということに気付く。

あとは時間に追い立てられながら、なんとか実装完了して、投げてみたら一発ACとなりましたーヾ(´∀`)ノワーイ

終了3分を切ってのAC。喜びもひとしおです。

F問題

F - Valid payments

問題は一読しましたが、解法がまったく思いつかないので早々に諦めでした。 

これまでの実績 

念願の入緑。AtCoder始めてから半年弱でやっとこさここまでたどり着くことができました。

コンテスト実績

コンテスト実績

総括

今の自分の実力だと、ABCクラスのコンテストでは全完は厳しいが、5完は現実的な目標になるかなという印象が抱けるようにはなりました。

今回は久々の5完でしたが、今後のABCは安定して5完程度の結果が残せるように精進していこうと思います。

また、次回も頑張ります。

AtCoder Beginner Contest 181 参加記

2020/11/1に開催されたAtCoder Regular Contest 181に参加しました。

atcoder.jp

ここ最近のコンテストでは緑パフォの連続で順調にレーティングも上がってきてます。今回もなんとか4完ぐらいできればレート上昇するだろうという感覚で臨みました。

今回の結果

で、今回もノルマ通りというか、いつもの4完で終了でしたー。

ABC181結果

ABC181結果

それでも、安定の緑パフォだったのでレートは少し上昇。着々と入緑に向かっています。

振り返り

もう少しで5完までいけそうでしたが、力及ばずでしたー。

ABC181提出結果

ABC181提出結果

A問題

A - Heavy Rotation

 Nが奇数なら'Black'、偶数なら'White'を出力するだけ。

問題なくAC。

B問題

B - Trapezoid Sum

 与えられるA_i,B_iについて、等差数列の和の公式を使って合計値を算出するだけ。これも問題なくAC。

C問題

C - Collinearity

 「競技プログラミング 同一直線上」でググってみた。

すると、A,B,Cの3点があり、ABの傾きとACの傾きが同じだったら同一直線上、というやり方をすればよいと書いてたので、そのまま実装しました。

ということで、これも難なくAC。

D問題

D - Hachi

 「8の倍数判定法」でググってみた。

すると、下3桁が8の倍数だったらOK的な解説があったので、とりあえず8の倍数で3桁且つ’0’を含まない整数を羅列しておき、その後数字列Sが8の倍数の3桁の数字いずれかを作成できるかを判定させるという方式で実装しました。

実装に少し時間がかかったものの、何とかAC。

E問題

E - Transformable Teacher

根拠はないが、とりあえずペアの身長の差の絶対値の和を最小化するには、身長順でソートしたあと隣同士でペアを組ませればいいんじゃねという発想に至る。

あとは先生の身長のパターンがM個あるので、そのそれぞれについて、前述の考え方で計算した結果の最小値を求めればOKと思われる。

さらに、1回1回これを愚直に計算すると計算量が大きくなり、TLEの恐れもあることから、累積和を使って効率化すれば完璧。

ということで実装に入ったのですが、なかなか上手い実装方法が思いつかず、さらに時間も切迫していることで焦ってしまい結局うまくまとめることができずで、結局時間切れ負けを喫してしまいました。

 解説だけ確認すると、考え方自体はあってたみたいなので、あとは実装力が不足していたということでした。

F問題

F - Silver Woods

一読して解法が思い浮かばすなので早々に諦めでした。

これまでの実績

安定の緑パフォが継続しており、レーティングも7回連続上昇となりました。

コンテスト実績

コンテスト実績

総括

今回ぐらいの難易度だと5完は達成したかったなーという印象ですが、如何せん実装力がまだ追い付いていないのが問題かと思います。

今後数をこなして強化していきたいというところです。

また、次回も頑張ります。

AtCoder Regular Contest 107 参加記

2020/10/31に開催されたAtCoder Regular Contest 107に参加しました。

atcoder.jp

ARCは過去3回参加して全て2完終了なので、そろそろ3完以上を達成したいなーという気持ちで臨みました。

今回の結果

で、結局今回も2完で終了となりました。

ARC107結果

ARC107結果

今回は、手応えからしてレートマイナスもありうるかなーという感じでしたが、なんとかHighest更新です。

振り返り

Bで時間かけすぎ。C以降は歯がたたずでした。

ARC107提出結果

ARC107提出結果

A問題

A - Simple Math

\sum_{a=1}^A\sum_{b=1}^B\sum_{c=1}^C abcを計算する問題。

式通りに愚直に計算するとTLEするやつだが、式変形すれば、

\sum_{a=1}^Aa \times\sum_{b=1}^Bb \times \sum_{c=1}^Ccとなるので、簡単な等差数列の和を求める公式を当てはめればOK。

あとはmodの計算を実装してAC。 

B問題

B - Quadruple

整数N,Kが与えられた時、以下の条件を満たすa,b,c,dの組の個数を求める問題。

  • 1 \le a,b,c,d \le N
  • a + b - c - d = K

2番目の式を(a + b) - (c + d) = Kと変形する。

また、f(x) := a + b = x且つ1 \le a,b \le Nを満たす整数a,bの組の個数と定義すると、求める答えは、

\sum_{x=K+2}^{2N} (f(x) \times f(x - K))

となる。ということで、あとはf(x)の関数の実装さえ適切に行えばOKのはずだったが、効率悪い実装をしたため、一度TLEを喰らってしまいました。

再度実装を見直してなんとかAC。

 

と、なんか簡単そうに書いてるが、本番では大分考察と実装に苦労しており、開始から60分経っての2完達成でした。

C問題

C - Shuffle Permutation

で、C以降は全然わからず。

 

まー問題の意味はなんとなくわかるが、どーやったら数え上げれらるん?という感じで思考がまとまらずでした。

D問題

D - Number of Multisets

1を最大限使えるだけ使った時の場合の数を数え上げ、あとは1を使う個数を1つずつ減らしていく感じのDPかという思いつきはありましたが、如何せん実装できずで諦め。

E問題

E - Mex Mat

問題すら見れてません。

F問題

F - Sum of Abs

Eと同じです。

これまでの実績

一応6連続でレート上昇ですが、そろそろ天井が見えてきた感があります。実力の方が上がっていかないと、これ以上は厳しいという印象です。

コンテスト実績

コンテスト実績

総括

ARCの参加は4回目ですが、全てABの2完止まりなのはいただけません。いつかは3完以上できるように直近のARCのC問題を中心に精進していきたいと思います。

また、次回も頑張ります。

AtCoder Regular Contest 106 参加記

2020/10/24に開催されたAtCoder Regular Contest 106に参加しました。

atcoder.jp

現在の自分の実力だと、ABCが3~4完、AGCが1完、ARCが2完ぐらいかな、というあまり根拠のない相場感で捉えてます。今回ARCなんで、とりあえず2完を目指します。

今回の結果

で、今回もノルマどおりの2完で終了です。

ARC106結果

ARC106結果

前回同様緑パフォだったので、レートはそこそこ上がってHighest更新です。

振り返り

Bで結構やらかしました。

ARC106提出結果

ARC106提出結果

A問題

A - 106

整数Nが与えられる。3^a+5^b=Nとなるa,bの組を出力する問題。

一目むずそうだったので、今日は1完も厳しいかと思いそうになったが、結局a,bを1から総当たりで探していけばいいやということで解決。

結局開始から10分以上立ってAC。

B問題

B - Values

これも一瞬訳がわからんかったが、 与えられたグラフをUnion-Findに突っ込んでから、各連結成分の各頂点が指す配列Aの要素の和が同じく配列Bの和と等しければYesという解法で行くことにした。

 

で、実装はしてサンプルが通ったので、投げてみたらこれがWA。。

 

オーバーフローなのか、もしかすると元から解法が間違ってるのかと大分悩んだが、調べてみると、結局条件判定でYesを出力すべきところが、まるっと抜けてたことが判明w

で、直してみるとまたバグを仕込んでおり、WAを喰らってしまったりで、都合4回目のSubmitでやっとこさACがとれましたとさ。

C問題

C - Solutions

 問題は見ましたが、ちょっと良い解法がすぐに思いつかなかったので、とりあえずDに浮気してみました。ということで、この問題は早々に諦め。

D問題

D - Powers

なんかシグマのシグマを計算する問題。

愚直で通れば問題ないが、多分計算の効率化をしないといけないという感じの問題。

とりあえず、思いつく限りの方法は試して、サンプルは通るところまでは実装できたが、実際投げてみたらTLE喰らいました。。

結局、もう少し工夫したらイケそうかな?という感覚だったので、終了ギリまで色々試行錯誤して粘ってみましたが、結局TLEは直らずでタイムアップ終了でしたー。

あとで、この問題が青diff後半ぐらいの難易度と判明。。こんなことなら、C問題もっと粘っとくんだったなーと後悔しました。

E問題

E - Medals

問題見れてません。

F問題

F - Figures

Eと同じで、問題見れてません。

これまでの実績

ここ数回はいい感じの右肩上がりグラフがつくれました。とりあえず、入緑が現実的なところまで見えてきてます。

コンテスト実績

コンテスト実績

総括

C以降解けなかったことは仕方ないですが、Bのミスはいただけません。

最近小ミスが多いので、気をつけたいと思います。

ということで、また、次回も頑張ります。