2022-04-18

ユニークビジョンプログラミングコンテスト2022(AtCoder Beginner Contest 248)参加記

2022/4/16に開催された、ユニークビジョンプログラミングコンテスト2022(AtCoder Beginner Contest 248)に参加しました。

先週の土日は、ARC、ABCと2連チャンでコンテストがありましたが、なんとか連勝することができて、一時期は3桁に落ちたレートもHighest付近まで戻すことに成功しました。

今回は、この流れのまま水色になれるようにと、水色パフォを目標として臨むこととしました。

Rated参加します。
水パフォ目指して頑張ります✊
ユニークビジョンプログラミングコンテスト2022（AtCoder Beginner Contest 248） - AtCoder https://t.co/q51UZm6pO2
— devgenjin77 (@devgenjin77) 2022年4月16日

今回の結果

しかしながら、今回は4完を確保するのが精一杯でした。。

パフォーマンスは3桁しか出ておらず、今回は下げという結果になりました。

次、頑張ります😓
devgenjin77さんのユニークビジョンプログラミングコンテスト2022（AtCoder Beginner Contest 248）での成績：2439位
パフォーマンス：961相当
レーティング：1064→1054 (-10) :(#AtCoder #ユニークビジョンプログラミングコンテスト2022（ABC248） https://t.co/BvBTpwqagm
— devgenjin77 (@devgenjin77) 2022年4月16日

振り返り

D問題でだいぶ手こずってしまいました。。

A問題

A - Lacked Number

数字のみからなる文字列 $S$ より0から9までのうち一つだけ欠落している数字を求める問題。

愚直にやると手間がかかりそうなので、なんか上手い解法が無いかなー、、と考えたら、0から9までを足した時の合計 $45$ から文字列内にある数字を引いていけば答えになるのでは？というアイデアが浮かんできた！

そのまま実装してみて、問題なくAC。大体愚直に解いてみることが多いA問題でしたが、今回は上手い解法が思いついて気分良いスタートが切ることが出来ました。

1分43秒で1完。

提出コード

https://atcoder.jp/contests/abc248/submissions/31003859

B問題

B - Slimes

スライムの数が $B$ 以上になるまで、 $A$ に $K$ を掛けた回数を求めれば良い。

なおオーバーフローを避けるために、long型で取るようにしないといけない。

ということで、あとは実装をして提出。こちらも問題なくACが取れました。

3分38秒という、個人的には良好なタイムで2完。

提出コード

https://atcoder.jp/contests/abc248/submissions/31007400

C問題

C - Dice Sum

一読して手強そうな問題と思ったら、DPでやる問題でした。最近はC問題からDPが出るようになったんだね。

ということで、DP配列を以下のように定義する。

$dp \lbrack i \rbrack \lbrack j \rbrack :=$ 数列 $A$ を $i$ 番目まで決めた時に、合計が $j$ になる場合の数。

初期値は、 $dp \lbrack 0 \rbrack \lbrack 0 \rbrack = 1$ とし、 $i$ 番目の値を決めるとき、 $0 \le j \lt NM$ および $1 \le k \le M$ について、 $j + k \le NM$ の時、 $dp \lbrack i \rbrack \lbrack j + k \rbrack$ に $dp \lbrack i - 1 \rbrack \lbrack j \rbrack$ を加算する。

少しバグ取りに手間取ったりしましたが、なんとか実装に漕ぎ着け、ACを取ることができました。

25分1秒での3完。ここまでは、まあまあな内容かと。

提出コード

https://atcoder.jp/contests/abc248/submissions/31021992

D問題

D - Range Count Query

なんかセグ木でやるには難しそうな配列に対するクエリの問題。

とりあえず、 $A_i$ の上限値が限定されているので、各数値ごとに出現した位置を管理する配列を作る方法が効きそうな予感だけはした。

そこで、まずは各数値について、出現位置をTreeSetで管理し、各クエリについては、位置が $L$ 以上、 $R$ 以下のサブセットを返すような実装を行う。

が、、サンプルは通ったものの、あえなくTLEを喰らってしまう。。

今度は、各数列の位置について、 $i$ 番目の状態ではどんな数字が何回現れたかと管理するHashMapを生成すれば良いのではと考えてみたが、インスタンス生成時間が相当ネックになるらしく、これもあっさりとTLEを喰らってしまう。。

ということで、結局、各数値について出現位置を配列で管理し、開始と終了の位置を二分探索でやるしかないのかなーということで、あとはなんとか実装してみる。

これが添字ミスなどで何回かWAを喰らってしまうものの、一応TLEはしないということでなんとか諦めずにバグ取りを行い、終了5分前というところで、なんとかACを取り切ることができました！

95分2秒の5ペナでやっと4完。なんとか爆死はまぬがれた模様。。

提出コード

https://atcoder.jp/contests/abc248/submissions/31041502

E問題

E - K-colinear Line

一応問題に目を通したものの、残り5分足らずという状況ではまともな考察すら出来ず。ここで時間切れとなりました。

F問題

F - Keep Connect

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

G問題

G - GCD cost on the tree

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

H問題

Ex - Beautiful Subsequences

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

これまでの実績

上がればHighest更新というところでしたが、ここでまた足踏み状態となりました。

総括

今回はあえなく4完緑パフォという結果でしたが、もう少しD問題を早く片付けられたら現レートの維持以上ができたところだったかと。Dの実装方針について既存のライブラリの活用にこだわりすぎたあまり、無駄に時間をかける結果になったのが反省点となります。

また次回も頑張ります。

2022-04-11

AtCoder Beginner Contest 247 参加記

AtCoder 競プロ ABC

2022/4/10に開催されたAtCoder Beginner Contest 247に参加しました。

atcoder.jp

昨日のARCでは、なんとか2完を確保することができ、レートを上昇させることができました。

今日のABCでは、昨日の流れを引き継いでレート上昇につなげるべく、5完という目標を立てて臨むこととしました。

Rated参加します！とりあえず目標は5完というところで✊

AtCoder Beginner Contest 247 - AtCoder https://t.co/N08EZKJUZi
— devgenjin77 (@devgenjin77) 2022年4月10日

今回の結果

そして、今回はなんと目標通りの5完を達成することが出来ましたー！まさしく有言実行です。

久々の水色パフォーマンスも達成し、レートは大幅上昇。Highestにもう少しというところまで戻すことができましたとさ。

目標の5完達成＋水パフォで3連勝😂😂😂
来週も頑張ります✊

devgenjin77さんのAtCoder Beginner Contest 247での成績：1341位
パフォーマンス：1319相当
レーティング：1032→1064 (+32) :)#AtCoder #ABC247 https://t.co/gyu9WfEzoj
— devgenjin77 (@devgenjin77) 2022年4月10日

振り返り

前半はそこそこ順調に進み、E問題は力技で通すことに成功しました。

A問題

A - Move Right

文字列 $S$ をビット列とみなし、右に1ビットシフトした結果を出力すればよい。

とはいえ、ビット演算に落とし込むのも逆に手間がかかるという事で、”0” + $S$ の先頭3文字を出力する実装を行い、問題なくACを取る事が出来ました。

1分40秒で1完。まずまずのスタートです。

提出コード

https://atcoder.jp/contests/abc247/submissions/30847874

B問題

B - Unique Nicknames

見た目だいぶややこしそうな問題かと思いましたが、全探索が普通に通りそうな制約だったので、ゴリ押しで実装することに。

各 $i$ に対して、 $i \ne j$ となる全ての $j$ について、姓の一致( $s_i = s_j$ または、 $s_i = t_j$ )及び名の一致( $t_i = s_j$ または、 $t_i = t_j$ )をチェックし、姓、名両方について一致が一回でもあった場合、答えはNoとする。

上記の要領で実装し、なんとかACを取る事が出来ました。

11分20秒で2完。少し時間を掛けすぎたきらいがあります。

提出コード

https://atcoder.jp/contests/abc247/submissions/30856383

C問題

C - 1 2 1 3 1 2 1

再帰で実装すればよいかという考えが最初に浮かんだので、とりあえず再帰で実装しきることにしました。

で、実装後、 $N=16$ としてローカルで実行してみると、とりあえずそれっぽい出力で動くものの、多少実行速度に懸念が出てきたので、一応メモ化の処理も入れてみてから提出。とりあえず問題なくACが取れましたとさ。

でもあとでよくよく考えると、再帰を使わなくても大丈夫そうだし、だいぶ無駄な実装もしてたかなという印象。また、復習がてら書き直すことにしてみますか。

22分45秒で3完。とりあえず、大きな問題は無しというところ。

提出コード

https://atcoder.jp/contests/abc247/submissions/30864288

D問題

D - Cylinder

クエリ1の $x,c$ をペアオブジェクトでキューに突っ込んで置き、クエリ2の $c$ を使い切るまで、ペアオブジェクトをキューから取り出せばOKな感じがする。

ちなみに、後で知ったのですが、こういう手法をランレングス圧縮というんだそうな。

とりあえず、解法は見えたので、あとは実装して問題なくACすることができました。

39分41秒で4完。あと1時間あるので、目標の5完目が現実味を帯びてきました。

提出コード

https://atcoder.jp/contests/abc247/submissions/30872695

E問題

E - Max Min

問題としては、やや難解という印象だが、区間の最大、最小を考慮するというところで、とりあえずセグ木を使えばなんとかなるかと考えました。

ということで、とりあえずは区間最大、最小を計算するセグ木をそれぞれ用意します。

その後、 $L$ を固定してから、区間最大が $X$ となる $R$ の範囲及び区間最小が $Y$ となる $R$ の範囲を二分探索で求め、重複する範囲を数え上げて答えに追加する。これを全ての $L$ に対して実行するという実装を行いました。

範囲を求める二分探索の実装でだいぶ手こずってしまい、且つ最初の提出でＷＡを喰らうなどしてだいぶ焦りましたが、なんとか時間内に修正し、ACを取る事が出来ました。

89分46秒1ペナで5完。このあたりで1300位ぐらいまで上げる事ができたので、なんとかレート上昇ぐらいはあるかと一安心できました。

提出コード

https://atcoder.jp/contests/abc247/submissions/30888032

F問題

F - Cards

終了まで10分程度あった為、問題を一読することまではしましたが、何もわからず。

結局、ここで時間切れとなりました。

G問題

G - Dream Team

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

Ex問題

Ex - Rearranging Problem

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

これまでの実績

ここ最近は停滞ムードが続いておりましたが、なんとかHighest付近まで戻すことができました。

総括

今回のE問題は、あえてセグ木を使わなくても解ける問題だったようですが、上手い解法が降りてこない時に間に合わせの実装としてライブラリが使えるようになったのは一つの成長の印かと思います。

反省点としては、C問題などでは、多少複雑な実装をしてしまい、多少時間ロスをしたのが少し悔やまれます。

とりあえず、レートの方はHighest付近まで戻せたので、この勢いで水色に行けるように頑張りたいと思います。そのためには、今後、当たり前のように水パフォが取れるようにならないといけないですがね。

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

2022-04-10

AtCoder Regular Contest 138 参加記

AtCoder 競プロ ARC

2022/4/9に開催されたAtCoder Regular Contest 138に参加しました。

atcoder.jp

今回のARCコンテストはA問題から400点問題ということで、場合によっては0完してしまうかという懸念もありますが、なんとか爆死を回避すべく1完は確保したいという気持ちで臨むこととしました。

Rated参加します。とりあえず0完爆死しないように頑張ります✊

大和証券プログラミングコンテスト2022 Spring(AtCoder Regular Contest 138) - AtCoder https://t.co/2pTuhW6Zo1
— devgenjin77 (@devgenjin77) 2022年4月9日

今回の結果

で、今回は苦戦したものの、なんとか2完を確保することに成功しましたー。

肝心のパフォーマンスは、緑上位辺り。なんとかレートは上昇という結果になりましたとさ。

なんとか2完確保です😆
devgenjin77さんの大和証券プログラミングコンテスト2022 Spring(AtCoder Regular Contest 138)での成績：1428位
パフォーマンス：1198相当
レーティング：1012→1032 (+20) :)#AtCoder #大和証券プログラミングコンテスト2022Spring(ARC138) https://t.co/6vPPm10mfa
— devgenjin77 (@devgenjin77) 2022年4月9日

振り返り

Aで相当もたついてしまったのが反省点です。

A問題

A - Larger Score

解法は早めに思いつきましたが、実装に時間をかけすぎました。。

まず、入力された整数列 $A$ を、先頭 $K$ 項目までの $B$ と $K + 1$ 項以降の $C$ に分けて考える。

各 $C_j$ に対して、 $B_i \lt C_j$ となる最大の $i$ に対して、 $(j + (K - i))$ を最小化すれば答えが求まる。

最大の $i$ を探すところがネックになるが、区間最小を求めるセグ木を使って二分探索すれば良いかというところまでは早めに見通せました。

で、早速実装に取り掛かりましたが、これまでコンテスト本番でセグ木を使ってこなかったので、大分実装にもたついてしまいました。。

また、最大の $i$ を検索するところで、ac-libraryから移植してきたセグ木のmaxRightかminLeft関数が使えるかというところを検討してたら、あっというまに時間を溶かしてしまい、気づいてみたらコンテスト開始1時間経過してしまいました。。。

結局、肝心の二分探索は、自力実装をすることでとりあえず提出。なんとかA問題をACすることができ、0完爆死は回避することができましたとさ。

79分16秒という、かなり残念なタイムで1完。後で見ると、A問題のAC数が想定以上に多かったので、びっくりしました。

提出コード

https://atcoder.jp/contests/arc138/submissions/30820232

B問題

B - 01 Generation

空の数列 $x$ に対して、操作A,Bの繰り返しを行うことで、整数列 $A$ に一致させることができるかという問題。

とりあえず、整数列 $A$ の状態から、操作A,Bの逆操作を繰り返すことで、空の数列にできるかという観点で考える。

で、とりあえずざっくりと検討してみると、操作Aを行なった後は、数列 $x$ の先頭は必ず $0$ になり、操作Bを行なった後は、末尾が必ず $0$ になるということから、

$A$ の末尾が $0$ の場合、Bの逆操作として、末尾の $0$ を取り除く。
$A$ の末尾が $0$ でない場合、Aの逆操作として、先頭の $0$ を取り除いたのち、flip操作を行う。この時先頭が $0$ でない場合は答えはNoとなる。

という要領の解法を立ててみる。

あとは、flip操作を行う時に、 $A$ の要素全てをflipするのではなく、比較する値をflipすることで、高速化を図ればなんとかなるかと。

で、サンプルは通ったので、証明が完全でないながらも、とりあえず投げてみたらば、これがあっさりACが取れてくれましたとさ。

103分13秒というだいぶ微妙なタイムで2完を確保。この時点で、一応順位も1300台に乗せたので、レート下げはないかというところでホッとしました。

C問題

C - Rotate and Play Game

残り時間が20分足らずというところで、なんとか問題文を見てみましたが、解法が降りて来ずで時間切れ。。

一応、青Diffということらしいので、今週じっくりと検討してみることにします。

D問題

D - Differ by K bits

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

E問題

E - Decreasing Subsequence

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

F問題

F - KD Tree

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

これまでの実績

前回に続いての2連勝！とりあえず、この勢いを大事にしたいものです。

総括

今回は、A問題が400点ということで、だいぶ構えてしまった結果、A問題で相当時間を掛けてしまいました。

解法が見えていただけに、もう少し早く提出することもできたかという思いもあるので、少し残念な気持ちです。

まず当面の課題として、セグ木の使い方に慣れてないというところが今回時間がかかった原因というところがあるので、その辺りを中心に対策をしていこうと思います。

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

2022-04-03

AtCoder Beginner Contest 246 参加記

AtCoder 競プロ ABC

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

atcoder.jp

前回のABCはコンディションが万全でなかった事もあって、久々の茶パフォでレート暴落という回でした。

前回下げた分を少しでも取り戻すべくということで、今回は5完以上を目標に臨むこととしました。

Rated参加します。前回の茶パフォのリベンジを果たすべく、5完以上を目標に頑張ります✊

AtCoder Beginner Contest 246 - AtCoder https://t.co/p3VqsOLn9T
— devgenjin77 (@devgenjin77) 2022年4月2日

今回の結果

今回は、なんとか4完を確保というところでした。

パフォーマンスは、一応緑の上位まで出ており、なんとかレートを上げることに成功しました。

全体的に難易度が上がってた感じでしたが、なんとか4完を確保！レートも4桁復帰しました😂
来週も頑張ります✊

devgenjin77さんのAtCoder Beginner Contest 246での成績：1938位
パフォーマンス：1130相当
レーティング：998→1012 (+14) :)#AtCoder #ABC246 https://t.co/C3Yg1kbDmb
— devgenjin77 (@devgenjin77) 2022年4月2日

振り返り

前半でやたらともたついてしまいました。

A問題

A - Four Points

いきなりの図形っぽい問題。。

とりあえず、 $x_1,x_2,x_3$ のうち1度しか出ていない数値が $x$ の答え。 $y_1,y_2,y_3$ のうち1度しか出ていない数値が $y$ の答えと気づくのに3分程度要しました。

その後、出現数をまじめにカウントするのに、MapかSetを使うか悩んだりしながら、なんとか実装に漕ぎ着けてACを取ることができました。

だいぶ実装に苦労したA問題。コンテスト後、いろんな人の実装をみてると、XORを計算するシンプルな解法があったとのことで愕然としました。。

10分34秒で1完。Aで10分超えてしまうとは。。。

提出コード

https://atcoder.jp/contests/abc246/submissions/30634404

B問題

B - Get Closer

三角関数使う系の問題かと思われるB問題。数学が得意でない自分は、色々と三角関数の基本的な解説のページをググりながら、なんとか解法を見つけることができました。

結局、 $(0,0)$ と $(A,B)$ の距離 $d$ を求めて、 $(\frac{A}{d},\frac{B}{d})$ を答えとして出力することでAC。

19分49秒で2完。序盤はだいぶ立ち遅れ気味です。

提出コード

https://atcoder.jp/contests/abc246/submissions/30640738

C問題

C - Coupon

少しややこし目の計算問題。方針としては、値段の高いほうからクーポンを満額使える分を使っておき、クーポンが余ってしまったら、使えなかった端数のうち大きい金額を優先して使うようにすれば良いという感じ。

で、実装に取り組んでみると、 $K$ と $X$ の扱いが逆になってたりと色々バグらせてしまい、提出がだいぶ遅くなってしまったものの、なんとかACを取ることに成功。

47分39秒で3完。順位を見てみると、やっと3700位台というところで、このままでは再び茶パフォの危機かと冷や汗をかいておりました。。

提出コード

https://atcoder.jp/contests/abc246/submissions/30652723

D問題

D - 2-variable Function

前回同様、訳わからん方程式が出てきたという印象のD問題。

初手でどうすれば良いのかよくわからず、だいぶ手詰まり感があったのですが、 $N$ が最大の場合でも3乗根は $10^{6}$ 程度なので、 $0 \le a \le \sqrt[3]{N}$ を全探索して、 $b$ を二分探索すればなんとか行けるのではないかと想定。

ということで実装してみましたが、サンプル3がなぜか通らず。。苦し紛れに色々探索範囲をいじくり回したりして、なんとかサンプルが合うところまで漕ぎ着けたので、そのまま提出し、なんとかACを取ることができましたとさ。

90分6秒で4完。多分これでレートが落ちることはないかということで少し安心しました。

提出コード

https://atcoder.jp/contests/abc246/submissions/30667042

E問題

E - Bishop 2

残り10分足らずというところで、なんとか問題を見てみたところ、BFSでやれば解けるのではないかという印象。

しかし、実装時間があまりにもなさすぎというところで、考察をするだけで今回は時間切れ終了となりましたとさ。

F問題

F - typewriter

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

G問題

G - Game on Tree 3

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

Ex問題

Ex - 01? Queries

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

これまでの実績

再びレートを4桁に乗せることができました。次は落ちないようにしないと。。

総括

今回は二分探索を使うD問題がコンテスト中に通せたのが良かった点です。ただ、実装の正確性に欠けるところがあるので、その点は改善しないといけないなーというところ。

反省点としては、A、B、C問題でやたらと時間がかかってしまったところ。苦手な問題が多かったですが、この辺は今までのABC過去問で対策していくしかないでしょうね。

まだまた目標の水色は遠いですが、とりあえず粛々と精進を続けていこうと思います。

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

2022-03-27

AtCoder Beginner Contest 245 参加記

AtCoder 競プロ ABC

2022/3/26に開催されたAtCoder Beginner Contest 245に参加しました。

atcoder.jp

この日は仕事上の付き合いで飲み会があり、家に帰ったのが午後8時半ぐらいというところ。コンテストに参加するか微妙なコンディションでしたが、とりあえず前回の負けが取り返せれば、という思いで参加してみることにしました。目標はとりあえず5完です。

Rated参加します。飲み会後の参加で多少不安もありますが、なんとか5完はできるように頑張ります。

AtCoder Beginner Contest 245 - AtCoder https://t.co/bbGsQTAw8Y
— devgenjin77 (@devgenjin77) 2022年3月26日

今回の結果

で、今回の結果ですが、なんと3完で終了という非常に残念な結果となりましたとさ。

んで、、久しぶりに茶パフォを叩き出してしまい、レートは暴落。。再度3桁落ちという結果になりましたとさ。

3完で久々の茶パフォを叩き出してしまい、
レートは暴落😭😭3桁落ちとなりましたとさ😱

また、初心に立ち返って精進します。
devgenjin77さんのAtCoder Beginner Contest 245での成績：3693位
パフォーマンス：719相当
レーティング：1025→998 (-27) :(#AtCoder #ABC245 https://t.co/umETBQLARC
— devgenjin77 (@devgenjin77) 2022年3月26日

振り返り

Dを解き切ることすらできませんでした。

A問題

A - Good morning

アルコールが入っているせいか、A問題を読み解くのにも少し苦労しました。。

とりあえず愚直に $A$ と $B$ の時間の比較のIF文を書き、その後 $A=B$ の場合は $C$ と $D$ の分の比較をするという要領。

後で考え直せば、単位を分にまとめるなどで実装をシンプルにできたかというところでしたねー。

4分3秒で1完。今日はコーディングのスピードもイマイチです。

提出コード

https://atcoder.jp/contests/abc245/submissions/30430889

B問題

B - Mex

$A$ の全要素をSetに突っ込んだ後、0から順番に、その数字がSetにあるかどうかを見ていけば良い。

ということで、あとは実装と提出を行い、ACが取れました。

8分7秒で2完。ここまでは、まあままの結果かなという印象です。

提出コード

https://atcoder.jp/contests/abc245/submissions/30437136

C問題

C - Choose Elements

今回のCはDPの問題。ひと昔前のC問題といえば、全探索のゴリ押しでクリアできるイメージだったが、最近はDPもよく出るようになったなぁと。

で、まずはどんなDPを作ろうかということで、以下のようなDPの配列を立ててみる。

$dp\lbrack i \rbrack \lbrack 0 \rbrack :=$ 数列 $N$ の $i$ 番目として $A_i$ が採用できる場合 $True$
$dp\lbrack i \rbrack \lbrack 1 \rbrack :=$ 数列 $N$ の $i$ 番目として $B_i$ が採用できる場合 $True$

あとは、以下の要領でDP配列を埋めていく。

$dp\lbrack i \rbrack \lbrack 0 \rbrack = True$ 且つ $| A_i - A_{i+1} | \le K$ の場合、 $dp\lbrack i + 1 \rbrack \lbrack 0 \rbrack = True$
$dp\lbrack i \rbrack \lbrack 1 \rbrack = True$ 且つ $| B_i - A_{i+1} | \le K$ の場合、 $dp\lbrack i + 1 \rbrack \lbrack 0 \rbrack = True$
$dp\lbrack i \rbrack \lbrack 0 \rbrack = True$ 且つ $| A_i - B_{i+1} | \le K$ の場合、 $dp\lbrack i + 1 \rbrack \lbrack 1 \rbrack = True$
$dp\lbrack i \rbrack \lbrack 1 \rbrack = True$ 且つ $| B_i - B_{i+1} | \le K$ の場合、 $dp\lbrack i + 1 \rbrack \lbrack 1 \rbrack = True$

と、まあこんな感じの実装でACは取れたのですが、ここまでの考察に時間がとられたり、実装にもたついたりして、かなりタイムを消費してしまいました。

41分6秒で3完。この時点では、5完は厳しそうかなーという印象でした。

提出コード

https://atcoder.jp/contests/abc245/submissions/30457890

D問題

D - Polynomial division

一見して、なんか訳わからん方程式が出てきたー、という印象のD問題。

とりあえず、 $B$ の中で、一番高次の係数と、0次の係数は簡単に求まりそうだが、それ以外をどう求めるかの計算がややこしそう。。

アルコールも入っているせいか、あまり頭が回っておらず、ノートに方程式の展開を書いてみるも、考えをまとめるのにやたらと苦労する。

とりあえず、それなりの実装をしてサンプルが通ったところまでは頑張ってみたものの、結果はWAとRE (多分ゼロディバイド)のダブルパンチで通らず。。

その後も、どうすれば良いかあれこれ考えてみたものの、結局ACには至らずで時間切れとなりましたとさ。

E問題

E - Wrapping Chocolate

コンテスト中は問題すらみておらず。あと見ても解法はわからんので後で解説ACするしかないかというところ。

F問題

F - Endless Walk

コンテスト中は問題すらみておらずだったが、終了後のぞいてみると、これ強連結成分分解するやつじゃね？という印象。。

最近、強連結成分分解の典型問題を勉強していたので、もしかするとFのほうがワンチャンあったかもしれません。。。

G問題

G - Foreign Friends

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

Ex問題

Ex - Product Modulo 2

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

これまでの実績

レートは再度3桁落ち。。なかなか上抜けできないもどかしい展開が続きます。

総括

今日は、コンディションが万全でなかったということもありましたが、まだまだ計算力が足りていないなーというのを思い知らされた回でした。

とはいえ、これでへこたれていては、一生上のレートにはいけません。これに懲りずに精進を続けていこうと思います。

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

2022-03-22

AtCoder Beginner Contest 244 参加記

AtCoder 競プロ ABC

2022/3/20に開催されたAtCoder Beginner Contest 244に参加しました。

atcoder.jp

昨日のARCでは、なんとかレート上昇という結果を得ることができ、直近では2連勝という状況。

ということで、今回もレートを上げて、Highest更新を目指していくぞという気持ちで臨むこととしました。

Rated参加します。昨日のARCに続いての連勝目指して頑張ります✊
AtCoder Beginner Contest 244 - AtCoder https://t.co/j4wkpaJ0tA
— devgenjin77 (@devgenjin77) 2022年3月20日

今回の結果

で、今回の結果は、とりあえず4完で終了となりました。

しかし、順位表の状況から嫌な予感がしていた通り、パフォーマンスは伸びずで緑の下位というところ。今回はあえなく下げという結果になりましたとさ。

4完緑パフォで冷え😭😭
E問題は十分時間があったのですが、解けませんでした。また、次回頑張ります
devgenjin77さんのAtCoder Beginner Contest 244での成績：2140位
パフォーマンス：884相当
レーティング：1040→1025 (-15) :(#AtCoder #ABC244 https://t.co/BIEJ9tMfkG
— devgenjin77 (@devgenjin77) 2022年3月20日

振り返り

Cでちょっとしたやらかしがあったのが敗因です。

A問題

A - Last Letter

文字列 $S$ の末尾の文字を出力する問題。これはほとんどやるだけの問題なので、速攻で実装してACを取ることができました。

0分54秒で1完。多分、A問題を0分台で解いたのは初めてかも。

提出コード

https://atcoder.jp/contests/abc244/submissions/30267950

B問題

B - Go Straight and Turn Right

これもほぼやるだけの問題。東南西北それぞれの向きの場合に1マス進んだ時の $x$ 座標と $y$ 座標の差分を配列で管理し、向きの遷移を $mod4$ で扱えば大丈夫。

ということで、あとは実装と提出を行い、問題なくACが取れましたとさ。

5分45秒で2完。自分の中では、まあまあ早い方のタイムという印象です。

提出コード

https://atcoder.jp/contests/abc244/submissions/30273530

C問題

C - Yamanote Line Game

で、なんの前触れもなくいきなり出てきたインタラクティブ問題。。

とりあえず提出だけはしたAHC008がインタラクティブ問題だったので、まあまあ実装経験はあるかという所なので、まあ大丈夫かなと。。

で、やるべきことは単純にSetで今まで使った番号を管理すればOKということで、まずは実装して提出してみたら、、なんとWAという結果。。

なんか実装がマズイのか？ということで、すこし変えてみるもWAという結果は変わらず。。

で、ローカルでちゃんとテストしてみたら、なんのことはない、自分で出力した数字をSetで管理するのをド忘れしてましたというオチでした。。。

バグを治したら、ちゃんとAC。インタラクティブ問題だろうがなんだろうが、ちゃんとテストするのは大事だなーという知見を得ました。

16分7秒の2ペナで3完。この2ペナがかなり痛かったです。

提出コード

https://atcoder.jp/contests/abc244/submissions/30280621

D問題

D - Swap Hats

$10^{18}$ 回操作するというよりも、操作を偶数回行うに読み替えたほうがよさそうな問題。

で、要素が3つなので、とりあえず2回の操作で作れる文字の並びを見てみる。すると、元の並びと全く同じか、または、全ての文字の位置が変わっているケースは作れるが、1文字だけ位置が同じというケースが作れないという感じかと。

ということで、あとは実装だけしてACが取れましたとさ。

25分15秒の2ペナで4完。ここで順位は1300ぐらいだったのですが、ペナの影響であとは落ちる一方でした。。

提出コード

https://atcoder.jp/contests/abc244/submissions/30285768

E問題

E - King Bombee

まだまだ苦手意識のあるグラフ問題。さらに、今回は経路数を考えるという、自分的にはあまり経験のない問題。。ということで、まったく解法は思いつかず。。。

とはいえ、1時間以上はあるので、なんとかやり方はないものかと、いろいろググってみたり蟻本を漁ったり悪あがきをしてみるも、全く手がかりはつかめず。

うーん、どんなアルゴリズムを使うべきなのかが全くわからんということで、最後は諦めモードに。結局、1時間椅子を温めただけで終了ということになりましたとさ。

で、解説を見てみると、この問題は動的計画法で解くべき問題だったとのこと。全く思いつきませんでしたわ。

F問題

F - Shortest Good Path

コンテスト中、チラ見はしてみたものの何もわからず。

G問題

G - Construct Good Path

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

Ex問題

Ex - Linear Maximization

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

これまでの実績

連勝も止まりまして、再度停滞モード突入の予感です。

総括

前回のABC 243では、Eの難易度が高かったため、4完終了でもそこそこのパフォが出たのですが、今回のE問題は大分解かれていた問題だったので、結局パフォが伸びませんでした。

まあ、今回のE問題が解けないようでは、上に行けないのも仕方なしという印象ではあります。

また、こういうときはペナの影響もかなり大きかったですね。ペナなしの状態なら現状維持ぐらいは行けたのですが、、まあこれも自分の所為なので致し方なし。

今回も反省点の多い回でした。また、精進を重ねて力を付けて行こうと思います。

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

2022-03-20

AtCoder Regular Contest 137 参加記

AtCoder 競プロ ARC

2022/3/19に開催されたAtCoder Regular Contest 137に参加しました。

atcoder.jp

先週のABCコンテストでなんとか連敗をストップすることができ、レートも4桁に復帰しました。

今回はARCということで、問題セットによっては0完爆死もあり得るかというところですが、なんとか2完いけたらという気持ちで臨むこととしました。

Rated参加します。とりあえず目標は2完以上ということで。

AtCoder Regular Contest 137 - AtCoder https://t.co/XISLNwgbtC
— devgenjin77 (@devgenjin77) 2022年3月19日

今回の結果

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

パフォーマンスは緑上位ぐらい出てくれまして、レートは上昇。なんとか連勝することができましたとさ。

2完4ペナでも緑パフォまで出てくれて、なんとかレート上昇となりました😂😂
次のABCも頑張ります✊

devgenjin77さんのAtCoder Regular Contest 137での成績：1512位
パフォーマンス：1153相当
レーティング：1027→1040 (+13) :)#AtCoder #ARC137 https://t.co/z0dX3DoGF6
— devgenjin77 (@devgenjin77) 2022年3月19日