AtCoder Beginner Contest 244

5完。

各問題

A - Last Letter

cout << S[N - 1] << endl;

B - Go Straight and Turn Right

現在の向きと座標を持って、愚直にシミュレートします。

C - Yamanote Line Game

ABCで初めてインタラクティブ問題解いた気がする...。

どの数が宣言済みかを保持しておいて、まだ宣言されていない数を返します。やること自体はC問題のレベルじゃないので、インタラクティブってだけでここに置かれた感じ？

D - Swap Hats

並べ方は6パターンありますが、数巡シミュレートするとそのうちの3こずつが交互に現れるだけとわかります。よって、偶数回目に現れる3パターンのうちのどれかならYesでそうでないならNoです。

E - King Bombee

制約がいかにもDPっぽくて、実際DPで解けます。

DP[K][N][2(Xの出現回数のパリティ)]でDP[0][S][0]=1 / その他 = 0を初期値として木上で配るDPをすればよいです。Xを通るときパリティが変わることに注意です。

F - Shortest Good Path

たとえば111なら110, 101, 011のうちから一番少なくて済むものを選べばよさそう、それを000から再帰的にやればよさそうと思って再帰を書いていたのですが、1が少ないものから順に処理する必要があるのでBFSじゃないか？と気づいたのが終了15分ほど前で、必死に実装を書き直すも間に合わず...。もったいなかった。

まとめ

先週失ったレートをあらかた取り戻したのでよしとするべきか、見えてた6完をみすみす逃してしまったことをだめとするべきか...。

AtCoder Beginner Contest 243

3完。惨敗。

各問題

A - Shampoo

愚直にシミュレートします。一昔前ならB問題でもおかしくないレベルだと思うんですが...。

B - Hit and Blow

Nが1000までなので、全探索できます。恥ずかしながらそれに気づくのに遅れてもたつきました。

C - Collision 2

まず、y座標が同じ点同士しか衝突の可能性はありません。で、各y座標について、「Lの点のx座標が最も大きいもの」＞「Rの点のx座標が最も小さいもの」を満たせば衝突することになります。

D - Moves on Binary Tree

計算過程をうまく持たないと数値が爆発してしまう可能性がありますが、最後までわからず...。

E - Edge Deletion

ワーシャルフロイドする前とした後の行列を比較して、変わった辺は削除可能、みたいにしてやってみたのですが、数割がWA。連結していないといけないことに終了5分前に気づき、dsuを使った実装を気合で書きましたが間に合わず。

まとめ

Dを諦めるのが遅かったかなー、すぐに見切ってたらE間に合ったかもなー、という感じでした。

今年初の3桁パフォとなってしまいました。まあたまにはこういうこともあります。いやでもレート-40は厳しい...。

AtCoder Beginner Contest 242

4完。

各問題

A - T-shirt

単純な算数の問題で、XがA以上なら確率は1、XがAより小さくB以上なら確率はC / (B - A)、それ以下なら確率は0です。

B - Minimize Ordering

問題文を言い換えると「Sを昇順にソートして出力しなさい」となります。文字列をソートできる言語ならそれを実行するだけです。

C - 1111gal password

DPするだけです。1-9までの初期値が1でスタートすることに注意。あと、DPのテーブルの幅は11取っておく（番兵をつくる）と、if文が不要になって楽です。

いやもうCでDP解かされるの当たり前になってきましたね...。

D - ABC Transform

t, kの位置からさかのぼっていくと、tが0になるかkが1になるかまでの回数がたかだかlogkなので、位置を保存しつつさかのぼっていって、保存した位置を使って復元していきます。

さかのぼっていった結果、tが0でないときはt%3を見ることで文字が確定できます。また、復元するときは位置の偶奇で次の文字が確定できます。

E - (∀x∀)

Dにほとんどの時間をつぎ込んでしまい、桁DP？いや違うな、と思ったところでタイムアップでした。

感想

Dの考察がなかなかうまくいかず、そこだけで76分使ってしまい残念なことに...。

かろうじて水パフォをキープできましたが...。

AtCoder Regular Contest 136

1完、3:22。

ほぼ2時間椅子を温めているだけのやつ・・・。

各問題

A - A ↔ BB

AをすべてBBに変換してから、前から順にBBをAに変換すればよいです。BABB -> BBBBB -> AABみたいな感じで。

B - Triple Shift

O(N²)が通りそうなので貪欲にやります。（距離2は移動させるだけ、距離1の移動は移動させたあと、後ろの二つをswap）

しかしこれでは5つほどWAが出ます。

最後まで解決できず終わりました。on_

解説を見ると、distinctでない場合必ず構築できると書いてあります。その条件を付け足すと・・・、通りました。まじかよ。

まとめ

Aが瞬殺できたので水パフォに踏みとどまれましたが、なんとも残念な感じです。

MC Digital プログラミングコンテスト2022（AtCoder Heuristic Contest 008）

システス後10,185,820,181点で、358位という結果になりました。

一応、正の点数を得た参加者のうちで真ん中より上には入れたようですし、大したことができなかったにもかかわらず水パフォだったようです。

経過

例によって、Scrapboxで思考をまとめていたのでそこからのコピペです。

• 初手
  • 全員ステイ
  • 2,041,339点
• 得点の計算式
  • 各人の満足度の平均
  • 満足度は
    • 追い出せなかったペット1匹毎に半減していく
    • 通過可能スペースが1減る毎に0.1%くらい減少？（多分）
  • どうすればいい？
    • 通過可能スペースを多く残すことよりはペットを追い出すことを優先したほうがはるかによさそう
    • 10あったスペースが追い出すことで4にしかならないなら追い出さないほうが得だが？
      • レアケかなぁ？
• （1.5手目）
  • 盤面をクラス化
  • intの二次元配列で持って、各座標はビットで管理
    • 0〜19が立っていたらペット、20〜29が立っていたら人、30が立っていたら壁
    • 重なりに対応できる
• 2手目
  • 人は動かさず、周りを囲う
    • 通過可能スペースは囲いきれた場合、1になる
  • 11,117,605点
    • これで伸びるので、とにかくペットを拒絶するほうがやはりよさそう
    • まとわりつかれた場合、囲いきれないのでその人のスコアは取れない
    • ちなみに提出時点で同点の人がいなかった
      • 誰でも考えつきそうなアイデアなのにな
      • たぶん自分の実装がまずくて囲いきれてないときがあったっぽい
• 3手目
  • 縦移動は行わず、ただ横に仕切っただけ
  • 279,015,861点
    • 伸びたなー
• 4手目
  • 縦移動して、人の間隔を等間隔に
  • 316,488,777点
• 5手目
  • 一番上の人は狭いスペースに閉じ込められてしまっていたので、とりあえず壁を作らないようにした
  • 337,361,052点
• 6手目
  • 最後、ペットの少ない空間を選んで入るようにした
  • 394,072,068点
• 7手目
  • 無駄なウェイトをなくして、極力まとわりつかれないようにした
  • 452,070,526点
• 8手目
  • 一番上の人が何もしてないので、ペットの少ない空間に移動するようにした
  • 448,566,939点
  • ローカルではまあまあ伸びていたのに提出すると微減- - -
    • ペットを連れてきてしまうなど悪影響が出ることもある？
    • あと、別件で計算を雑にしていたため一番下の空間だけがやたら広くなってしまうバグを発見- - -
• 9手目
  • 仕切る人が必ず4人になるように調整
    • 上記のバグ対策でとりあえず
  • 518,675,518点
    • 伸びたは伸びたけど、テストケースによってばらつきがかなり大きいのが気になる
• 次やること
  • 全員をペットの少ない空間に移動するようにしたい
  • それなりに実装できたのだが、犬がどうにもならない

最終結果

seed0でこんな感じです。何も難しいことはしていません。（ていうかできなかった・・・。）

感想

期間がありすぎても、生活とか社会とかいろいろありますからずっとAHCのことばかり考えているわけにもいかず。犬対策をどうしたらいいのかわからないところでほぼ放置状態になってしまいました。

でもまあ、単純なアイデアと実装でもAHCの現環境ならまだまだ水パフォは維持できるんだよー、というところはアピールしていきたい所存です。

AtCoder Beginner Contest 241（Sponsored by Panasonic）

ABCEの4完、1WA。

各問題

A - Digit Machine

次のkはa[k]となるので、k=0から始めて3回繰り返します。

B - Pasta

ある長さが何本あるか（残っているか）をmapで管理して、Bをひとつひとつチェックしていきます。

C - Connect 6

各マスから、右、下、右上、右下を（今いるマスを含めて）6個分チェックして、'#'が4つ以上ある方向が一つでもあればYesで、どこにもなければNoです。

チェックする際、盤面をはみ出さないように気をつけましょう。（その点で考慮が足りず1WA...）

D - Sequence Query

解ききれず・・・。

さいしょ、multisetにいれて二分探索で頑張ったんですが、TLEしてしまいました。

ただ、Twitterみてるとこれで通した人結構いるようなんですよね。なにがだめだったのでしょうか？

で、座圧＋セグ木で頑張ろうとしたところでタイムアップでした。

E - Putting Candies

鳩の巣原理で、N回操作する前にかならずループが出来上がる（Nで割った剰余が既出になる）ことがわかります。ループの始点を特定すれば後は単なる計算問題です。

ダブリング？知らない子ですね・・・。

まとめ

Cで詰まり、Dの方が解けそうと思ったらTLEをくらい、一旦Cに戻って通して、またしばらくDを考えても解けず、Eに行ったら実装に手間取ったものの通すことができて、結局Dは通せずじまいということで、大いに立ち回りをミスった感が・・・。

まあEを通したことで水パフォ拾えたのでよしとしましょう。

AtCoder Beginner Contest 240

5完。26:55は自己ベストだったらしい。

各問題

A - Edge Checker

1から順に並んでいるので、差が1なら隣同士です。ただし、例外として1と10も隣同士であることに注意。

B - Count Distinct Integers

setに突っ込んでサイズを答えます。Aより楽。

C - Jumping Takahashi

柱とかカエル飛びの問題のようなシンプルな1次元DPをすればよいです。答えるのは最後までジャンプした後の位置であることに注意です。途中でXに到達してもそれは無効です。

D - Strange Balls

やり方はいろいろありますが、例えばdeque<pair<int, int>>で「何番」が「何個」積まれているかを管理していけばできます。積まれている総数は別途管理しておきます。

E - Ranges on Tree

問題文の解読に時間をかけてしまいましたが、読み解けると実はかなり簡単で、葉に端から番号を順番に振っていって各点が含んでいる葉の番号の範囲を[R, L]とする、という問題です。木のDFSが書ければE問題としては特に難しいことはないかと。

F - Sum Sum Max

等差数列の和さえ求まれば、各範囲の終了時点の状態を取ることはできて、あとは範囲内の状態がどうなっているかなんですが、これが求めきれず・・・。

三分探索かー。それはそうすぎる。

まとめ

5完速度自己ベストで久しぶりの青パフォあるかと思いましたが、残念ながら1500台。いやこの速さ（早さ）で青行かないのはきつい・・・。