AtCoder Regular Contest 170

1完2WA

各問題

A - Yet Another AB Problem

気合の if 文...

前からみていって、S, T が

• ともに A
  • なにもしなくてよい
• A と B
  • S の B をすでに A に変換している
    • それを一つ消費することでコストなしで変換可能
  • そうでなく、そこまでに S が A のときがある
    • その A を A に変換、この A を B に変換することで変換可能、コスト1追加
  • 上記のどれにも当てはまらない
    • 詰み
• B と A
  • とりあえず A に変換する
    • あとで B に変換する部分が存在する必要がある
• B と B
  • なにもしなくてよい
    • B に変換する必要が生まれていた場合、ここで消費できる

というようなロジックでなんとかなりました。

最初、BA -> AB の変換と思い込んでいて 2WA。

B - Arithmetic Progression Subsequence

A_i - A_j の組がいくつあるかを記憶しながらの尺取りで何とかなるかと思いましたが、間に合わず。

終了20分前まで見当違いのロジックを組み立てていたのが敗因...。

まとめ

A は問題を、B はロジックの組み立てを勘違い、これでは勝てません。

トヨタ自動車プログラミングコンテスト2024#1（AtCoder Beginner Contest 337）

5完4WA2RE

各問題

A - Scoreboard

集計して比較します。

B - Extended ABC

ABC順に並んでいるかをチェックしていけばいいのですが、空文字も拡張文字列として認められるので、AC とか B などでもOKであることに気をつける必要があります。

自分は見逃していて 1WA と修正をミスしてさらに 1WA...。

C - Lining Up 2

人 i が A_i の後ろに並んでいるということは A_i の後ろに並んでいるのは i なので（進次郎構文みたい...）それを表す B[a[i]] = i となるような B を作って、A_i = -1 となる i を先頭に B から次の人を引いてくればよいです。

いつもはこれを利用した問題が出るイメージですが、今回は単体で出ましたね。

D - Cheating Gomoku Narabe

一つ一つの判定が O(1) でできれば全体で O(HW) で解けます。‘H ＊W <= 200000` なのでそれで充分です。

K個分の o と x を集計して、それを一つずらしたときに o x の増減を更新するようにしていき、x が 0 のとき K - o の個数が必要な変換数としていけば解くことができます。

実装をバグり散らかし 1WA2RE とか...。

E - Bad Juice

呼び出す友達を2進数の各ビットだと思って、友達 i は 1 << (i - 1) と AND を取った時に non zero となる番号のジュースを飲ませることにすれば、最少人数を達成できます。なお飲ませるジュースは N-1 番目まででよく、だれもおなかを壊さなかったら N 番目が腐ってるとすればよいです。

上記 1 << (i - 1) の部分を単に i にしていたというしょうもないミスで 1WA。

まとめ

余裕で青パフォあったはずなのに、ミスを連発でちょい浮きどまり...。かなしい。

AtCoder Beginner Contest 336

4完1WA

各問題

A - Long Loong

cout << "L" << string(N, 'o') << "ng" << endl;

B - CTZ

「2 で割った余りをとる -> 1 なら終了、0 なら 2 で割る」を繰り返して、あまりが 0 だった回数が答えです。

C - Even Digits

N - 1 を５進数に変換して、それを2倍したもの、が答えです。N - 1 なのは、1番目が 0 なので。

D - Pyramid

左右両方について、各位置がサイズいくつの頂点となりうるかをチェックしていき、

チェックの方法は、ある位置がいくつの頂点になりうるかを f(x) としたとき、f(i - 1) < a[i] ならば f(i) = f(i) + 1 で、そうでないなら f(i) = a[i] となります。

E - Digit Sum Divisible

OEIS にはあるのですが、だからといってそれが答えに結びつくとは限らない...。

まとめ

D が第一感でわからなかったので、E を OEIS で見つけたので（D より先に）頑張って何とかしようとしてしまったのが敗因。

後で落ち着いて考えたら D すぐ思いつけた...。

AtCoder Beginner Contest 335（Sponsored by Mynavi）

4完

各問題

A - 2023

いわれたとおりやりましょう。

B - Tetrahedral Number

全探索しましょう。

C - Loong Tracking

龍が動くとき、パーツ i は もともとパーツ i - 1 があったところに移動します。

各パーツの座標を deque で管理しておけば、最後尾を削除 -> 先頭にパーツ 1 の移動先を挿入、とすることで移動をエミュレートすることができます。

D - Loong and Takahashi

左上から中心に向かって渦を巻くようにパーツを置いていけばよいだけです。発想は C より簡単な気がする。実装は方針にもよりますが C より面倒かも。

E - Non-Decreasing Colorful Path

最初トポロジカルソートすればいいのではと思ったのですが、「広義」単調増加だから頂点の数値が同じものがつながっているとループしてしまうので DAG じゃなかった...。

単純に DFS でやろうとすると、たくさんの頂点が同じ数値を持ってつながっていた場合に終わらなくなるのでだめ...。

というわけで解ききれませんでした。

まとめ

E 解ききれなかったのは残念ですが、配点から D まで早解きできれば OK だと思っていたのでとりあえず目標はクリアというところ。

ユニークビジョンプログラミングコンテスト2023 クリスマス (AtCoder Beginner Contest 334)

ABDE の 4 完、2WA

各問題

A - Christmas Present

比較してください

B - Christmas Trees

超難問。（うそ

左側の人がツリー上に立っている場合と立ってない場合で場合分けしました。

立っている場合は (R - L) / M + 1 でよく、立っていない場合は左側の人の左に立っているツリー上（L' とする）にいるとみなして (R - L') / M でよいです。

算数で苦しみ、剰余の計算で苦しみ、単純な実装ミスで苦しみ、最終的に解けた問題の中では一番時間をかけた挙句 2WA。

C - Socks 2

一枚しかない靴下どおしをペアにすればよく、二枚揃っているものはそのままでよいです。例えば 1 と 4 が一枚しかないときに、(1,2), (2,3), (3,4) とするのも (1,4), (2,2), (3,3) とするのもともに 3 で変わらないです。

で、わざわざ遠いものをペアにしても得しないので、隣り合うものがペアになると考えてよいです。

偶数の時は一通りなのでいいとして、奇数の時はどれか一つ余りますが、両側から距離の累積和をとって余らせるやつの左右の分を合算するとよいです。

B 通した時点で15分弱しか残っておらず、解法に気づいたときには5分を切っていて、結局間に合わず。

D - Reindeer and Sleigh

R はソートして累積和を作り二分探索するだけです。

C より簡単にみえる...。

E - Christmas Color Grid 1

dsu で初期状態の連結成分を管理します。赤のマスを緑に変えたとき、連結成分の個数は「隣り合う連結成分の数 - 1」だけ減ります。

その連結成分の個数はleader をチェックすればすぐわかるので、各赤マスごとに全体の連結成分数がいくつになるかも簡単に求められます。

まとめ

B, C でハマるのを本当に何とかしたい...。

トヨタ自動車プログラミングコンテスト2023#8（AtCoder Beginner Contest 333）

5完

各問題

A - Three Threes

こんなかんじで。

for (int i = 0; i < n; i++) cout << n;

B - Pentagon

abs(S[0] - S[1]) と abs(T[0] - T[1]) を計算して、どちらも 1 or 4 のとき、どちらも 2 or 3 のときは距離が等しいです。

C - Repunit Trio

priority_queue に（符号を逆転させて）入れて、一番大きい（元の値は小さい）ものを取り出してそこに 1, 11, 111 を足して priority_queue に入れる、を繰り返して取り得る値を作っていく典型のやつです。

1の位が3のときが3つの和になのでそれを答えの候補とします。

D - Erase Leaves

頂点1をルートとして、それにぶら下がる部分木のうちでいちばん頂点数が多いものを残して他を削除していくのが最適なので、部分木の頂点数を DFS などで数えます。

E - Takahashi Quest

ポーションはできるだけ持っている期間を短くしたいので、モンスターに一番近いものを拾うようにします。

クエリを後ろからみていくことで、モンスターに対して一番効率のよい（一番モンスターに近い）ポーションがどれかがわかるようになります。ポーションの保持数は、後ろから見た場合だとある時点で倒せていないモンスターの数と同じになります。

クエリを最初までさかのぼった時に生存しているモンスターがいた場合、敗北決定です。

F - Bomb Game 2

数学弱者すぎて、入力例1が 1/3 と 2/3 になるということがそもそもわからないという...。

まとめ

C の実装でまごついてしまった（queue から pop し忘れてただけ...）のでちょっともったいなかったですが、Eまですんなり解けたのでまあまあいい結果になったのではないでしょうか。

あすの AGC に向けていい貯金ができました。

AtCoder Beginner Contest 332

4完

各問題

A - Online Shopping

計算しましょう。

B - Glass and Mug

問題文の通りに場合分けを頑張って実装しましょう。

C - T-shirts

後ろから必要なTシャツの数を数えます。0がきたらリセットします。（あれ？前からでもよかった？

食事に行くときに無地のTシャツが足りなければその分ロゴ入りTシャツを購入する必要があることに注意です。

D - Swapping Puzzle

行の入れ替えと列の入れ替えは独立して考慮可能です。また、任意の順に入れ替えることができます。

で、H, W がたかだか5なので全探索可能です。転倒数も O(N²) で求めて構いません、たかだか5なので。

E - Lucky bag

なんもわからん。

F - Random Update Query

O(N²) でいいんならとける？

まとめ

D であまり詰まらなかったのでちょい勝ち。最初に全探索を考えなかったのはだめ。