Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Regular Contest 140

2完、8WA。やりすぎたー。

各問題

A - Right String

ある文字列Uの繰り返しの形にできれば、種類数はUの長さLにすることができます。Uの繰り返しにするためにはL文字間隔で同じ文字が出現すればよいです。 つまりabcabcabcなら、長さ3の文字列abcの繰り返しで、1文字目と1 + 3 = 4文字目と1 + 3 * 2 = 7文字目がa、2文字目と2 + 3 = 5文字目と2 + 3 * 2 = 8文字目がb、という具合です。

Nは2000までなので2重ループは許されます。なので、f(S) = 1から順にNまで調べていけばよいです。ただし、Nの約数でないと答えには当てはまらないので注意です。

B - Shorten ARC

AARCCは、奇数回目からなら ARC -> AC と変換することができます。AAARCCCは、単体では AARCC -> AACC と2回止まりですが、別の場所で偶数回目を消費することで AARCC -> (偶数回目を別の場所で消費) -> ARC -> AC と消費し切ることができます。この偶数回消費は ARC が単体で出ている場所でやれば得できます。

というわけで、A...ARC...C 型と 単体で出現するARC 型を分けて集計して、うまいこと消費回数を数えれば答えがわかります。(雑

C - ABS Permutation (LIS ver.)

適当な貪欲を投げるも、当然通らず。

まとめ

AもBも、考察ははずしてないんだけど詰めが甘くてWAを量産してしまい、水パフォキープにとどまってしまいました。

パナソニックグループプログラミングコンテスト2022(AtCoder Beginner Contest 251)

3完...。

各問題

A - Six Characters

Sが1文字なら6連結、Sが2文字なら3連結、Sが3文字なら2連結して出します。

一般化するとSを6 / |S|連結して出します。1も2も3も6の約数なのでこの一般化が可能です。

B - At Most 3 (Judge ver.)

Nがたかだか300なので、入力を受け取るときに1つの和、2重ループで2つの和、3重ループで3つの和を求める全探索が可能です。和がW以下になったときだけsetに入れて、setの要素数を答えればいいでしょう。

C - Poem Online Judge

setにSを入れていってオリジナルかどうかを判定、オリジナルならそれがそこまでの最優秀かどうかを判定、とすればよいです。

Bより楽...。

D - At Most 3 (Contestant ver.)

なんだこれ...。

なんかN進法的なことをやるのかと思ってみましたが、全然それらしい答えに近づくこともできず。

解説を見ると、N進法という観点は間違ってなかったようでですが、100進法なのかー。いわれてみればそれはそうなのですが、それは思いつけなかった...。

E - Tahakashi and Animals

順位表を見ると、Dに見切りをつけてEを通す人がどんどん増えてきたので自分もそうしようとしましたが、解けず。

いやDPなのかー。これは解かないといけなかった...。

まとめ

惨敗...。明日のARCがんばりましょう。

AtCoder Regular Contest 139

1完、29:37。

各問題

A - Trailing Zeros

以下、0オリジンで。

  • xに対して、T_iだけ下位ビットを0で埋める
    • ctz(A_i) = T_i を満たすため
  • xに2^T_iを加算する
    • 0埋めした後のxは元のx以下なので、狭義単調増加の条件を満たすため
    • 演算後の数値は少ないに越したことはないので、末尾のT_i個を0埋めした数値で最も小さい2^T_iを加算
  • T_iビット目が0だった場合、それを1にする
    • ctz(A_i) = T_i を満たすため

以下をNまで繰り返してできたxが答えです。

B - Make N

ARCの500だし、そんな解法でいけるわけないようなぁと思いながら貪欲っぽいものを投げるも、案の定WAでした。

しかも予想外にWAが多い(35/36がWA)し、順位表を見ても全然解かれていないので、ほぼほぼ諦めの状態でした。

まとめ

ARCの500点問題がさっぱり解けないようになってしまいましたなぁ...。

モノグサプログラミングコンテスト2022(AtCoder Beginner Contest 249)

4完。

各問題

A - Jogging

算数をすれば解けるのは分かるのですが、自分の算数力を悲観しすぎてしまいループを書きました。

ただ、効率的なアルゴリズムが思いつかず、A問題なのに地獄のようなコードに...。今日通したDまでの中で一番複雑なコードになってしまいました。

B - Perfect String

文字の出現数を愚直に集計して、条件に合うかをチェックするだけです。

C - Just K

ビット全探索。

D - Index Trio

各数字の出現数をまず取ります。それぞれの数字に対して約数を求めて、約数毎に組み合わせの数を計算すればよいです。

まとめ

Aで激冷えを覚悟したわりに、Eが崖だったので水パフォ中位まで取れてホッとしました。

いや、Aをちゃんと算数してたら青パフォやん...。

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

5完3WA2TLE。

けんちょんさん (@drken1215) の有理数ライブラリのおかげで命拾いしたー。

各問題

A - Lacked Number

0から9までのバケツ(要するに要素数10の配列)を作って、与えられた数字を一つずつ確認してバケツに入れて(つまりa[数字]を+1して)いき、最後に空っぽのバケツが一つあるはずなので、それが答える数です。

後から気づいたのですが、9文字の中に0があるか確認、1があるか確認、... と9まで全探索すればよいだけでした。(たいして実装内容に差はありませんが)

ところで、バケツの中身を確認する処理で、9を確認するのを忘れており1WA出しました。(あほ

B - Slimes

AをBを超えるまでK倍していきます。何回K倍したかが答えです。K倍した結果がintに収まらない可能性があるので注意です。

C - Dice Sum

複雑そうな問題文ですが、要はN×KのDPをするだけです。最終的な答えはΣdp[N-1][i]です。

D - Range Count Query

A_iの値ごとに、出現したインデックスを配列で持ちます。クエリ毎にLとRの間に含まれているインデックスが該当するインデックスなので、それを数えるためにLとRで二分探索します。

WAやTLEを出してしまったので、配列が空のとき二分探索しないようにしたら通りました。まじか...。

E - K-colinear Line

まず、K=1のときは必ずInfinityです。それ以外でInfinityはないので以下K=2の時を考えます。

2点間の傾きとy切片のペアを全探索して、同じペアを持つi, j をsetで管理します。要するにmap<pair<傾き, 切片>, set<int>>を作って管理です。(ただしx=a型の直線の場合は傾きが求められないため例外として、傾きと切片ではなくx座標だけで別に管理します)

setの中身がK以上の直線がほしい直線なので、その数が答えとなります。

ところで、傾きや切片をdoubleなどで持って実際に計算してしまうと誤差で死んでしまうので(これで1WA)、有理数で持ちます。

しかし、まだ自分は有理数ライブラリを作っておらず、その場で頑張って実装しようかと思いましたが諦めてググったところ、けんちょんさんの有理数ライブラリがヒットしたので拝借したら、無事通りました!

drken1215.hatenablog.com

感謝感激。

F - Keep Connect

どう見ても解けそうにないので諦め...

まとめ

いやー、Dで詰まったときはどうなるかと思いましたが、Eが通せて助かりました。有理数ライブラリは作らないとなーと思いつつ作れてなかったんですよね...

f:id:mdstoy:20220416230714p:plain

AtCoder Beginner Contest 247

4完2WA。

5ヶ月ぶりに緑落ちでございます。

各問題

A - Move Right

"0s[0]s[1]s[2]" を出力。

B - Unique Nicknames

Nが100なので、各人について「他の人の」姓名と一致しないかどうか全探索すればよいです。

自分は、全探索が思いつかず、これ難しすぎないかと思って先にCDを通してから戻ってきました...。

さらにようやくひねり出した解法でmapを使って実装したところ、自分の姓と名だけが同じのパターンを"No"としてしまい、1WAという。

C - 1 2 1 3 1 2 1

整数の配列でやるとめんどうくさそうなので、文字列で、"1" -> "121" -> "1213121"とやっていき、出力するときに一文字ずつばらします。

ただし、Nが10以上になると、"(S9)10(S9)"となってしまい、10が1と0にバラされてしまうので、10から16までは適当に一文字に変換しておき、出力するときに元の数字に戻します。(これをうっかりして1WA)

D - Cylinder

dequeを使って愚直にシミュレーションすれば何の問題もないです。

E - Max Min

しゃくとり法だとは思ったのですが、どこにどうやって適用すればよいのかわからず...

F - Cards

なんか解けそうな見た目をしていたので、Eよりこっちかなと思ってしばらく粘ってみましたが、錯覚だったようです。

まとめ

Bで思い切りつまずいたのが痛すぎて、緑に落ちてしまいました。なんか毎年春にパフォーマンス落ちてるような気がするんですが、気のせいでしょうか...。

f:id:mdstoy:20220410235801p:plain

AtCoder Beginner Contest 246

4完2WA。

晩御飯は居酒屋でした...。

各問題

A - Four Points

示されたxとyそれぞれの3つは、同じ値が2つと異なる値が1つになるので、それぞれの異なる値を出力すればOKです。

B - Get Closer

純粋な数学問。atan2で角度を求めて、sinとcosで座標を求めます。

...どっちもググりました。

C - Coupon

まず、無駄が出ない範囲(X円のクーポンをX円未満に対して使わない)でクーポンを使えるだけ使います。

それでもクーポンが余る場合、余った金額の多いものから順にクーポンを使っていきます。前半部分でクーポンを適用した後の金額をpriority_queueに入れておけば楽です。

D - 2-variable Function

まず、与式をぐっと睨むと式変形すると、aとbは106以下であることがわかります。なのでaを全探索、bは二分探索で求めれば十分間に合います。

しかし、全探索する範囲も二分探索する範囲も適切に与えることに失敗し、2WA。

E - Bishop 2

ただのBSFを書くと、TLEします。ダイクストラしようとすると、メモリも足りません。

コンテスト終了2分前に、同じ方向に何度も移動するのはむだなので方向を持たせる必要があることに気づきますが、ときすでに遅し...。

まとめ

水パフォには届きませんでしたが、飲酒後の参加で大怪我しなかったのでまあいいか、という感じです。ていうか、酔いさめちゃったw

f:id:mdstoy:20220402231728p:plain