ECR160-D Array Collapse

ECR強化期間

AtCoderは前半解きすぎて残っているセットがほぼない(助けてくれ)。ECRでバチャを走り、セット形式で練習する。バチャ中に解けなかった問題をupsolve/解説ACし、自分の理解をブログに留める。

  • 橙まで、やる気があったら赤diffもACする
  • ICPCなどでチームメイトに解法を伝える練習も兼ねる

強化期間と銘打っているが、やる気がなくなったらすぐ終わる。この記事でそれっきりかもしれない.....

問題

https://codeforces.com/contest/1913/problem/D (2100diff)

長さ Nの数列 Aが与えられる。 Aはdisjoint。以下の操作を 0回以上行う。

  • 連続する区間を選び、区間内の最小値以外を削除する

最終的にありうる数列の数 \mod{998244353}

制約:  Nがでかい。

続きを読む

RUPC2024 参加記

はじめに

3/23, 24に開催された立命館大学プログラミング合宿2024 RUPC2024 に参加してきました。day2の問題セットのWriter, Testerも担当しました。本記事はこれらの参加記です。

運営のRiPProの皆さん。今回は貴重な体験をすることができました。ありがとうございました!

注意事項

  • 問題内容のネタバレ(RUPC2024day1, day2, ABC346, ARC175)を含みますので、これからセットを解こうと思っている人は注意してください。
  • ですます調なのか、タメ口なのか、口調が統一されていない
続きを読む

ABC342-F Black Jack

コンテスト中は丁寧丁寧丁寧に解いたので雑に雑に雑に解説残しておきます。想定解と多分一緒です。

問題概要

https://atcoder.jp/contests/abc342/tasks/abc342_f

あなたとディーラー、 D面サイコロ、変数 x = 0, y = 0があります。あなたとディーラーがゲームをします。

まず、あなたが、以下の操作を好きな回数繰り返します。

  • サイコロを一回振る。出た目を xに加算する。

次に、ディーラーが y \lt Lの間以下を繰り返します。

  • サイコロを一回振る。出た目を yに加算する。

勝敗は次のように決められます。

  •  x \gt Nならディーラーの勝ち
  • そうでなくて y \gt Nならあなたの勝ち
  • そうでなくて x \gt yならあなたの勝ち
  • そうでないならディーラーの勝ち

あなたが勝つために最適に行動した時、勝つ確率を求めてください。

制約

  •  1\ \le\ L\ \le\ N\ \le\ 2\times 10^{5}
  •  1\ \le\ D\ \le\ N
続きを読む

AOJ3336 Fish Tank

備忘録。想定解をそのまま追っかけただけの記事なので新規性は無いです。

問題概要

https://onlinejudge.u-aizu.ac.jp/problems/3336

長さ nの広義単調減少列 Aが与えられる。以下の操作を何回か行うことを考える。

  • 添字 iを一つ選んで、 A_{i} 1増やす。

各操作の前後で Aは広義単調減少でなければならない。全ての A_{i} Mにする操作の仕方の通り数を 998244353で割ったあまりを求めよ。

制約

  •  1\ \le\ N\times M\ \le\ 200000
  •  1\ \le\ A_{i}\ \le\ M
  •  Aは広義単調減少
続きを読む

ICPC 2023 Asia Yokohama Regional 参加記 (LuzhiledFanClub zawatin)

前置き

zawatin.hatenablog.com

これは嘘でした。問題解いた時の復習記事以外でははてなブログを使おうと思います。

ICPC 2023 Asia Yokohama Regionalに参加しました。とても貴重かつ楽しい経験をさせていただきました。大会に関わったすべての人に感謝を申させていただきます。ありがとうございました。

自分が作題に関わったHUPC2023*1や、自分が在籍している大学で開催されるパソコン甲子園などの参加記を読むのが存外楽しく、(大会・イベント運営に関わった皆さんへの恩返しも兼ねて)今回自分も参加記を書いてみようと思いました。本当はJAG2023夏合宿の参加記も書く予定でしたが、day3のコンテストの成績があまりにも酷く、萎えてしまったので書きませんでした。参加記というより日記・行動記録を細かくしましたみたいな文章になってしまいましたが、お付き合いいただけると幸いです。

*1:HUPC2023-day3 AFHL

続きを読む

ABC237-G Range Sort Query

これ  Q \le 2\times 10^{5} で解けるのすごいね......

  • 問題概要
    • 制約
  • 情報を削る
  • 上でのクエリ処理
  • 提出コード

問題概要

https://atcoder.jp/contests/abc237/tasks/abc237_g

長さ Nの順列 Pを与えます。以下のクエリを Q回処理します。

クエリ・・・ t\ l\ rを与える。順列の l番目の要素から r番目の要素までについて t = 1なら昇順にソート、 t = 2なら降順にソートする

すべてのクエリを処理した後、 P_{i} = Xを満たす iを出力しなさい

制約

 1\ \le\ N, Q\ \le\ 2\times 10^{5}

続きを読む