2021-12-28

AtCoder Beginner Contest 233 参加記

AtCoder 競プロ ABC

2021/12/25に開催されたAtCoder Beginner Contest 233に参加しました。

前回と前々回のコンテストでは思うような結果が残せず、結果として連続でレートが下がってしまいました。今回は2021年最後のABCコンテストということで、良い結果を残して来年に繋げようかということで、とりあえずレート上げを最低限の目標として臨むこととしました。

参加します。2021年最後のABCコンテスト。冷えて終わることがないようにしたいですな。

AtCoder Beginner Contest 233 - AtCoder https://t.co/fM7RYMSVAs
— devgenjin77 (@devgenjin77) 2021年12月25日

今回の結果

で、結果としては5完を達成。タイムは個人的にはまずまず良好かなという印象です。

パフォーマンスは水色。とりあえず4桁レートに復帰ということで、満足のいく結果で終えることができました。

5完水パフォで4桁レートに復帰しました😂😂
明日も頑張ります✊
devgenjin77さんのAtCoder Beginner Contest 233での成績：1216位
パフォーマンス：1319相当
レーティング：981→1020 (+39) :)
Highestを更新しました！#AtCoder #ABC233 https://t.co/JVIF5eDrce
— devgenjin77 (@devgenjin77) 2021年12月25日

振り返り

今回、E問題までが緑Diffだったようで、個人的には5完がノルマという問題セットでしたね。

A問題

A - 10yen Stamp

$\lceil \frac{Y - X}{10} \rceil$ を求める問題。マイナスのケースも考慮が必要な為、実装としては以下の要領で行う。

System.out.println(Math.max((y - x + 9) / 10, 0));

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

提出コード

https://atcoder.jp/contests/abc233/submissions/28113606

B問題

B - A Reverse

StringBuilderのreverseメソッドを部分的に使えば良いかと思ったが、逆に実装がややこしくなりそうなので無難に以下の要領で実装。

$S_L$ と $S_R$ を入れ替え
$L$ をプラス1、 $R$ をマイナス1する
$L \lt R$ の場合、再度1.の処理を行う

これで問題なくACが取れましたとさ。

提出コード

https://atcoder.jp/contests/abc233/submissions/28119424

C問題

C - Product

一読しただけでは、制約条件の上限値がよく分からなかったが、C問題といえばとりあえず全探索でなんとかなるという印象のため、まずは愚直に全探索で実装する方針で取り掛かることに。

とりあえずDFSで全探索のロジックを作成。計算過程では一応オーバーフローを考慮したり、剰余を計算して多少の効率化を図ったりなど工夫を凝らしたところ、多少実装に手間取ったものの、なんとかACが取れました。

提出コード

https://atcoder.jp/contests/abc233/submissions/28130933

D問題

D - Count Interval

結果として、やったことは、公式解説と大体同じようなことになりました。

与えられた数列 $A$ の合計 $SUM$ を計算していく過程で、各要素までの累積和とその値が何回現れたかを管理する連想配列を作成することを考える。

あとは、 $SUM$ の計算途中で連想配列より $SUM - K$ の出現回数を答えに足し合わせていけば答えを導くことができる。

ということで実装にかかり、一度はオーバーフロー要因と思われるWAを出してしまうも、2回目の提出でACを取ることができました。

提出コード

https://atcoder.jp/contests/abc233/submissions/28135364

E問題

E - Σ[k=0..10^100]floor(X／10^k)

見た目がややこしそうな問題だったが、サンプルを見ると $X = 1225$ の場合、 $1225 + 122 + 12 + 1$ という要領で、元の数を10で割った値をひたすら足し続ける問題のようだ。

制約からするに、Javaでまともに計算するのは不可能そうなので、以下のような工夫を用いて解くことに。

$array[ i ] :=$ $A$ の先頭1桁目から $i$ 桁目の数字をそれぞれ1桁の数字と見做して合算した値を前計算で作成する。

あとは、 $array$ の後ろの値から、10の剰余を答えの桁として追加し、10で割った商を繰り上がり分として、 $array$ の一つ前の値に足していく。

この処理を $array$ の先頭まで続けて、 $array[1]$ の値はそのまま答えの先頭に設定する。

上記の要領で実装を行い、なんとかACを取ることができました！

余談だが、この問題、Pythonだと普通に計算しても解けてしまうようですね。この辺に競プロとしてのJavaの不便さというか、メリットのなさを感じてしまう。。

提出コード

https://atcoder.jp/contests/abc233/submissions/28139257

F問題

F - Swap and Sort

30分ぐらい時間があったので、問題を熟読してみましたが、解法は全く思いつかずで、結局時間切れとなりました。

あとで確認すると、bitDPの応用問題ということ。今後上位に上がるためには必須となる知識と思われるので、後日解説ACしておこうと思います。

G問題

G - Strongest Takahashi

ワンチャンあるかと、問題はチラ見してみましたが早々に諦め。

Ex問題

Ex - Manhattan Christmas Tree

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

これまでの実績

とりあえず、4桁レートに復帰しました。とはいえ、ここから上に行くのはしんどそうだなーという気がしなくもないです。

総括

今回ある程度早めの5完達成ということで、なんとか水色パフォまで出すことができました。とはいえ、今後自分が水色コーダーになろうと思ったら、今回のパフォーマンスが最低ノルマで、青パフォを射程圏内に入れるこが求められるかと思います。

そのためには、今回解けなかったF問題をはじめ、青Diffまでの過去問は積極的に取り組んでいく必要がありますね。これは、年末年始などの空いた時間でやっていこうと思います。

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

2021-12-20

M-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232) 参加記

AtCoder 競プロ ABC 企業主催コンテスト

2021/12/19に開催されたM-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232)参加しました。

atcoder.jp

前回のABCコンテストでは、あえなくレート下げを喰らってしまい、せっかく一時は4桁になったレートも、3桁となってしまいました。

今回は、なんとか4桁に復帰できるようにという気持ちで臨むこととしました。

Rated参加します。連敗を止めて4桁レートに復帰できるように頑張ります✊

M-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232) - AtCoder https://t.co/I2aCINM4lZ
— devgenjin77 (@devgenjin77) 2021年12月19日

今回の結果

で、肝心の結果ですが、今回はぎりぎりで4完を確保できたというところでした。。

パフォーマンスもぎりぎり緑。結局連敗ということになってしまいました。。

4完緑パフォで連敗しました。次こそは。。。
devgenjin77さんのM-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232)での成績：2309位
パフォーマンス：837相当
レーティング：996→981 (-15) :(#AtCoder #M-SOLUTIONSプロコンオープン2021(ABC232) https://t.co/HugVJ7z9hS
— devgenjin77 (@devgenjin77) 2021年12月19日

振り返り

B、C問題で盛大にやらかしてしまい、4完するのが精一杯でした。

A問題

A - QQ solver

入力は3文字固定なので、1文字目と3文字目を数値とみなして掛け算すれば良い。

問題なくAC。

提出コード

https://atcoder.jp/contests/abc232/submissions/27985125

B問題

B - Caesar Cipher

$T_1$ と $S_1$ をint型とみなして引き算を行い、その差の値が全ての $T_i$ と $S_i$ の差と同じだったらYesとすれば良い。

と思って提出してみたものの、なんとこれがWAを食らってしまう。。

んで、このWAの原因が全く分からずでパニクってしまい、いろいろ悪あがきをしていじってみたコードを提出するも、WAの結果は変わらず。。

気づけば、B問題が解けずで20分も溶かしてしまいました。。。

これはいかんと問題文を見直し、愚直に題意の $K$ の値を $S_1$ と $T_1$ から求めて、他の $S_i$ と $T_i$ から求めた $K$ の値が全ての $i$ について同じとなるかというプログラムにしたところ、なんとかWAが消えてくれました。

B問題で大分ハマってしまい、開始26分で2完目のAC。相当出遅れてしまいました。

提出コード

https://atcoder.jp/contests/abc232/submissions/27999933

C問題

C - Graph Isomorphism

C問題にしては珍しいグラフ問題かと思ってたら、どうもこれは数列 $P$ を順列全探索して求める問題らしいということに気づいた。うーむ、過去にはやったことはあると思うが手持ちのコードにそのサンプルが見当たらない。。

ということで、「順列全探索」でググった結果より、適当に見繕ってコピペしてきたコードをいじくり回してなんとか実装をしてみることに。

で、なんとか動きそうな実装はできたものの、サンプルのケースが通らず。且つどこが原因かもよく分からんという事態に陥ってしまいました。。

あれこれやってみるも上手くいかず、残り時間も相当厳しい状態に。このままC問題と心中すれば、最悪2完で爆死という悲惨な結果になってしまいそうだったので、一旦D問題から片付けることに。

で、結局DをACした後で、Cに戻って来た時にデバッグを色々やってみたところ、有向グラフとして作成、比較をしてしまっていたのが原因ということにやっと気づき、なんとかコンテスト終了間際に実装と提出にこぎつけることができましたとさ。

大分冷や汗ものでしたが、なんとか4完が確保できたというとこです。

提出コード

https://atcoder.jp/contests/abc232/submissions/28017206

D問題

D - Weak Takahashi

C問題が解けずでやってきたD問題だったが、こちらはすぐに解法が思い付いたので助かった。

右のマスと下のマスを探索していくBFSを実装し、マスごとの移動回数の最大値及び全体の移動回数の最大値を管理して、最終的に移動回数の最大値を出力すれば良い。

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

提出コード

https://atcoder.jp/contests/abc232/submissions/28013200

E問題

E - Rook Path

Dを解いた直後に、ワンチャンあるかとE問題も覗いてみたが、一読しても解法が思いつかずのため、とりあえず諦めてC問題に戻ることにしました。

F問題

F - Simple Operations on Sequence

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

G問題

G - Modulo Shortest Path

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

H問題

H - King's Tour

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

これまでの実績

レートはまたまた微減。はやく4桁に復帰したいなーー。。

総括

今回は、B、C問題で相当なやらかしをしてしまい、大幅なタイムロスをしてしまったのが大いに悔やまれます。

どちらの問題も、難易度的にはそんなに苦戦する問題でなかったのですが、勝手な思い込みが原因でハマってしまい結果として解き切るまでに相当に時間を喰ってしまうという惨憺たる状況となりました。

今回の問題セットだと、4完で60分は切れるぐらいは行けたと思うし、そうすればレートが下がるという事は無かったかと思います。簡単な問題を取りこぼさないようにする訓練がもっと必要なんだと痛感しました。高難易度の問題を解く訓練と並行して、低難易度問題も数を解いて早解きができるようにしていきたいと思います。

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

2021-12-12

パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231) 参加記

AtCoder 競プロ ABC 企業主催コンテスト

2021/12/11に開催されたパナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231)に参加しました。

atcoder.jp

直近のARCコンテストでは人生初の青パフォを達成し、レートは4桁の大台に乗りました。

しかし、レートが爆上がりしたことで今後はそれなりのパフォーマンスが出せないと冷えてしまうという状況にもなりました。

ということで、今回のコンテストでは何とか現状のレートぐらいの結果は欲しいという気持ちで臨むこととしました。

Rated参加します。前回のコンテストは、まぐれ勝ちでレートが大幅上昇したので、今回は現状維持以上を目標に頑張ります✊
パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231) - AtCoder https://t.co/0FpsPXndsu
— devgenjin77 (@devgenjin77) 2021年12月11日

今回の結果

今回、なんとか4完を確保することができたというところです。

肝心のパフォーマンスはというと、緑パフォが出たものの、4桁を切る結果となったので、今回は冷えということになってしまいました。。

4完緑パフォで冷えました。次頑張ります
devgenjin77さんのパナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231)での成績：2134位
パフォーマンス：915相当
レーティング：1005→996 (-9) :(#AtCoder #パナソニックプログラミングコンテスト2021(ABC231) https://t.co/cB1CPZ5FG3
— devgenjin77 (@devgenjin77) 2021年12月11日

振り返り

Dで少し手間取ってしまい、E以降は手が出ませんでした。

A問題

A - Water Pressure

一読すると単純に入力を $100$ で割った結果を、小数点付きで出力するだけのように見える。

最近のA問題は難易度が上がってきているという印象があったので本当にこんな簡単で良いのかと疑心暗鬼になりましたが、あまり考えてもしょうがないので普通に実装して提出。問題なくACが取れましたとさ。

提出コード

https://atcoder.jp/contests/abc231/submissions/27816714

B問題

B - Election

候補者の名前をキー、名前が出てきた回数を値としたHashMapを作り、最終的に値が最大となる候補者名を出力すれば良い。

こちらも問題なくAC。

提出コード

https://atcoder.jp/contests/abc231/submissions/27821630

C問題

C - Counting 2

まずは、入力の $A$ をソートし、各 $x_i$ が、 $A$ の中で何番目の大きさであるかを二分探索で求めれば良い。

ということで実装したものの、細かい条件分岐などで結構戸惑ってしまい、いろいろ試行錯誤した挙句になんとかACが取れたというところでした。

提出コード

https://atcoder.jp/contests/abc231/submissions/27835518

D問題

D - Neighbors

最初この問題を見た時、少し前に出てきたトポロジカルソートの類題かな？という考えが頭をよぎり、とりあえず類題と思われる問題のACコードをパクってきて貼ってみるということをやってみましたが、サンプルすら通らず。。

よくよくサンプルケース２をみると、同じ人が3回以上出てくる場合はどうやっても隣り合うように配置ができない。ということで、そもそもトポロジカルソート自体が相当な勘違いということに気づき、結構時間を無駄にしてしまいました。

では、次は入力を無向グラフとみなし、次数が3以上の頂点があればNoという感じで実装、提出をしてみましたが、こちらはWAという結果。よくよく考えると、グラフにサイクルが含まれるようなケースもダメなようだ。。

ということで、Union-Findを使って連結成分中にサイクルが発生するかを検知し、サイクルができればNoという条件を追加して提出。なんとかこれでACを取ることができましたとさ。

提出コード

https://atcoder.jp/contests/abc231/submissions/27844598

E問題

E - Minimal payments

なんか昔、これに似たような問題をやったかなーとことで、過去問を漁ってみましたが、該当の問題が分からず。うーん、これまでやってきた過去問とかをちゃんと整理しないとなー。。

で、あまり考えててもラチがあかないのと、順位表をみると、F問題の方が解かれていそうだったので、この問題は諦めることに。

F問題

F - Jealous Two

考察してみると、 $N^{2}$ 通りのパターンから、 $i$ 番目のプレゼントをもらった場合に、それより嬉しさが大きいプレゼントが相手に渡るケースを引いていく問題のように思える。

あとは、 $i$ 番目のプレゼントが、何番目に嬉しさが大きいかを、 $A,B$ について求めて計算すれば良いかと考えましたが、気づけばもう終了時間間近。結局この問題を解くことはできませんでした。

G問題

G - Balls in Boxes

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

H問題

H - Minimum Coloring

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

これまでの実績

レートは微減。4桁の大台を割り込んでしまったのがなんとも悔しいところです。。

総括

今回の問題セットでは、4完早解きができれば現状維持ができたかというところでしたが、D問題で大きな勘違いをし、タイムロスをしてしまったのが痛かったですね。

他にも、C問題はもう少し実装が早くできたかというところなので、実装のスピードを上げていくことも今後の課題として取り組んでいこうかと思います。

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

2021-12-10

AtCoder Regular Contest 131 参加記

AtCoder 競プロ ARC

2021/12/5に開催されたAtCoder Regular Contest 131に参加しました。

atcoder.jp

金曜のABCは茶パフォで終わってしまい、直近2連敗で迎えた今回のARC。

ARCは問題の内容によっては0完もありうるかもという苦手意識があるのと、今回からRated参加の機能が追加され、0完NoSubでもレート反映されるとのことで爆死を覚悟しないといけないというところでしたが、いまさら緑コーダー如きが守りに入ってもどうしようもないだろうということで、参加することにしました。

前回は遅めの2完で足りなかったというところだったので、今回の目標は早めの2完です。

Rated参加します。とりま目標は早めに2完すること。

AtCoder Regular Contest 131 - AtCoder https://t.co/DpIQx3ezul
— devgenjin77 (@devgenjin77) 2021年12月5日

今回の結果

で！今回はなんと3完という望外の結果と相成りました。

しかも！人生初の青パフォ達成！レートはHighestを突き抜けて一気に1000の大台を達成！！まさしくこれが僥倖というしかないというところです。

初の青パフォでHighest突き抜けました😂😂😂
この調子で入水目指して頑張ります✊
devgenjin77さんのAtCoder Regular Contest 131での成績：662位
パフォーマンス：1608相当
レーティング：913→1005 (+92) :)
Highestを更新し、5 級になりました！#AtCoder #ARC131 https://t.co/E7dSMy2Ztn
— devgenjin77 (@devgenjin77) 2021年12月5日

振り返り

Cが解けてくれたので、満足してしまいました。

A問題

A - Two Lucky Numbers

$2x$ を十進法で書いたときに、部分文字列として $B$ を含むということで、 $x$ には $B \times 5$ を部分文字列として配置しておけばよさそうという考えが浮かんだ。

よって、 $B \times 5$ と $A$ を連結した文字列を解とする実装で提出。制約最大の時のケースで通るかという不安はありましたが、なんとかACを取ることができました。

提出コード

https://atcoder.jp/contests/arc131/submissions/27713933

B問題

B - Grid Repainting 4

まだ塗られていないマス目について、5色のうち上下左右どの色とも異なる塗り方をせよという問題。

言うまでもなく、5種類の色が選択でき、上下左右どの色とも被ってしまうという状況が存在しないので、単純に周りと異なる色を選択すれば良い。

あとは実装するだけ。すこし手こずりましたがなんとかACを取ることができました。

一応前回より大分早めの、開始30分で2完達成です。

提出コード

https://atcoder.jp/contests/arc131/submissions/27717409

C問題

C - Zero XOR

3完を目指すべく望んだC問題だが、一読したのみでは解法が思いつかず。。XORの性質が絡む問題とかあまり上手く解けた記憶が無いんだよね。。

だが、時間は結構余っていたのと、順位表を見る限りD以降が絶望的な難易度という予想が立ったので、とりあえず悪あがきしてみることに。

よくよく考えてみると、Nimの必勝法に関連する問題かという感じがしたので、類題として今まで見たことのあるNimに関する過去問などを漁ってみると、 $N$ の偶奇によって場合分けするのが解法のヒントかなという気がする。

そこでよくよく考えてみると、

$N = 1$ の場合、必勝
$N = 3$ の場合、相手が残り2個の状態から勝てるケースが無いので必勝
$N = 5$ の場合、残り4個で手番を渡したときに相手が勝てる手が無ければ、 $N=3$ の場合に移行するので必勝

ということで、 $N$ が奇数なら必勝として良い気がする。

$N$ が偶数の場合は、現在の手番で1手で勝ちとなる手があれば必勝なのは自明。それ以外の場合は、、、前述の考え方と同様で、奇数個で手番となった方が主導権を握れそうな気がするので、後手必勝として良い気がする。。

まあ、考察が間違ってってWAを食らったとしても大したリスクではないので、とりあえず上記の考察で実装をしてみることに。ちなみに、実装しながら検討したのですが、1手で勝てる手とは、すべてのクッキーの値をXOR演算した値のクッキーが存在するかということですね。

で、ダメ元で投げてみたら、なんとこれが見事に一発ＡＣ！見事解法エスパー成功となりました！！

提出コード

https://atcoder.jp/contests/arc131/submissions/27721694

D問題

D - AtArcher

時間が余ったので、問題を見ながらあれこれ検討してみましたが、何も分からず。

というか、Cが解けたことで満足してしまい、考察もそこそこにあきらめモードとなりましたｗ

E問題

E - Christmas Wreath

これも問題を見ながらあれこれ検討してみましたが、何も分からずで諦め。

F問題

F - ARC Stamp

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

これまでの実績

ここ最近は、微増微減の結果でしたが、今回の青パフォで一気に突き抜けました！！

総括

今回は、初めて青パフォを達成し、レートの4桁の大台に乗せたということで非常に良い気分ですが、逆に4桁レートになったことで今後は少なくとも緑上位か水色ぐらいのパフォを出すのがノルマということになってしまいました。

今回の結果は、まぐれ勝ちというところもありますので、実力以上のレーティングになってしまっているかもしれませんが、なんとか今後のコンテストでは現状維持以上ができるように日々精進を重ねていこうと思います。

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

2021-12-05

AtCoder Beginner Contest 230 参加記

AtCoder 競プロ ABC

2021/12/3に開催されたAtCoder Beginner Contest 230に参加しました。

atcoder.jp

前回参加したARC130で、わずかに冷えてしまったので今回は連敗だけは避けようという気持ちで参加することにしました。

Rated参加します。前回のARCでわずかに冷えたので、今回は連敗しないように頑張ります✊
AtCoder Beginner Contest 230 - AtCoder https://t.co/PXi31XPY9Y
— devgenjin77 (@devgenjin77) 2021年12月3日

今回の結果

で、結果ですが、久々の3完という無念な結果となりました。。

こりゃ、だいぶ冷えるかと思ったのですが、なんとか茶色パフォの上の方だったので、なんとか、かすり傷ですんだかというところです。

3完茶パフォで連敗です😭😭
また、次、頑張ります
devgenjin77さんのAtCoder Beginner Contest 230での成績：2472位
パフォーマンス：796相当
レーティング：925→913 (-12) :(#AtCoder #ABC230 https://t.co/el5fPgmhGx
— devgenjin77 (@devgenjin77) 2021年12月3日

振り返り

D、E以降は全く手が出ませんでした。

A問題

A - AtCoder Quiz 3

やたら前置きが長いA問題だったが、 $N$ が42を超えた場合、 $N$ に1を足して表示してやればOK。

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

提出コード

https://atcoder.jp/contests/abc230/submissions/27645480

B問題

B - Triple Metre

当初、oとxの並びであり得ないパターンを検討していく問題かと思ったが、よくよく考えると、 $|S|$ が10以下程度ということで、"oxx"をある程度の長さで連結しておいて、 $S$ がその連結文字列に含まれるかを考えれば良さそう。

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

提出コード

https://atcoder.jp/contests/abc230/submissions/27651003

C問題

C - X drawing

問題文を読んだだけでは、問題の意味がさっぱり分からずに時間を溶かしてしまったが、サンプルをみるにマス目 $(A,B)$ を中心としたXの字を書いて、あとは四角形で切り取った部分を表示せよということらしいことがわかった。

$N$ の最大値が $10^{18}$ ということで、マス目全ての状態を管理するのは不可能ということで、 $(P,R)$ を左上、 $(Q,S)$ を右下とする四角形で各マス目の状態が判定できれば良さそう。

あとは、判定するマス目に対して、 $k$ が求めることができる場合、問題文のとおりの条件式に合致するかどうかを判定することでなんとかACが取れました。

提出コード

https://atcoder.jp/contests/abc230/submissions/27662023

D問題

D - Destroyer Takahashi

なんか見た目上、区間スケジューリング問題っぽい形をしたこの問題。

サンプルの見た目上、一番 $R_i$ の小さい順番でソートし、右端から $+D - 1$ 列目までにパンチをすることでいけそうな気がするが、証明もおぼつかなかった為実装に手をつけることができず、いろいろ悩んでしまい時間を溶かしているうちに時間切れとなってしまいました。

で、解説をみると結局、区間スケジューリング問題だったようで解法も思いついたものとそう変わらないものだったというオチでした。。

こんなことだったら、とりあえず実装をしてしまえば良かったかなーと思うものの後の祭り。自分の実力不足を認めるしかありません。

E問題

E - Fraction Floor Sum

D問題に詰まってしまったため、E問題もチラ見してみましたが、これもよく分からずで早々に諦め。

F問題

F - Predilection

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

G問題

G - GCD Permutation

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

H問題

H - Bullion

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

これまでの実績

ついに、ABC単体で見た時の連勝もストップしてしまいました。

総括

今回のD,E問題は、ある程度典型アルゴリズムに対する理解が無いと対応できない問題。やはりまだまだ典型に対する知識を得るための精進が足りないと感じる次第です。

ここ数ヶ月レート上昇を続けてきましたが、実力の方は早々上がっていないようで、このままでは緑の下位の方で停滞する可能性が高いですね。今回の問題も復習もそうですが、当面は典型アルゴリズムを習得することを目標に精進をしていきたいと思います。

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

2021-11-30

AtCoder Regular Contest 130 参加記

AtCoder 競プロ ARC

2021/11/28に開催されたAtCoder Regular Contest 130に参加しました。

atcoder.jp

ARCはめちゃくちゃ久しぶりの参加。ここ最近は基礎を固めようということでABCコンテストに絞って参加するようにしてきましたが、この前日に行われたABC229は都合がつけられず不参加となり、あまり間を開けたくなかったのと、そろそろARCも参加してみようかなーという気まぐれが合わさり、今回参加することになりました。

これまでのARCの最高記録は3完というところ。直近のARCも問題ぐらいは目を通していたのですが、この難易度ぐらいだと2完はできればレート維持は可能かな、という感じだったので、とりま2完が目標ということで臨んでみることにしました。

久々のARC参加。なんとか2完できるように頑張ってみます！
AtCoder Regular Contest 130 - AtCoder https://t.co/liOJDl2ets
— devgenjin77 (@devgenjin77) 2021年11月28日

今回の結果

で、今回はなんとか2完を確保できました。とりあえず有言実行です。

が、、なんとパフォーマンスはギリギリ緑にのった程度しか出ず、久しぶりのレート減という結果になりました。。

2完取れたもののギリギリの緑パフォでレートは微減となりました😢
連勝は途切れましたが、また気持ちを切り替えて、次頑張ります。
devgenjin77さんのAtCoder Regular Contest 130での成績：1193位
パフォーマンス：868相当
レーティング：931→925 (-6) :(#AtCoder #ARC130 https://t.co/SoDhOrGJ4s
— devgenjin77 (@devgenjin77) 2021年11月28日

振り返り

A、B問題ともなんとか解けたという体たらくでした。

A問題

A - Remove One Character

初っ端のA問題から問題の理解に苦しみましたが、サンプルをみると、同じ文字が連続する回数を見ていけば良さそうという印象。

文字列を先頭から見ていき、同じ文字が2連続以上した場合連続した回数をリストに追加。あとは、リストに追加した回数 $K$ に対して、初項１、公差１、項数が $K - 1$ の等差数列の和を答えに加算していくことで解けそうかと。

で、ここまでの考察とか等差数列の公式をググったりという作業で時間はかかりましたが、なんとかACを取ることが出来ました。

提出コード

https://atcoder.jp/contests/arc130/submissions/27570725

B問題

B - Colorful Lines

与えられたクエリを順番に処理するためには、どの色が上塗りされて消されたかという情報を逐次更新していく必要があり、マス目の大きさやクエリ数の制約からすると愚直にこれを行うのは難しそう。

だからといって、これを解くために必要な典型アルゴリズムがあるのかもよくわからずで、いろいろ思考を廻らせるも解決策が見えずで、20分以上時間を浪費しましたが、最後のクエリから逆順で処理をしていき、１列を塗る場合は、これまでに塗った行数分のマス目を、１行を塗る場合は、これまでに塗った列数分のマス目を引いてやることで上手く計算ができることに気づいた。

あとは、塗った列番号、行番号をそれぞれ別のSetで管理し、クエリのタイプごとに差し引くマス目を求めることで実装、なんとかACが取れてくれました。

これでなんとかノルマの２完達成。このときはまさかレートが冷えるとは思いもしませんでした。。

提出コード

https://atcoder.jp/contests/arc130/submissions/27574341

C問題

C - Digit Sum Minimization

3完を目指すべく望んだC問題でしたが、一読しようと何読しようと全く解法が思いつかず。。

時間はある程度残ってましたが、ほぼほぼ諦めモードで結局そのまま終了と相成りました。

D問題

D - Zigzag Tree

問題をチラ見しましたが、何も分からず。

E問題

E - Increasing Minimum

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

F問題

F - Replace by Average

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

これまでの実績

長らく続いていた上昇トレンドも、11連騰で終了。まあ連勝はいつか終わるものなので、あまり気にしても仕方ないですなー。負け惜しみですが。

総括

今回、久々のARC参加。パフォーマンスは出ませんでしたが、当初は2完できずにレート暴落するかという不安しかなかったため、なんとか大怪我せずにすんだかという印象です。

やはり、ARCに出るからには青Diffあたりこなせないと難しいかもしれませんが、今後の自身のレベルアップの為にはARCも積極的に参加していく必要があるかと思いますので、年末にかけてARCは都合のつく限り参加していこうという所存です。

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

2021-11-24

トヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228) 参加記

AtCoder 競プロ ABC 企業主催コンテスト

2021/11/20に開催されたトヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228)に参加しました。

atcoder.jp

ここ最近のレートの推移は順調な上昇トレンドを刻んでおり、前回までのコンテストで10回連続でレート上昇という状況。

今回もその流れを途切れさせないようにという気持ちで臨むこととしました。

参加します。ここ最近レート上昇傾向が続いているので、途切れさせないように頑張ります。

トヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228) - AtCoder https://t.co/Kw4YnnO52W
— devgenjin77 (@devgenjin77) 2021年11月20日

今回の結果

で、今回はなんとか4完を確保することが出来たというところです。

今回もパフォーマンスは4桁台を出すことが出来、レートの方は11連騰となりましたとさ。

4完でレート続伸です😃
devgenjin77さんのトヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228)での成績：1723位
パフォーマンス：1102相当
レーティング：911→931 (+20) :)#AtCoder #トヨタシステムズプログラミングコンテスト2021(ABC228) https://t.co/Cq1qyEkqc5
— devgenjin77 (@devgenjin77) 2021年11月20日

振り返り

A問題で想定外のWAを喰らったりしましたが、なんとかDまでを解き切ったというところです。

A問題

A - On and Off

最近、結構難易度が上がってきた感があるA問題。今回の問題も一読してそこそこ手強い感じがする。

とりあえず、日付が変わることも考慮するということで、 $S \gt T$ の場合、 $T$ に24を足して、 $S \le X \ le T$ であればYesという感じでいいのでは？

と、雑な考察で投げてみたら、いきなりのWAを喰らってしまいましたorz

その後も $S \gt T$ を $S \ge T$ に変えてみたらどうかいう感じで投げてみても再度WAを喰らってしまう。

ここで、それならばと、 $X \gt S$ の場合に、 $X$ にも24を足して、 $S \le X \le T$ であればYesという感じでいいのでは？

で、これで投げてみたらやっとこさACがとれましたとさ。

A問題からいきなりの2WAのスタートで、出鼻をくじかれた格好です。

提出コード

https://atcoder.jp/contests/abc228/submissions/27356758

B問題

B - Takahashi's Secret

これについては、解法がすぐに思いついたので助かった。

秘密が伝わったかどうかをON、OFFで管理する配列 $S$ を用意しておく。友達 $i$ に秘密が伝わった時、友達 $A_i$ に秘密がまだ伝わっていない場合は、 $S_{A_i}$ をONにする。

この処理を再帰的に繰り返していき、友達 $A_i$ に秘密が伝わっている場合は処理を終了する。

最後に、 $S$ の配列内でONになっている数を答えとして出力すればよい。

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

提出コード

https://atcoder.jp/contests/abc228/submissions/27363241

C問題

C - Final Day

各生徒の得点の合計を計算し、降順ソートを行う。あとは、上位から $K$ 番目の点数に対して、各生徒の得点＋300した点数で届く場合YES、そうでない場合NOとすればよい。

あとは実装だけしてACが取れましたとさ。

提出コード

https://atcoder.jp/contests/abc228/submissions/27371650

D問題

D - Linear Probing

そもそも、問題文を理解するところから時間をかけてしまった。。

整理してみると、サイズが $2^{20}$ の配列があり、要素に値を設定するクエリを処理する際、既に値が入っていた場合は一つずつ右を見ていくというのがやっと理解できた。

どの要素に何の値が入っているかは、Mapなどを使って処理すれば良さそうだが、ある要素を編集しようとした時に最悪ケースだと右の項目を見ていく処理でTLEになってしまいかねないという感じがした。

このような性質の処理について、どのデータ構造を使えば良いかは分からず。で、いろいろ考えた結果一度値を設定しようとした要素の位置と何回その要素に値を入れようとしたかを別のMapで管理しておき、既に値が入っている要素を編集しようとした時は、その要素を参照した回数分右を見るようにすればある程度効率化できるのではというやり方が思いついたので、とりあえずこの方針で実装してみることに。

で、初回の提出は小バグがありREとなったものの、2回目の提出でなんとかギリギリTLEにならずにACを取ることが出来ましたー。

実行時間は、なんと3100msということで想定解法ではなかったようだが、これでなんとか4完を確保。

初っ端のA問題から2WAを喰らい、さすがに今回は冷えるやも？という不安があったのですが、これでとりあえず一安心することが出来ました。

提出コード

https://atcoder.jp/contests/abc228/submissions/27393270

E問題

E - Integer Sequence Fair

Dを解いたあとチラ見しましたが、なにも解法が思いつかずで終了です。

F問題

F - Stamp Game

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

G問題

G - Digits on Grid

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

H問題

H - Histogram

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

これまでの実績

レートの方は11連騰。もう少しでHighest更新というところです。

総括

今回なんとか4完を確保できたというところですが、A問題でWAを出したり、D問題での解法がサッと出てこなかったりと、反省点も多い回でした。

一旦D問題まではちゃんと解き直しの復習をして次回同様の問題に手こずらないようにしたいと考えております。

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