2022-08-07

LINE Verda プログラミングコンテスト(AtCoder Beginner Contest 263)参加記

2022/8/6に開催された、LINE Verda プログラミングコンテスト(AtCoder Beginner Contest 263)に参加しました。

前回は、ギリギリ水パフォを確保できたものの、小ミスが続くなど反省点がたくさんあった回でした。

今回のABCは、なんとか前回の反省点をクリアして、最低水パフォは出そうという感じで臨むこととしました。

Rated参加します。前回に引き続き水パフォを出せるように頑張ります✊

LINE Verda プログラミングコンテスト（AtCoder Beginner Contest 263） - AtCoder https://t.co/TzcAQuoxD1
— devgenjin77 (@devgenjin77) 2022年8月6日

今回の結果

で、今回は4完という、可も無く不可も無くといった内容で終了しました。

肝心のパフォーマンスは、なんとか現レートの少し上まで出てくれまして、なんとかレート上昇。とりあえず勝ちという結果になりました。

ギリ勝ちました😂
来週も頑張ります✊
devgenjin77さんのLINE Verda プログラミングコンテスト（AtCoder Beginner Contest 263）での成績：2041位
パフォーマンス：1073相当
レーティング：1054→1056 (+2) :)#AtCoder #LINEVerdaプログラミングコンテスト（ABC263） https://t.co/py12m3D7qK
— devgenjin77 (@devgenjin77) 2022年8月6日

振り返り

しょうもないミスをする癖は未だ治らずで、結局パフォーマンスを下げてしまいました。

A問題

A - Full House

フルハウスが成立する条件ということで、数字は2種類の筈。とりあえず出現した5つの数字をSetに突っ込んで、サイズが2ならYesとかいう実装で出してみる。

が、、これはあえなくWA。。。よくよく考えると、フォーカードの時もサイズが2になるやないかい！

ということで、各数字の出現回数を一度カウントして、3個出現の数字と2個出現の数字が両方ある場合のみYesとする実装で出す。これでなんとかACが取れました。

4分57秒1ペナで1完。今週もまた、しょうもないミスをしました。。

提出コード

https://atcoder.jp/contests/abc263/submissions/33805454

B問題

B - Ancestor

人 $N$ から始めて、 $P$ の情報を元に先祖を辿っていき、最終的に、人 $1$ に到達するまで何回掛かるかをカウントする。

最終的に、人 $1$ に到達しないケースなどあるかと考えてみたが、他に方法も浮かばすなので、この実装で提出。なんとかACが取れました。

9分28秒1ペナで2完。

提出コード

https://atcoder.jp/contests/abc263/submissions/33810231

C問題

C - Monotonically Increasing

とりあえず、DFSで探索し、出力していく実装で解いてみる。

この手のDFSは、結構久々の実装なので、少し手間取りましたが、なんとか提出してACが取れました。

23分51秒1ペナで3完。

提出コード

https://atcoder.jp/contests/abc263/submissions/33819373

D問題

D - Left Right Operation

厳密な証明はできていないが、 $L$ で置き換える処理と、 $R$ で置き換える処理は、それぞれ独立に考えられると思った。

ということで、まず、 $x$ を $0$ から $N$ まで試し、合計が最小となる状態を探索。整数列 $A$ も合計が最小となる状態で更新しておく。

次に、更新された $A$ に対して、 $y$ を $N$ から $0$ まで試し、合計が最小となる状態を探索。ここで計算された最小値を答えとする。

以上の実装でサンプルが通ったので、提出したらWA。。なにか考慮漏れでもあるのだろうか。。。

何がダメだったか、よくわからなかったが、考え方を切り替えて以下のDPを組み立ててみる。

$\ dpl\lbrack i\rbrack :=$ $x \le i$ の時、元の合計値との差の最小値。
$\ dpr\lbrack i\rbrack :=$ $y \ge i$ の時、元の合計値との差の最小値。

これらを前計算で求めて $dpl \lbrack i \rbrack + dpr \lbrack i + 1 \rbrack$ の最小値を計算。元の合計値に足すことで答えとする。

この実装で、なんとかACを取り切ることができました。

79分24秒3ペナで4完。順位的には2000位前後まで来たので、なんとか負けは回避したかと。

提出コード

https://atcoder.jp/contests/abc263/submissions/33835461

E問題

E - Sugoroku 3

問題を一読して、これと似たような問題をどっかでみたような気がしたが、思い出せず。

また、ぶっちゃけ期待値の計算方法などは少しやった記憶があるが、自分の手に馴染んでいないようで、どのように計算すれば良いのかがよく分からん。

ということで、この問題は早々に諦め。

F問題

F - Tournament

ワンチャンあるかと、問題を見てみましたがよく分からず。

G問題

G - Erasing Prime Pairs

問題すら見れておりません。

Ex問題

Ex - Intersection 2

問題すら見れておりません。

これまでの実績

レートは微増するも、水色へはまだ遠い状態が続いております。

総括

A問題のしょうもないペナルティと、Dに時間かけすぎなのが、今回の残念ポイント。やはりまだ精進が不足しているようですね。

来週は、盆休みで時間も結構取れるので、次回に備えて精進していこうと思います。

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

2022-08-03

第三回日本最強プログラマー学生選手権-予選-（ABC262）参加記

AtCoder 競プロ ABC

2022/7/31に開催された、第三回日本最強プログラマー学生選手権-予選-（ABC262）に参加しました。

atcoder.jp

昨日のARCは所用で出れず。よって今週はこのABCのみでレートが動くということになるので、今回はなんとしてもレートを上げていきたいところ。

とりあえず、目標水パフォで臨むこととしました。

Rated参加します。今回こそ水パフォ取れるように頑張ります✊
第三回日本最強プログラマー学生選手権-予選-（ABC262） - AtCoder https://t.co/ESgLGu8U4u
— devgenjin77 (@devgenjin77) 2022年7月31日

今回の結果

なんとか4完を確保しました。

で、なんとかギリギリでしたが、宣言通り水パフォを取得することが出来、レートを上げることに成功しました。

4完水パフォで上げ！来週も頑張ります✊
devgenjin77さんの第三回日本最強プログラマー学生選手権-予選-（ABC262）での成績：1572位
パフォーマンス：1211相当
レーティング：1035→1054 (+19) :)#AtCoder #第三回日本最強プログラマー学生選手権-予選-（ABC262） https://t.co/aFuszG5ZiN
— devgenjin77 (@devgenjin77) 2022年7月31日

振り返り

凡ミスでペナルティを重ねてしまい、大分パフォーマンスを落としてしまいました。

A問題

A - World Cup

めっちゃ効率的な解き方があるかもしれないかと思ったが、とりあえず早く解くために愚直に実装することに。

$Y$ の $mod 4$ をとって、あとは普通に場合分けをする実装を行い、提出。問題なくACが取れました。

2分7秒で1完。

提出コード

https://atcoder.jp/contests/abc262/submissions/33658725

B問題

B - Triangle (Easier)

グラフ上の連結を隣接リストで扱い、あとは3重ループでカウントしていけば良い。

実装方針は早めに固まったため、問題なくACを取り切ることができました。

6分14秒で2完。

提出コード

https://atcoder.jp/contests/abc262/submissions/33663510

C問題

C - Min Max Pair

$i$ を左から順に固定して考えていくとして、 $a_i = i$ の場合は、それより右に存在する $a_j = j$ となる $j$ が対象となる。

よって、前計算で、 $i = a_i$ となる項をあらかじめカウントして累積和をとっておき、計算することで対処する。

$a_i \ne i$ の場合は、 $a_{a_i} = i$ かどうかを判定し、Trueならカウントにプラス1する。

上記のような感じで、問題なくサンプルが通ったので提出したら、結果はWA。。。

原因が全く分からずで、10分近くあれこれ悩みましたが、結局カウント用の変数宣言をintからlongに変えてみることで、AC。。。

29分17秒1ペナで3完。もう2年近く競プロやっているが、こんな凡ミスがまだ治らないのかと、少しショックを受けました。。

提出コード

https://atcoder.jp/contests/abc262/submissions/33673610

D問題

D - Jumping Takahashi 2

大分難易度が高そうだが、modの合計を管理してDPすることで、なんとかやっていけそうな感じがする問題。

ということで、 $A$ の項を何個選ぶかというのを固定して、以下のDPを考えてみる。

$\ dp\lbrack i\rbrack \lbrack j \rbrack :=$ $M$ 個選ぶ時、 $A$ の項を $i$ 個採用して、 $mod M$ が $j$ になる時の通り数。

このDPを、 $M =2$ から $N$ のケースでそれぞれ実行していく。

あとは、各DPで、 $A$ から取得した値を選ぶかどうかや、最初の一つ目として選ぶ場合の遷移を実装。とりあえずサンプルまでは通るプログラムができました。

で、ジャッジに投げてみると、半分以上がWA。。。

本気で何が間違っているのかが全然分からずで、あれこれ試行錯誤してみるも、WAが取れずで傷口を広げるばかり。

で、ふと問題文をじっくり読んでみると、 $998244353$ で割った余りが答えになるやつだと今更気づく！

んで、 $mod$ の計算をまじめにやってみたら、無事ACを取ることが出来ましたとさ。。

C問題の凡ミスもショックでしたが、これは問題文をちゃんと読めば防げるミスなので、ショックを通り越して自分でも呆れてしまいました。。

84分20秒4ペナで4完。とりあえず、順位は1400台に乗ったので、なんとかレート上昇は望めそうなのが、せめてもの救い。

提出コード

https://atcoder.jp/contests/abc262/submissions/33685786

E問題

E - Red and Blue Graph

順位表のAC数をみると、多分青パフォぐらいの難易度かと。

問題文を一読しましたが、何も分からずで降参。このまま時間切れとなりました。

F問題

F - Erase and Rotate

問題すら見れておりません。

G問題

G - LIS with Stack

問題すら見れておりません。

Ex問題

Ex - Max Limited Sequence

問題すら見れておりません。

これまでの実績

一応、レートは上昇しましたが、ここから上に抜けるのが、しんどいんだよなあ。

総括

今回は、ギリ水パフォが取れましたが、CとDの凡ミスがなければ、もっと上のパフォーマンスが取れていたはず。実力不足というよりは、注意不足が原因でパフォーマンスを落とすのは大分勿体無い感じがしますね。

この手のミスは、以前から、ちょくちょくやらかしているのですが、どうすれば無くせるんだろうか。次回に向けて、少し考えてみたいと思います。

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

2022-07-24

AtCoder Beginner Contest 261 参加記

AtCoder 競プロ ABC

2022/7/23に開催されたAtCoder Beginner Contest 261に参加しました。

atcoder.jp

先週はARCで惨敗してABCで少し取り戻すという展開。今週はARCが無いので、なんとか今回は水パフォを取ってレートを上げれるようにという気持ちで臨むこととしました。

Rated参加します。今回は水パフォ取れるように頑張ります✊

AtCoder Beginner Contest 261 - AtCoder https://t.co/rLPDgovRFS
— devgenjin77 (@devgenjin77) 2022年7月23日

今回の結果

で、今回の結果は4完。時間は十分ありましたが、5完には到達できずでした。

これでもパフォーマンスは緑上位。水パフォは行きませんでしたが、なんとかレートを上げることはできました。

4完緑パフォでなんとかレート上げ😃
来週も頑張ります。
devgenjin77さんのAtCoder Beginner Contest 261での成績：2149位
パフォーマンス：1081相当
レーティング：1030→1035 (+5) :)#AtCoder #ABC261 https://t.co/lP8d1mFT5b
— devgenjin77 (@devgenjin77) 2022年7月23日

振り返り

E問題を解き切ることができませんでした。

A問題

A - Intersection

A問題にしては、いろんなケースを想定しないとWAを喰らってしまいそうな複雑な問題という印象。

考察した結果、左端を $max(L_1, L_2)$ 、右端を $min(R_1, R_2)$ とし、左端の座標から右端の座標の距離を求めれば解決できそうな感じ。

重複区間が無いケースを想定して実装。提出して問題なくACが取れましたとさ。

4分2秒で1完。少し時間をかけすぎかも。

提出コード

https://atcoder.jp/contests/abc261/submissions/33432347

B問題

B - Tournament Result

いわゆる、やるだけの問題。PaizaのCランクで出てきそうな感じだなあ。

2重ループを使って、勝敗表に矛盾がないかチェック。実装に少し時間がかかってしまいましたが、問題なくACを取ることができました。

9分39秒で2完。

提出コード

https://atcoder.jp/contests/abc261/submissions/33439448

C問題

C - NewFolder(1)

最近のC問題としては、少し単純な問題という印象。

Mapを使って、文字列の出現回数を管理し、2回目以降の場合は、文字列の末尾に出現回数に応じた数字をつければ良い。

こちらも、問題なくACを取ることができました。

15分22秒で3完。ここ最近のABCと比べると、大分ペースが早い方です。

提出コード

https://atcoder.jp/contests/abc261/submissions/33445497

D問題

D - Flipping and Bonus

一読して、解法が全然思いつかず。。

一瞬、今回3完で詰んだかと思いましたが、順位表をみると、やたらとAC数の増加ペースが速いので、そんなに複雑な解法では無いんだろうなという感じがする。

で、色々考察した結果、 $N=5000$ なら、 $N \times N$ の配列が作れそうで、その範囲でできるDPが構築できれば行けるだろうという結論に至る。

そこで、 $\ dp\lbrack i\rbrack \lbrack j \rbrack :=$ $i$ 回目のプレイで $j$ 回連続表が出た時に貰える最大の金額のDPを考える。

$i$ 回目のプレイでは、表を出した時に前回の連続数にプラス１した状態の金額を計算。裏を出した時には、前回のプレイで最も大きい金額を連続数が0の金額として採用する。

あとは、実装して、なんとか提出一回でACを取り切ることができました。

45分6秒で4完。これでなんとか緑パフォぐらいは確保できたかと。。

提出コード

https://atcoder.jp/contests/abc261/submissions/33461060

E問題

E - Many Operations

残りが50分以上あるので、なんとか5完以上は目指したいところだが、問題を一読した感じでは、上手い解法は思いつかず。

当初は、xor,or,andはそれぞれ順番を入れ替えても問題無いのかと思い、それぞれの演算毎に合算したものを演算に使う的なやり方を試してみたが、全然通らず。

あとは、論理演算の公式などをググってみるも、使えそうなものも無いということで、結局時間だけを浪費。。結局、このまま時間切れとなりましたとさ。

で、解説を見ると、bit毎に単独で合成関数を構築すれば解けるとのこと。本番時は全く思いつかずでした。過去に類型などあったんだろうか。。

F問題

F - Sorting Color Balls

ワンチャンあるかと、問題文を見てみましたが、何も思いつかずで撤退。

G問題

G - Replace

問題すら見れておりません。

Ex問題

Ex - Game on Graph

問題すら見れておりません。

これまでの実績

レートは微増しましたが、水色への道はまだまだ遠そうです。

総括

今回のEとFは、精進不足で解き切るまでの知識レベルに到達できていなかったという感想です。

しかし、今回もD問題クラスでも緑の下位あたりのDiffになっている点については、参加者のレベルがだんだん上がっているという印象を受けます。

このままでは、精進を重ねても、緑レートを維持するのも大変そうだなあ、という感じですが。とりあえず今回の復習をして次週に備えていきます。

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

2022-07-18

AtCoder Beginner Contest 260 参加記

AtCoder 競プロ ABC

2022/7/17に開催されたAtCoder Beginner Contest 260に参加しました。

atcoder.jp

昨日のARCでは、1完しかできずで、レートの方は大幅に下げることに。。

ということで、今日のABCでは、なんとか昨日の負けを少しでも取り戻そうという気持ちで臨むこととしました。

Rated参加します。
昨日の負けを少しでも取り戻せるよう、頑張ります✊✊

AtCoder Beginner Contest 260 - AtCoder https://t.co/s6e1GKbBy4
— devgenjin77 (@devgenjin77) 2022年7月17日

今回の結果

で、今回はなんとか4完を確保することができました。

肝心のパフォーマンスは、緑上位。なんとか昨日の負けを半分以上取り戻すことができましたとさ。

4完緑パフォで、なんとか昨日の負けを少し取り戻しました😄
来週も頑張ります。
devgenjin77さんのAtCoder Beginner Contest 260での成績：1788位
パフォーマンス：1169相当
レーティング：1013→1030 (+17) :)#AtCoder #ABC260 https://t.co/SS2MqpCdC9
— devgenjin77 (@devgenjin77) 2022年7月17日

振り返り

今回は、B問題に少し手こずってしまいました。

A問題

A - A Unique Letter

少し工夫ができないか考えたものの、上手いやりかたが思いつかないので、愚直に解くことに。

文字列中に現れた文字と、その出現回数をMapで管理し、最終的に出現回数が1の文字を出力。なければ-1を出力という感じで実装。

提出して、問題なくACが取れました。

3分24秒で1完。最近、A問題を解くのに少し時間をかけすぎの感があります。

提出コード

https://atcoder.jp/contests/abc260/submissions/33293963

B問題

B - Better Students Are Needed!

与えられたデータをいろんな要素でソートする感じの問題。

Javaでソート順を決めるには、Comparatorのメソッドを実装するなど、結構実装がめんどくさかったりするんだが、それを3回もやるのは超めんどくさい。

しかも、ソート順を決める方法も、結構忘れていたので、まずは実装方法をググるところから始めることに。

ということで、実装自体に大幅に手間取ってしまいましたが、やるべきことは問題文のとおり実装するだけなので、なんとか完成にこぎつけてACを取ることができましたとさ。

25分59秒で2完。ちょっと、この問題は復習して、もう少し効率が良いやり方などなかったを調査してみたいところです。

提出コード

https://atcoder.jp/contests/abc260/submissions/33303737

C問題

C - Changing Jewels

見た目の制約は緩めなので、再帰を使って解ければいいかなという印象の問題。

しかし、どうにも関数の実装方法が思いつかずなので、どうにかして解ける方法を模索することに。

しばし検討した結果、Queueに宝石の色とレベルと個数を管理したクラスを突っ込み、あとは、Queueの先頭から取得した宝石の色に応じて、変換できる宝石の色とレベルと数をQueueに突っ込むという実装をすることに。

処理時間が少し気がかりでしたが、問題なかったようで、無事ACが取れましたとさ。

44分44秒で3完。少し取り戻した感があります。

提出コード

https://atcoder.jp/contests/abc260/submissions/33308912

D問題

D - Draw Your Cards

当初の印象としては、愚直にシミュレーションするか、またはグラフっぽく捉える事で解ける問題なのかどっちなんだろうという印象。

とりあえず、場に見えてるカードのうち、特定の数字より大きい最小の数字を取るためのデータ構造が必要となるが、これはTreeSetを活用すればなんとかなる。

あとは、カードを重ねた時に、何枚になっているかと、重なっているカードの数字を管理する必要があるが、一旦グラフの隣接リストの要領で、山の一番上のカードの数字に対して、山の下にいるカードの数字を連結させることで管理する方法を試してみる。

で、一旦この実装でサンプルが通ったので、提出してみたらなんとこれがTLE。。

改めて考え直してみたところ、カードの山を連結成分として捉えることで効率化できるのではないかということで、Union-Findを使うやりかたを実装することに。

これが見事にハマってくれたようで、なんとかACを取りきることができましたとさ。

80分58秒1ペナで4完。これでなんとか負けを回避できたかと。。

提出コード

https://atcoder.jp/contests/abc260/submissions/33316373

E問題

E - At Least One

残り20分程度あるので、一応問題を読んでみましたが、なにも解法が浮かばず。ここで時間切れとなりました。

F問題

F - Find 4-cycle

問題すら見れておりません。

G問題

G - Scalene Triangle Area

問題すら見れておりません。

Ex問題

Ex - Colorfulness

問題すら見れておりません。

これまでの実績

昨日の負けを少し取り戻しました。それにしても停滞モードが長い。。

総括

今回は、B問題とD問題で結構な時間がとられたので、水パフォを逃したかという印象。

同じ4完の人でも、早めに解けてる人が水色コーダーなどになっているようなので、難しい問題を解く練習はともかく、前半の問題を速く解く練習にも力を入れていかないといけないな、という感想です。

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

2022-07-17

AtCoder Regular Contest 144 参加記

AtCoder 競プロ ARC

2022/7/16に開催されたAtCoder Regular Contest 144に参加しました。

atcoder.jp

ここ最近のコンテストでは、レートが上がったり下がったりで、停滞ムードが漂っている状況。

とりあえず、今回のARCは、Bが400点問題ということで、2完できればなんとかレートが上がるかなという感じだったので、2完を目標として挑むこととしました。

Rated参加します。とりあえず2完以上目指して頑張ります✊

AtCoder Regular Contest 144 - AtCoder https://t.co/1A3xaDqWjb
— devgenjin77 (@devgenjin77) 2022年7月16日

今回の結果

で、結果としては、1完で終了という悲しい結果に。。

パフォーマンスは緑にすら届かずで、レートは大幅に下げてしまうことになりましたとさ。

1完で冷え😢
また、次回頑張ります。
devgenjin77さんのAtCoder Regular Contest 144での成績：2443位
パフォーマンス：792相当
レーティング：1036→1013 (-23) :(#AtCoder #ARC144 https://t.co/MpQfRfHQPI
— devgenjin77 (@devgenjin77) 2022年7月16日

振り返り

B問題が二分探索だということに、まったく気がつきませんでした。

A問題

A - Digit Sum of 2x

最初のうちは、よくわからずだったが、サンプルの解答を見ると、ある程度の法則性が掴めてきた。

$f(x) = N$ の時、 $f(2x) = M$ となる $M$ を最大化する時、 $x$ に $5$ 以上の数字が含まれていると必ず損をしてしまうので、 $x$ には4以下の数字だけを含むようにする。
上記のような $x$ を最小化するには、下位の桁をできるだけ　 $4$ で埋めるようにすれば良い。

ということで、 $M=2N$ とし、 $x$ は、題の条件を満たし且つ、できるだけ $4$ を下位に埋めた数字とすることに。

あとは実装して提出したら、なんとか一発でACが取れてくれましたとさ。

16分55秒で1完。順位表をみたら、この時点でA問題のACが1000以上付いてたので、少し時間使いすぎかと反省しました。

提出コード

https://atcoder.jp/contests/arc144/submissions/33261534

B問題

B - Gift Tax

サンプルデータから検討してみると、整数列 $A$ の最小値に $a$ を足し、最大値に $b$ を引くことを繰り返し、操作後の $min(A)$ を求めるのが正当なように見える。

ということで、実装方法を色々考えてみるが、セグ木を使ったやりかたでは実装は無理そう。

ならばと、最大値と最小値を管理する優先度付きキューを使うことでなんとかなるかと実装してみるが、これは上手くいかず。。

残り時間はたくさんありましたが、いかんせん実装方法は思いつかずで、このまま時間切れとなりましたとさ。

で、コンテスト後に解説をみると、二分探索を使うのが正解とのこと。本番中は全く思いつかずだったので、この点は反省したいです。

C問題

C - K Derangement

一応、少し問題を見たものの何もわからず。

D問題

D - AND OR Equation

問題すら見ておりません。

E問題

E - GCD of Path Weights

問題すら見ておりません。

F問題

F - Arithmetic Sequence Nim

問題すら見ておりません。

これまでの実績

今回は、大幅な下げ。レート3桁台も見えてきてしまいました。

総括

B問題が二分探索と気づけなかったのが、一番の反省点。このぐらいの典型が思いつかないようでは、まだまだ勉強不足ですね。

とりあえず、日曜のABCではレートを落とさないように頑張るのみです。

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

2022-07-13

AtCoder Beginner Contest 259 参加記

AtCoder 競プロ ABC

2022/7/9に開催されたAtCoder Beginner Contest 259に参加しました。

atcoder.jp

先週のABCでは、水色パフォを出すことが出来、下がり気味だったレートも少し戻すことができました。

今回は、その流れに乗れるようにということで、水色パフォーマンスを出すことを目標として挑むことにしました。

Rated参加します。今回も水パフォ目指して頑張ります✊

AtCoder Beginner Contest 259 - AtCoder https://t.co/w74mYFYcU8
— devgenjin77 (@devgenjin77) 2022年7月9日

今回の結果

しかしながら、今回は3完止まりという残念な結果となりました。。。

茶パフォで暴落かと覚悟しましたが、なんとか緑パフォの下位辺りで勘弁してくれたようで、レートの方は少し下がるという結果となりました。

3完緑パフォで負け😢
まあ、傷は浅かった方かと。。
devgenjin77さんのAtCoder Beginner Contest 259での成績：2862位
パフォーマンス：911相当
レーティング：1049→1036 (-13) :(#AtCoder #ABC259 https://t.co/epUPCJbPrp
— devgenjin77 (@devgenjin77) 2022年7月9日

振り返り

Dでバグりちらかしてしまいました。

A問題

A - Growth Record

変数が5個もあり、なんか条件分岐が複雑そうな問題。題意を読み解いて整理するのが大変でした。

まとめてみると、 $\ X - M \gt 0$ の場合は、 $\ T - ( D \times (X - M))$ が答え。それ以外の場合は、 $T$ を答えとして出力すれば良い。

実装に少し手間取りながらもなんとかACを取り切ることができました。

7分5秒で1完。A問題にしては、だいぶ時間が取られてしまいました。

提出コード

https://atcoder.jp/contests/abc259/submissions/33077040

B問題

B - Counterclockwise Rotation

三角関数を駆使するんだろうなーという感じの問題。

とりあえず、原点から、 $(a, b)$ への距離を求め、 $cos(d)$ と $sin(d)$ にそれぞれ掛けた値を求めてみるが、違うっぽい。

ということで、原点から、 $(a, b)$ を見た時の角度も考慮に入れないとダメっぽいので、仰角を求める方法などをググってみる。

そして、三角関数に入れるラジアンに、先ほど求めた仰角を足してみたところ、サンプルが通ってくれたっぽいので、そのまま提出。なんとか、ACが取れましたとさ。

24分43秒で2完。今までのABCとは違い、だいぶ苦戦しております。

提出コード

https://atcoder.jp/contests/abc259/submissions/33087987

C問題

C - XX to XXX

$S, T$ をそれぞれ連長圧縮することで、なんとかなりそうな問題。

とはいえ、ライブラリ的なものはないので、とりあえず実装。

あとは、 $S, T$ をそれぞれ連長圧縮した後、文字の並びと数が合っているか。その次に片方の文字長が1の場合は、他方の文字長が1か。1でない場合は、 $T$ の方が大きいかを判別。

多少、実装が長くなったものの、なんとか一度の提出でACを取り切ることができましたとさ。

36分55秒で3完。少し取り戻した感があります。

提出コード

https://atcoder.jp/contests/abc259/submissions/33094321

D問題

D - Circumferences

読み進めてみると、各円をグラフの頂点とみなし、スタート地点に接している円と、ゴール地点に接している円が同じ連結成分に属しているかを判定する問題の様に見える。

制約から見ても、円同士の連結判定で $O(N^{2})$ 使っても大丈夫そう。

ということで、あとは、円同士が接点を持つかどうかの判定と、スタート地点とゴール地点はどの円に属するのかを判定できれば良い。

前者については、とりあえずググってみると中心点の間の距離と、円の半径を見れば判定可能な模様。

後者については、各円の中心から、スタート及びゴール地点それぞれの距離を見たときに、円の半径と一致しているかを判定すれば良い。

ということで実装してみて、サンプルまで通ったものの、なんとWA×3を喰らってしまう。。。

当初、 $N=1$ のコーナーケースがおかしいかと思ったが、それは関係無いっぽい。

円の半径と距離の判定で、途中計算でdoubleを使っている事による誤差が原因かと少し思いましたが、それを修正するには大分時間が掛かりそうなので、他の線をまず洗ってみるも、結果は芳しくない。

ということで、結局WAは取れずじまいとなりましたとさ。。

解説を見ると、考えかたは合っているみたい。なのでWAの原因は恐らくdoubleで計算したことによる誤差である模様。。こんな凡ミスで解ける問題を落としてしまい、非常に残念な気持ちです。

E問題

E - LCM on Whiteboard

ワンチャンあるかと、問題を見てみるも、なにも解法が浮かばずで、早々に諦め。

F問題

F - Select Edges

問題すら見れておりません。

G問題

G - Grid Card Game

問題すら見れておりません。

Ex問題

Ex - Yet Another Path Counting

問題すら見れておりません。

これまでの実績

上げた翌週は下げという流れが続いております。。

総括

少し前も似たような感じで、解けたはずの問題を解けなかったという事があったような気がします。

やはり、こういった取りこぼしは、無くしていきたいものですが、なかなか無くならない。こういったところを改善していくには、やはり実装経験を積んでいくことしかないかと思う次第です。

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

2022-07-03

AtCoder Beginner Contest 258 参加記

AtCoder 競プロ ABC

2022/7/2に開催されたAtCoder Beginner Contest 258に参加しました。

atcoder.jp

先週土日のABC、ARCは、思ったより結果が出ず、レートは大きく低下。今回はなんとかこの悪い流れを止めようという気持ちで臨むこととしました。

Rated参加します。ここのところ連敗しているので、今回で止められるように頑張ります✊

AtCoder Beginner Contest 258 - AtCoder https://t.co/salOSnU3zO
— devgenjin77 (@devgenjin77) 2022年7月2日

今回の結果

で、今回はなんとか4完を達成しました。

パフォーマンスは、意外と出てくれて水色に到達。なんとか連敗を止めることができました。

4完水パフォでなんとか連敗を止めることができました😂
次回も頑張ります。
devgenjin77さんのAtCoder Beginner Contest 258での成績：1678位
パフォーマンス：1253相当
レーティング：1024→1049 (+25) :)#AtCoder #ABC258 https://t.co/1fsQ8hnocX
— devgenjin77 (@devgenjin77) 2022年7月2日