naoya_t@hatenablog

いわゆるチラシノウラであります

早稲田大学プログラミングコンテスト(WUPC)2019

諸般の事情により家にいることになったので、ちょうどやってたWUPCに途中から(個人で*1)参加。

3/10 13:00-17:00
早稲田大学プログラミングコンテスト2019 - AtCoder
早稲田大学の学生を中心とする有志メンバーによるプログラミングコンテスト

AtCoder のアカウントをお持ちであれば、どなたでも参加することができます。

早稲田大学の学生(や卒業生)ではない人も、というか学生じゃなくても*2参加できるのは良い。

4完(ABEG)77/507位
青コーダーの単独参加としてはまずまずの出来なのでは

問題の実際の難易度はこんな感じらしい:


A - WAsedAC (100)

(言われたとおりにシミュレートしたらWWWWWWWWWWWWWWWWAみたいなのでTLEになるよね)
pythonre.finditer(r'W+A',s)して
マッチした区間ACCC.. に替えて、それ以外はそのままで
文字列を再構築
AC

でもここは kimiyukiさんのコードのように

import re
s = input()
t = re.sub(r'W+A', lambda m: 'A' + 'C' * (len(m.group(0)) - 1), s)
print(t)

re.subにlambdaを渡すのがスマートでいいね

B - 10 puzzle (100)

  • 全部0なら(0)
  • 5がなければ無理(-1)
  • 5が1つ以上あって、それ以外が5未満なら一発(1)
  • 6〜9がある場合、5をどれか1つ残しつつ9→8→6→2, 7→4のように減らしていって5以下のパターンになったら一発

→WA(1)
テストケースの後半が全滅だ
あ…幅1のとき死ぬのか
幅1の場合どの5を使うか全部調べた
AC

C - Permutation City (200)

(未)
葉から攻めるみたいなのは考えたんだけど最後どうしたらいい?

D - Choose Your Characters (200)

(未)
計算量をO(N^2)からどう減らせるのか見えず

E - Artist (200)

縦横独立に計算し(各行・各列の和を求めておいて、その和の配列をどこかで二分したときに左右ともpalindromeになる箇所の個数を求め)た積。
palindrome判定にローリングハッシュを初めて使った(modは2種類、1e9+7と1e9+9を使った。baseは5e5以上で適当な素数ここから選んだ)
AC

こういう問題でローリングハッシュと並んで名前が出てくるManacharも使えるようになりたい。

F - RPG (200)

(未)
開いてない

G - Teishoku (200)

  • 列を逆順に見ていって定食kの注文数を累積しながら、定食iの人が定食jに先を越されて怒る数 d[i][j] を求める。O(NM)
    • d[i][j] : N×N行列
  • あとはbitDP O(2^NN^2)
  • 合わせてO(NM+2^NN^2)

AC

H - Doki Doki Programming Clubs! (200)

(未)
開いてない

I - Ramen (300)

(未)

  • 入力は開店日順になっているのでこの順に
    • 閉店操作はpriority_queueに入れておいて、次の店の開店前に参照する
  • 開店済みの店iの値段がp_i、位置がd_iのとき、新規開店する店の位置d_jに関して
    • p_i+(d_i-d_j)^2=p_i+d_i^2-2d_id_j+d_j^2=d_j^2+(-2d_i\cdot d_j+(p_i+d_i^2)

d_j^2iによらないので外に出して、iに依存する部分を

    • -a_ix+b_i

という形にまとめることができる。これはCHTでどうにか出来るのでは?
(という所までは考えたんだけど詰められず)

J - Color Ball (300)

(未)
問題は読んだ
すべてのパターンから禁止パターンを引き算(包除原理)する系かな?

*1:レート2000未満だとチーム参加可能なのだけれど、出る予定ではなかったので考えてなかった

*2:どれにもあてはまりません