2022-02-15

AtCoder Regular Contest 135 参加記

AtCoder 競プロ ARC

2022/2/13に開催されたAtCoder Regular Contest 135に参加しました。

ここ最近のARCは良くて2完という感じなので、今回はなんとか2完はいけるかという気持ちで臨むこととしました。

Rated参加します。
とりあえず、2完目標という感じで頑張ります✊

AtCoder Regular Contest 135 - AtCoder https://t.co/DgSetpBwxS
— devgenjin77 (@devgenjin77) 2022年2月13日

今回の結果

で、今回の結果は、なんとか1完を確保という体たらく。。これが現在の実力という所でしょう。

パフォーマンスは、現レートより少し悪いぐらいで収まり、ちょい冷えという結果になりましたとさ。

1完緑パフォで冷えました😢
来週はABC連チャンであるようなので、ここで取り戻すべく、精進します。✊
devgenjin77さんのAtCoder Regular Contest 135での成績：1665位
パフォーマンス：983相当
レーティング：1065→1057 (-8) :(#AtCoder #ARC135 https://t.co/DkCBFE6ilc
— devgenjin77 (@devgenjin77) 2022年2月13日

振り返り

Bを解き切ることが出来ませんでした。

A問題

A - Floor, Ceil - Decomposition

とりあえず黒板にある4を超える数字については、操作を行う方が最終的な積は大きくなりそう。ということで求める答えを $f(X)$ とし、以下の式を立ててみる。

$f(X) = f(\lfloor \frac{X}{2} \rfloor) \times f(\lceil \frac{X}{2} \rceil)$ ( $X \gt 4$ )
$f(X) = X$ ( $X \le 4$ )

あとはこれをDFSを使って再帰的に解いていくプログラムを書けば解けるか、ということでサンプルが通った実装を提出したらTLEを食らってしまいました。。

ということで、最近書いていないメモ化DFSをなんとか思い出しながら実装することに。なんとか完成までこぎつけて、ACを取る事が出来ました。

32分53秒プラス1ペナという遅めの内容で1完。

提出コード

https://atcoder.jp/contests/arc135/submissions/29306502

B問題

B - Sum of Three Terms

とりあえず、サンプルケースを元に色々考えてみるが、全く解法が思いつかずで小一時間椅子を温める羽目になってしまいました。。

あまりにもわからないので、諦めて他の問題を見ようかと思うも、順位表をみるとB問題が他に比べて圧倒的にAC数が多いため、この問題以外は見てもあまり解ける見込みは無いものと推察。結局、この問題で最後まで時間を使うことにしました。

で、1時間以上あれこれ検討して、得た考察としては以下のとおり

問題文にある計算式を組み替えてみると、
$A_{4} = A_1 + (S_{2} - S_{1})$ 、 $A_{5} = A_2 + (S_{3} - S_{2})$ 、 $A_{6} = A_3 + (S_{4} - S_{3})$ 、
$A_{7} = A_4 + (S_{5} - S_{4})$ 、 $A_{8} = A_5 + (S_{6} - S_{5})$ 、 $A_{9} = A_6 + (S_{7} - S_{6})$
という感じになり、配列の位置の $mod3$ でグループ分けすることができそう。
$S_{i + 1} - S_{i}$ の値がマイナスになる場合、 $A_1,A_2,A_3$ のいずれかを調整し、 $A$ の全要素についてマイナスにならないように調整する必要がある。
逆にその条件が満たせない場合は解答がNoとなる。

というところまで考えてみたが、実装まで辿り着けずであえなく時間切れ。。

うーん、あと1時間ぐらいあれば解答できたかなーという感じでしたが、実装力と考察力がなさすぎでした。

C問題

C - XOR to All

少し目を通してみたものの、何もわからずで諦め。

D問題

D - Add to Square

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

E問題

E - Sequence of Multiples

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

F問題

F - Delete 1, 4, 7, ...

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

これまでの実績

今回はちょい冷え。水色への道のりはまだまだ遠いです。

総括

今回のB、C問題は水色Diffだったようですが、まだまだこれらを自力で解き切る実力が付いてないということを思い知らされるコンテストでした。

当面の目標は、水色コーダーになることですので、今回のB、Cが解けるぐらいの実力をつけたい所。とりあえず地道に今回の問題を復習して地道に力をつけていくことにします。

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

2022-02-06

モノグサプログラミングコンテスト2022(AtCoder Beginner Contest 238)参加記

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

2022/2/5に開催された、モノグサプログラミングコンテスト2022(AtCoder Beginner Contest 238)に参加しました。

atcoder.jp

先週のABCコンテストは、体調不良で参加できませんでした。よって、2週間ぶりのABCコンテストですが、今回はなんとかレート上げになるようなパフォーマンスを出せるようにという気持ちで臨むこととしました。

Rated参加します。先週のABCは体調不良で参加できずでしたが、今回はレートを上げられるように頑張ります。
モノグサプログラミングコンテスト2022（AtCoder Beginner Contest 238） - AtCoder https://t.co/WvT7598tzu
— devgenjin77 (@devgenjin77) 2022年2月5日

今回の結果

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

ただ、E問題以降が難易度的にいつもより高めだったためか、パフォーマンスは緑後半が出てくれて、なんとかHighest更新を達成することが出来ました。

😂😂😂
devgenjin77さんのモノグサプログラミングコンテスト2022（AtCoder Beginner Contest 238）での成績：1860位
パフォーマンス：1155相当
レーティング：1054→1065 (+11) :)
Highestを更新しました！#AtCoder #モノグサプログラミングコンテスト2022（ABC238） https://t.co/1GBri8FxZy
— devgenjin77 (@devgenjin77) 2022年2月5日

振り返り

C問題でやたらと苦労しましたが、なんとか4完で収めることができました。

A問題

A - Exponential or Quadratic

ここ最近のA問題の中でも、ずいぶんと難し目の問題という印象。 $2^n$ を、この制約でまともに計算すると簡単にオーバーフローするので、どうにか工夫が必要なところ。

で、 $n$ がある程度でかいと、 $2^n \gt n^2$ なのは自明なので、最初の部分を手計算してみることに。すると、 $n$ が2,3,4の場合のみ問題分の条件が偽となる様子。

ということで、 $n$ が、2〜4の時にNo、それ以外はYesと出力する実装をして、ACを取ることが出来ました。

7分42秒という、やや遅めのタイムで1完。

提出コード

https://atcoder.jp/contests/abc238/submissions/29071203

B問題

B - Pizza

三角関数使う問題かと少し考えてみたが、まったくそんな問題ではなかった。

最後に切れ目を入れた角度を $P$ とし、次に切れ目を入れる角度は $(P + A_i)$ を360で割った余りとする。切れ目を入れた角度を配列で管理し、昇順ソートした後、隣の要素との差分の最大値を取ればいけるかと。

ということで、あとはよしなに実装してACが取れました。

20分49秒という、大分遅めのタイムで2完。

提出コード

https://atcoder.jp/contests/abc238/submissions/29079179

C問題

C - digitnum

$f(x):=x - (x$ より桁数が1小さい数の中の最大の数 $)$ とすると、あとは、 $N$ 以下の整数について、各桁数の数がそれぞれ何個あるかを考えれば計算量もほどほどで抑えられるはず。

ということで、以下の要領で計算することにしました。

$N$ 以下で1桁の数の最小値と最大値を求め、等差数列の和の公式で合計を計算し答えに合算する。
$N$ 以下で2桁の数の最小値と最大値を求め、等差数列の和の公式で合計を計算し答えに合算する。また、 $9$ × (2桁の数の要素数)を答えから引く。
$N$ 以下で3桁の数の最小値と最大値を求め、等差数列の和の公式で合計を計算し答えに合算する。また、 $99$ × (3桁の数の要素数)を答えから引く。
以上の要領で、対象とする桁数が、 $N$ の桁数を超えるまで繰り返す。

で、実装までしてサンプルを検証してみたところ、MODの計算がちゃんと出来ていないためか、サンプル３のみが通らない。。

で、いろんなところでMODの余りを計算したり、2で割り算するところを逆元に直してみたりなど、いろいろ悪戦苦闘して、やっとサンプルが通るプログラムになりましたとさ。見返してみると、コードがぐちゃぐちゃになってます。

あとは、提出だけして、無事ACを獲得。

60分0秒での3完。いつもより大分苦戦しています。

提出コード

https://atcoder.jp/contests/abc238/submissions/29091790

D問題

D - AND and SUM

順位表からして、D問題が行ければなんとか下げは喰らわなくて済みそうかなという展開。ということで、なんとしてもこのD問題は取りたいところなので、残り時間全て投入するつもりで考察してみる。

まず、 $a$ を2進数で考えて、1が立っている桁については、 $x,y$ とも1が立っていることが確定する。よって $s$ から $a$ の1が立っている数を2回引いてみる。

その後、 $a$ を2回引いた後の $s$ を $s^{\prime}$ とする。 $s^{\prime}$ がマイナスになっていたら答えはNo。そうでない場合、 $a$ の1が立っていないビットの組み合わせで $s^{\prime}$ が作れるかがみたい。よって、 $s^{\prime}$ と $a$ のANDを取り、答えが0でない場合はNoという判断で良さそう。

ということで、最後の判定で、0の場合はYesで問題ないかが微妙でしたが、サンプルは通ってくれたのでそのまま提出。なんとかACを取ることに成功しました。

79分51秒で4完。順位も1800ぐらいまで上がったので、なんとか下げは免れそうです。

提出コード

https://atcoder.jp/contests/abc238/submissions/29096640

E問題

E - Range Sums

残りが20分程度で、なんとか解けるかとE問題を覗いてみましたが、結局何もわからず。ここで時間切れとなりました。

あとで解説を見てみると、なんとグラフ問題に落とし込む必要がある問題だったとの事。うーむ、その発想は全く無かったわ。。

F問題

F - Two Exams

ワンチャンあるかとチラ見はしましたが、何もわからず。

G問題

G - Cubic?

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

H問題

Ex - Removing People

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

これまでの実績

僅かながらもHighest更新となりました。これでまた水色に一つ近づくことができました。

総括

今回は、C問題でやたらと時間を取られてしまいましたが、D問題がすんなりと解けてくれたので大怪我をせずに済みました。

今回は相対的に難易度高めの回だったかと思いますが、それでもD問題まで取りこぼしがなかったのは日ごろの精進の結果というところかもしれません。

これまで着実に水色に近づいてこれていますので、なんとか次回は水色パフォ以上が出せるように精進を続けていきたいと思います。

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

2022-01-31

AtCoder Regular Contest 134 参加記

AtCoder 競プロ ARC

2022/1/29に開催されたAtCoder Regular Contest 134に参加しました。

atcoder.jp

前回のARC133は、1完で下げという残念な結果だったので、今回はせめて2完を取るぞという目標をもって参加することにしました。

Rated参加します。前回ARCは1完だったので、今回は最低2完はいきたいところ。
AtCoder Regular Contest 134 - AtCoder https://t.co/x1x6MtuHwD
— devgenjin77 (@devgenjin77) 2022年1月29日

今回の結果

結果は、予告通りの2完達成。これが今の全力です。。

肝心のパフォーマンスは今のレートと同じぐらいで、今回は現状維持という結果となりましたとさ。

2完緑パフォで現状維持でした😅
明日はレートを上げられるように頑張ります✊
devgenjin77さんのAtCoder Regular Contest 134での成績：1801位
パフォーマンス：1057相当
レーティング：1054→1054 (±0) :|#AtCoder #ARC134 https://t.co/uGrpla5w66
— devgenjin77 (@devgenjin77) 2022年1月29日

振り返り

Bでかなり悪戦苦闘しましたが、なんとか解き切ることができました。

A問題

A - Bridge and Sheets

位置0からシートで覆われている位置を変数で管理する。左端の区間から参照して覆われていない区間があった場合、その長さを $l$ とすると、 $\lceil\frac{l}{W}\rceil$ 枚のシートが必要となる。

この計算を右端の $L$ の位置まで計算すればOK。

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

提出コード

https://atcoder.jp/contests/arc134/submissions/28862848

B問題

B - Reserve or Reverse

とりあえず、 $s_{x1}$ に対する $s_{x2k}$ を選ぶときに、 $s_{x2k}$ が $s_{x1}$ より右に位置し、かつ辞書順最小のものを貪欲に選んでいけば良さそう。

ということで、まず文字列より、文字の辞書順の昇順且つ文字の位置の降順でソートしたリストを用意し、このリストの先頭を $s_{x2k}$ の候補として選択。

あとは、 $s_{x1}$ が $s_{x2k}$ より辞書順で大きい場合かつ、文字の位置が右となる場合に入れ替えを行うという手法でやってみることに。

で、この方法で大体合っていたようであるが、いざ提出してみると大量のWAに苦しめられることに。。

$s_{x1}$ と $s_{x2k}$ が辞書順で同じだった場合の考慮が抜けていたのを直したりなど、なんやかんややっているうちに5回ペナルティを食らってしまうことになりましたが、なんとかごにょごにょ直しているうちにACを取り切ることができました。

提出コード

https://atcoder.jp/contests/arc134/submissions/28873889

C問題

C - The Majority

残り時間があと20分少々あったので、問題に目を通してみましたが何もわからず。

あっけなく時間切れとなりましたとさ。

D問題

D - Concatenate Subsequences

チラ見するものの何もわかりませんでした。

E問題

E - Modulo Nim

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

F問題

F - Flipping Coins

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

これまでの実績

今回は現状維持というなんとも微妙な結果となりましたとさ。

総括

今回のARCはなんとか2完達成まではできたものの実装ミスが多く、B問題でペナルティを喰らいまり、1時間以上かけてしまったのは反省材料です。

高難易度の問題の精進も必要かというところですが、実装力を高めるために緑Diff程度の問題を数多く解いていくことにも注力していこうと思います。

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

2022-01-27

AtCoder Beginner Contest 236 参加記

AtCoder 競プロ ABC

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

atcoder.jp

昨日のARCでは1完で冷えという残念な結果だったので、今回で盛り返しできるようにという気持ちで臨むことにしました。

Rated参加します。昨日のARCでは冷えてしまったので、連敗しないように頑張ります✊
AtCoder Beginner Contest 236 - AtCoder https://t.co/9fc6TmBmes
— devgenjin77 (@devgenjin77) 2022年1月23日

今回の結果

結果は4完。D問題に大分手こずってしまいました。。

それでも、肝心のパフォーマンスは水色まで出てくれまして、なんとかHighestを更新することができましたとさ。

4完でも水パフォが出て、Highest更新しました😂😂
来週の土日も頑張ります✊
devgenjin77さんのAtCoder Beginner Contest 236での成績：1449位
パフォーマンス：1309相当
レーティング：1022→1054 (+32) :)
Highestを更新しました！#AtCoder #ABC236 https://t.co/5kkSlPJqf5
— devgenjin77 (@devgenjin77) 2022年1月23日

振り返り

今回はDが解けるのと解けないのでは大分違う状況になりましたね。

A問題

A - chukodai

文字列 $S$ の $a$ 文字目と $b$ 文字目を入れ替えるだけの簡単な問題。

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

提出コード

https://atcoder.jp/contests/abc236/submissions/28721351

B問題

B - Who is missing?

配列 $A$ の中に、どの整数が何回出現したかを配列で管理し、最終的に出現回数が3だった数字を出力すればよい。

こちらも問題なくACが取れました。

因みに、コンテスト後の解説などを見ると、配列 $A$ の全部のxorを取ると答えになるということ。本番でこのような発想が出るようになりたいものですなー。

提出コード

https://atcoder.jp/contests/abc236/submissions/28729131

C問題

C - Route Map

配列 $T$ の要素を全部Setに突っ込んでから、 $S$ の要素について $T$ に含まれていればYes、なければNoを出力すればよい。

こちらも問題なくACを取ることが出来ました。

提出コード

https://atcoder.jp/contests/abc236/submissions/28735054

D問題

D - Dance

一目、あり得る全ての組み合わせについて、しらみつぶしに計算して最大値を求めればよいかと思われる。

ということで、計算途中でどの人が既に選ばれたのかを配列で管理しながら、DFSで探索して最深部で答えを計算するプログラムを組んでみる。

で、これがサンプルまで通ったものの、提出してみればあっさりTLEを喰らってしまう。うーむ、まさかD問題で詰まってしまうとは。。

メモ化して高速化が図れるのかとか、または別の考え方が必要なのかと色々考えてみるが解法は見えずというところでどんどん時間は過ぎてしまう。ちなみにこの時点での順位は3600ぐらいであり、このD問題を落とすとレート下げがほぼ確実であり、かなりピンチである。

で、あれこれ思案した結果、単純な全探索のDFSだと同種のペアも重複して数えてそうなので、ペアを作るときは小さいほうの番号から大きい方の番号にのみ探索をかけていくやり方に限定すればよいのでは思いつく。で、この改良をしたDFSもどきのプログラムでサンプルを通してみると、数段早くなっているようなので、提出してみたらやっとACをもらう事ができました。

このＤが通せた事で順位は一気に1300台まで上昇！なんと茶パフォになりかねないところから一気に水パフォぐらいまで上げることができましたとさ。

提出コード

https://atcoder.jp/contests/abc236/submissions/28750618

E問題

E - Average and Median

順位表からの情報では、今回のＥ問題は開始60分を過ぎてもＡＣ数が500足らずというところで、青Diffぐらいの問題なのかと。

一応、時間はあるので問題は見てみましたが、さっぱりわからずということで早々にこの問題は諦めました。

F問題

F - Spices

この問題も、E問題よりAC数が少ないということで、見る前から戦意が喪失しそうな問題でしたが、一応チラ見ぐらいはしておくことに。

しかし、結局何もわからずで諦めました。

G問題

G - Good Vertices

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

Ex問題

Ex - Distinct Multiples

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

これまでの実績

水色到達に向けて、また一歩前進することができました。

総括

今回はDが通せたか通せなかったかでパフォーマンスが大幅に変わるところでしたが、なんとか今回Ｄが通せたのは、良かったです。これも日ごろの精進のおかげかも知れません。

ただ、水色コーダ―になるためには、今回全く歯が立たなかったE以降の問題も取り組んでいけるように、水Diff以上の過去問に集中して取り組んでいくことが必要かなーと思います。

また次の土日も、ARC、ABCが連続であるようなので、平日も精進を続けていきます。

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

2022-01-24

AtCoder Regular Contest 133 参加記

AtCoder 競プロ ARC

2022/1/22に開催されたAtCoder Regular Contest 133に参加しました。

atcoder.jp

先週のコンテストは所用で参加できなかったのですが、今週は土日ともRatedコンテストが続くということで、先週参加できなかった分今週は連勝して帳尻を合わせようかなという気持ちで臨むこととしました。

Rated参加します。この土日で連勝できるように頑張ります！

AtCoder Regular Contest 133 - AtCoder https://t.co/gNov1Do6Xq
— devgenjin77 (@devgenjin77) 2022年1月22日

今回の結果

で、結果の方はというと、なんとか1完できましたという体たらくでした。。

それでもパフォーマンスは緑色まで取れており、結果としてはなんとかちょい冷えというところで勘弁してもらえました。

1完緑パフォで、ちょい冷えでした😭
結果は残念でしたが、明日もあるので気持ちを切り替えて復習に臨みます。
devgenjin77さんのAtCoder Regular Contest 133での成績：2008位
パフォーマンス：954相当
レーティング：1029→1022 (-7) :(#AtCoder #ARC133 https://t.co/AmbgC66FtZ
— devgenjin77 (@devgenjin77) 2022年1月22日

振り返り

B問題以降は歯が立たずでした。

A問題

A - Erase by Value

サンプルケースを眺めたところ、配列を先頭から見て行って、 $A_i \gt A_{i+1}$ となる $A_i$ を $x$ として定義すればよいかと考察。

また、そのような $A_i$ が存在しない場合は、 $x = A_N$ とすれば良いかと。

ということで実装して提出したものの、バグがあったようでWA。再度処理を見直してACを取ることができました。

提出コード

https://atcoder.jp/contests/arc133/submissions/28685237

B問題

B - Dividing Subsequence

一読して、解法がよく分からん手強そうな問題という印象。

とりあえず、サンプル入力を見て考えたところ、 $P_i$ を見たときに、 $i \ge j$ となる $j$ について $Q_j$ が $P_i$ の倍数ならば答えをカウントアップし、次から $Q$ を見るときは $Q_{j+1}$ 以降からみていくという、嘘くさい解法を考えてみる。

で、実装したらサンプルまでは通ってくれたものの、やはり嘘解法だったようで提出したらWAとTLEのダブルパンチを食らってしまいました。。

やはりこの問題は何らかの典型アルゴリズムの知識が必要かとおもい、LCSのアルゴリズムをググってみたりとか色々悪あがきをしてみるが付け焼き刃の知識ではどうにもならず。

結局、この問題であれこれ考えている途中で時間切れとなりました。

C問題

C - Row Column Sums

こちらの問題も、目を通してみるものの何もわからず。とりあえず順位表からみると難易度も相当高そうなので早々に諦めとなりました。

D問題

D - Range XOR

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

E問題

E - Cyclic Medians

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

F問題

F - Random Transition

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

これまでの実績

1完だった割には、爆死は免れました。

総括

2022年最初のARCは1完で冷えという残念な結果でしたが、これも青Diff程度の問題にまだまだ取り組めておらず、アルゴリズムの知識がまだ足りないというのが原因かと。

今年は、水色コーダーになるという目標を立てているので、なんとか今回のB,C問題は復習をし、次回同様な問題が出たときに対応できるようにしていこうと思います。

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

2022-01-10

AtCoder Beginner Contest 234 参加記

AtCoder 競プロ ABC

2022/1/8に開催されたAtCoder Beginner Contest 234に参加しました。

atcoder.jp

2022年最初のABCコンテストになります。今年は昨年より競プロに力を入れて、どんどん上を目指していきたいので、今回はとりあえずレート上げを達成して初回のコンテストを終えられるようにという気持ちで臨むことにしました。

Rated参加します。2022年最初のコンテストは好結果で終えて良いスタートを切りたいもんですな。
AtCoder Beginner Contest 234 - AtCoder https://t.co/tI9ntY6RYQ
— devgenjin77 (@devgenjin77) 2022年1月8日

今回の結果

んで、今回の結果は5完。E問題に大分時間を取られたので、タイムは大分遅めだったという印象です。

パフォーマンスは緑の上位。とりあえずレートを上げることはできたので、最低限の目標は達成しました。

5完緑パフォでレート上げ！
この調子で今年中に水色行けるように頑張ります✊
devgenjin77さんのAtCoder Beginner Contest 234での成績：1887位
パフォーマンス：1116相当
レーティング：1019→1029 (+10) :)
Highestを更新しました！#AtCoder #ABC234 https://t.co/0XtED2Zi9t
— devgenjin77 (@devgenjin77) 2022年1月8日

振り返り

D問題までは順調にいってましたが、E問題でやたらと時間を取られてしまいました。

A問題

A - Weird Function

関数 $f(x)=x^{2}+2x+3$ を定義し、関数を再帰的に呼び出して答えを求めるという問題。

問題文のとおりに実装し、ACを取ることができました。

提出コード

https://atcoder.jp/contests/abc234/submissions/28381813

B問題

B - Longest Segment

二点間の距離の最大値を求める問題。制約上の最大は $N=100$ であり計算するパターン数としては最大でも $100 \times 99$ 程度なので、２重ループの実装で問題なし。

こちらも問題なくACが取れましたとさ。

提出コード

https://atcoder.jp/contests/abc234/submissions/28388630

C問題

C - Happy New Year!

入力例2を参考に愚直に小さい方から数え上げてみると、 $2,20,22,200,202,220,222,2000,2002,2020,2022$ という感じで確かに $2022$ が11番目に小さい数字となる。

で、よくよく考えるとこの数字の動き方が2進数を小さい方から数え上げたものに対して1を2に置換しただけのように見える。

確かに、11を2進数にすると1011となるので、結局答えは、入力を2進数の文字列に変換し、1を2に置換すればOK。

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

提出コード

https://atcoder.jp/contests/abc234/submissions/28391968

D問題

D - Prefix K-th Max

この問題は、もう少し単純に考えればよかったかと後悔しました。

先頭から愚直に $K$ 番目に大きな数値を求めようとすると、TLEになりそうなこの問題。ということで先頭からでなく、配列の一番後ろまで先読みする方法が有効ではないかと思い付いた。

$i = N$ の場合、 $K$ 番目に大きな値は $N - K +1$ で確定。この値を $Kth$ として定義し、解答用の配列に追加
順列 $P$ を後ろから見ていく。 $P_N$ を参照し、 $Kth$ より大きい場合は、現在の $Kth$ を使用済みの数値の集合 $S$ に追加し、 $Kth$ は集合 $S$ に含まれない値になるまで1ずつマイナスしていく。 $Kth$ が確定したら、解答用の配列に追加。
2の処理の要領で $P_{N-1}$ から $P_K$ まで順次処理する。
解答用の配列を、後ろから出力していく。

途中色々試行錯誤したが、出来上がった解法としてはこんなもん。結果として多少時間はかかりましたが、これでなんとかACを取ることが出来ました。

ただ、コンテスト後によくよく考えると、TreeSetを使って最小値を管理する方法の方がシンプルに実装できたかなーと反省。すこし問題を難しく捉えすぎたきらいもあります。

提出コード

https://atcoder.jp/contests/abc234/submissions/28401425

E問題

E - Arithmetic Number

等差数というのが、一般的な用語なのかよくわからんかったのでググってみるも等差数列の結果しか出てこない。。

ということで、過去問とか典型の類は当てにならないだろうということで、自力で考えてみることに。

で、よくよく考えると、 $1$ から $10^{17}$ ぐらいまでに存在する等差数なるものは多くはないと思われるので、とりあえず前計算で等差数を全部出してからソートを行い、 $X$ 以上の最小の等差数を求めればよいのではと考えた。

で、どうにかして実装をしてみたものの、これが無限ループやOutOfMemoryになったりと散々な結果に。。実は等差数って結構いっぱいあるのでは？？

しかも順位表から見るにこの問題、やたらとACが多く、これを落としてしまうと緑パフォすら怪しくなるという感じ。

このE問題は絶対に通しておきたいところですが、算出する等差数の桁数を限定してみたりなどしてみたものの、無限ループは治らずで、解決方法がわからずのまま、どんどん時間が過ぎていきました。。

で、よくよく確認してみると、ループ内の処理が盛大にバグっていることが判明するというオチ。。

なんやかんやで、実装からバグ治しまで40分程度かかってしまうことになりましたが、結局当初の解法でなんとかACを取ることが出来ましたとさ。

提出コード

https://atcoder.jp/contests/abc234/submissions/28412322

F問題

F - Reordering

15分程度しか残っていない状態でしたが、問題を読んでみることに。しかし、解法は全く思いつかずで、結局時間切れとなりました。

これは後日解説ACしておこうと思います。

G問題

G - Divide a Sequence

問題はチラ見してみましたが早々に諦め。

Ex問題

Ex - Enumerate Pairs

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

これまでの実績

2022年はHighest更新という良いスタートを切れました。ここからなんとか水色を目指して頑張っていきたいです。

総括

今回は5完をキープ出来たというところでしたが、D問題はもっとシンプルに考えることはできたし、E問題は盛大にバグらせて時間を無駄にしたりなど色々と反省も多い回でした。

順位表から見ると、5完60分で水色パフォまで出たというところみたいだったので、今後はどうすれば早く正確に解けるかというのも考えていかないといけませんね。

当面は、水色コーダーになることを目標にするので、まずは過去問の青Diffまでの問題を解くことと、数を多く解いて実装力を高めるということをやっていこうと思います。

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

2021-12-29

AtCoder Regular Contest 132 参加記

AtCoder 競プロ ARC

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

atcoder.jp

2021年最後のRatedコンテストなので、とりあえず目標はレート上げ。気分良く今年の締めくくりができればという気持ちで臨むこととしました。

Rated参加します。今年最後のコンテストなので、レート上げで終えられるように頑張ります。
AtCoder Regular Contest 132 - AtCoder https://t.co/gD7DHgjA5N
— devgenjin77 (@devgenjin77) 2021年12月26日

今回の結果

で、肝心の結果ですが、なんとか2完が確保できたというとこです。

パフォーマンスは、現レートよりちょい悪というところでして、結果としてはレート-1というなんとも中途半端な内容となってしまいました。

2021年の締めくくりは、2完でちょい冷えといういうなんとも微妙な結果となりました。😅
来年頑張ります✊
devgenjin77さんのAtCoder Regular Contest 132での成績：1402位
パフォーマンス：1017相当
レーティング：1020→1019 (-1) :(#AtCoder #ARC132 https://t.co/zSF3kP92j6
— devgenjin77 (@devgenjin77) 2021年12月26日

振り返り

B問題をめちゃくちゃ苦労してなんとか通すことが出来ました。

A問題

A - Permutation Grid

一読して、初手から解法がよく分からん問題がきたかという印象。制約条件より、2次元配列を生成して中身を埋めてから実行するというのも大分苦しそうである。

それでも、A問題からいきなり諦めるわけにはいかないということで考察をしていく。まずは条件を満たす塗り方がちょうど一通り存在するということで、各条件においてどういう塗り方となるかを考えると、 $R_i$ と $C_j$ が $n$ の行と列は全て黒で確定し、その次に、 $R_i$ と $C_j$ が $1$ の行と列について、先に塗ったマス以外は全て白で確定することはわかった。

次に同様の要領で、 $R_i$ と $C_j$ が $n - 1$ の行と列、次に $R_i$ と $C_j$ が $2$ の行と列という具合に塗る色のが特定できる。この要領でサンプルケースを実際に塗ってみると、以下のように問題文の説明と同様の塗り方ができる。

 42315
5#####
2#...#
3#.#.#
4###.#
1....#

後はこの図を見た時に、白のマスと黒のマスでなんらかの法則性があるかを見てみると、どうも黒のマスのみ $R_i + C_j$ の値が大きくなりそう。ということで、答えは $R_i + C_j \gt n$ の場合は黒、それ以外は白ということでした。

あとは実装して、ACを取ることができました。

提出コード

https://atcoder.jp/contests/arc132/submissions/28171316

B問題

B - Shift and Reverse

こちらも一読して、解法がよく分からん問題がきたかという印象。考えてはみるものの何も分からずで時間だけが溶けていきました。

で、30分以上あれこれと考えてみたところ、問題文の操作で並び替えができるのは元々昇順で並んでいる数列を何回かシフトするか、一度だけ逆順にひっくり返すリバース操作を行ったものなので、配列中の $1$ の位置と、全体として昇順、降順どちらで並んでいるかという事に着目すればよいというのがやっとのことでわかりました。

で、元の入力が昇順の場合は、 $1$ が先頭になるまでシフトするか、一度リバースした後 $1$ が最後尾になるまでシフトして再度リバースする操作のどちらかで、操作回数が少なくなるものを選択すれば良い。

また、元の入力が降順の場合は、 $1$ が最後尾になるまでシフトしてからリバースする操作か、先にリバースをしてから $1$ が先頭になるまでシフトする操作のどちらかで、操作回数が少なくなるものを選択すれば良い。

とここまで考察するのに小一時間かかってしまったのですが、あとは実装をするのみ。なんどかバグらせてWAを出したのち、やっとのことでACを取ることが出来ました。

前回より大分遅めの、開始100分弱で2完達成です。

提出コード

https://atcoder.jp/contests/arc132/submissions/28177702

C問題

C - Almost Sorted

残りが20分程度あったので、問題には目を通してみたものの適切な手法が思いつかずでした。

D問題

D - Between Two Binary Strings

ワンチャンあるかと思い、問題だけは覗いてみたものの何も分からず。

E問題

E - Paw

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

F問題

F - Takahashi The Strongest

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

これまでの実績

2021年最後のRatedコンテストは、やたら苦労した挙句にレート-1というなんとも微妙すぎる結果となりましたとさ。

総括

今回のARCでは、AB問題もすぐには解法が見出せずで、苦労させられました。そんな中でも諦めずに地道に問題に取り組むことでなんとか最低限の結果は確保できたのは、それなりに自分が成長した結果なのかという感じが致します。

今年1年間AtCoderに取り組んだ結果としては、レートが200少々上がったという結果でした。途中競プロに取り組めない時期もあり、レートがダダ下がりになる時期がありましたが、後半にかけて精進を継続することでなんとか巻き返しが出来たのは非常によかったですね。

来年も精進を継続して、少しでも上の色、レートに到達できるようにしていこうと思います。

ということで、また来年も頑張ります。