全国統一プログラミング王決定戦本戦-E Erasure
問題概要
N個のブロックが並んでおり、幅K+1以上の全ての区間がある。区間の数をM個とすると区間の選び方は通りある。全てのブロックを選択できる区間の使い方は何通りか。
メモ
素直なDPをする方法と包除原理を用いる方法がある。
素直なDP
seicaさんから掲載許可を頂いた画像が非常にわかりやすい。
これを参考にしたAC提出
包除原理
ixmelさんに教えていただいた。
dp[i][j]を、i番目のブロックまで見て、i番目のブロックを(未来永劫)使わず、[0,i]でj個以上のブロックを使っていない場合の数と定義する。
分かりやすさのために、0番目のブロックとN+1番目のブロックを用意すると良い。
そうすると、dp[k][j]からdp[i][j+1]に遷移したいときに区間の幅とKから(k,i)での区間の選び方が求められる。
このままだと状態数が、遷移の種類がでだが、二次目を偶奇のみ持つことで状態数をまで減らすことができ全体でとなるので間に合う。
この解法でのAC提出
AGC008-E Next or Nextnext
問題概要
サイズNの数列Aが与えられる。サイズNの1~Nの順列であるPの中で、
p[i]=a[i],p[p[i]=a[i]の少なくとも一方を満たすPの数を数える。
メモ
途中まではAtCoderの公式解説と同じ考察をする、「ただの閉路」の数え上げがDPで行える理由が分からなかったので(分かる人いたら誰か教えてください)、組み合わせで殴りたくなる。
サイズが3以上の奇数である閉路の数え上げ
閉路のサイズをS、そのような閉路の数がK個、その中からM個のペアを作る場合の数は
となる。(2つの閉路を選んだ時のペアの作り方はS通りあるし、ある1つの閉路の使い方は2通りある。)
Mが1変わったときの差分は高速に求められるので、十分高速に全ての場合を計算できる。
それ以外の閉路の数え上げ
閉路のサイズをS、そのような閉路の数がK個、その中からM個のペアを作る場合の数は
となる。(2つの閉路を選んだ時のペアの作り方はS通りある。)
Mが1変わったときの差分は高速に求められるので、十分高速に全ての場合を計算できる。
閉路のサイズごとにこれらを求め、掛け合わせると答えが出てうれしいです。
ACの提出を載せます。
AtCoderで橙になるまでにやったこと
橙になった記事が少ないので橙記事を書きます。
前回のみんなのプロコンで橙になりました。
olpheさんの「みんなのプロコン 2019」での成績:77位
パフォーマンス:2660相当
レーティング:2374→2406 (+32) :)
Highestを更新し、三段になりました!#AtCoder https://t.co/tvWmHNySL4— olphe (@_olphe) February 12, 2019
— olphe (@_olphe) February 12, 2019
簡単な自己紹介
olphe
競プロ始めて5年弱
今年度n=1で農工大入学
データ構造で殴るのが苦手で、構築やインタラクティブが得意
無->水-青ボーダー(ぐらい?)(高1春~高3夏)
AtCoderに参加する前で、JOIやPCKの本戦参加を目指していた頃です。
JOI非公式難易度表 AOJ/AtCoder-JOI
の難易度6までを埋めようとしていたり、
PCK予選の過去問の問6ぐらいまでを埋めようとしていました。
水-青ボーダー(ぐらい?)->黄到達(高3夏~浪人期夏)
CfやTcでは緑->青になっていました。
このころにtwitterで競プロerと絡むようになり、介護されていました。
ABC-ABを埋めたり、ABC-CD、ARC-ABの多くを埋めたりしていました。
また、JOIの難易度7~8ぐらいの問題を時間をかけて解いていて、考察をまとめて記事を書いていた時期です。(めんどくさくなって途中でやめています。)
黄到達->橙到達(浪人期夏~Now!!)
CfやTcでは青->黄になっていました。
序盤は難しくて解けていなかったABC-CDやARC-ABを解いたりしていました。DPばかり残っていて、苦手だと思いTDPCの簡単な問題を解いたり、600点までを埋めていました。
中盤は700点~900点ぐらいの面白そうな問題をつまみ食いしていました。
終盤はAGC-BCD埋めをしていたのですが、これがかなり大きいと思っていて、曖昧な感覚ですが考察の仕方が分かってきたような気がしています。
特にAGC-Dで感じたのが、個々のステップ自体はそんなに重くなくて、うまく組み合わせるのが求められている気がします。
今はAGC-Eもゆっくり埋めています。
また最近はICPCのことも考えてCfの2300点(?)前後も少しずつ解いています。
AGC埋めからは同時に実力の近い人と問題を解いており、解説の抜けを補い合ったり感想戦ができて楽しく問題を解けています。
橙到達->赤到達(Now!!~????)
2021年の夏ぐらいまでには赤くなりたい!
AGC-Eを埋めます。
ARC-CDを埋めます。
ICPC国内予選2018
メンバー紹介
ferin:基本的にはBとDを担当する。
div9851:基本的にはAとCを担当する。(←予選通過の立役者!!)
olphe:基本的にはEとFを担当する。幾何が出たらferinさんと1問交換、構文解析が出たらdivさんと1問交換
模擬国内前
僕が入学してすぐにチームが決まった気がする。(競プロerが少ないので)
5月ごろから週に1度500点*3ぐらいのセットを2時間で解く練習をしていた。(1時間でDまで解いて残り頑張ろうなみたいな感じ)
多くの練習でdivさんが構文解析引いてたの面白かった。
模擬国内
事前の打ち合わせ(?)通りとりあえずdivさんにFまで印刷してもらって問題を割り振る。
二人がAとBを一瞬で通したので次に軽そうなEの実装に入る。
楽勝じゃ~んとか言ってたら細かい部分で手間取ってちょっと時間がかかるも通る(FA!!!)
Fを考えている間にCが通る(すごい)
CHTかな~とか考えていたけど3回微分するといい感じになることに気づく(天才か?)
めちゃくちゃ時間かかったけど通る。
残りferinさんがDを、divさんがGを考えたり実装したりしていたけどどっちも辛そうだった。
5完で11位だったのでめっちゃ強いじゃんとか言ってた。
当日
先輩たちから大量のエナドリの差し入れをもらいつつ準備
さしいれドリンク pic.twitter.com/oZQrr0HqxT
— olphe (@_olphe) 2018年7月6日
— olphe (@_olphe) 2018年7月6日
模擬国と同じくFまで印刷してもらい問題に目を通す。Fが幾何っぽかったのでferinさんのDと交換する。
開始後一瞬でAとCが通る。すごい。Dは枝刈り全探索をしたくなったので書くと最悪ケースでかなり重い。微妙だったのでBの実装に入ってもらうもBも辛そう。
その後しばらく高速化をしていたが、最悪ケースを埋め込むと爆速になったので通す。
その後Bも通る。
この時点で1時間以上経っていて焦って順位表を見るもその時点では5完は結構少なく、また順位が29位でそこそこ余裕があったので一息つく。
Eはくり返し二乗法で解けなかったら解けないでしょ!と強硬に主張して実装に入る(←戦犯)
二人が残りの問題の考察を進めるも辛そう。
そのままEが通らず終了(それはそう)
33位
順位は厳しかったけど通過したので挽回のチャンスがありますね!
codingame (Code of Cutulu)
ルール
最初正気度を250持っていて、毎ターン4~6正気度を失う。ただし、2マス以内(壁を挟んでもよい)に他の冒険者がいると1~3で済む。
敵はトンベリみたいな見た目のものと死神みたいな見た目のものがいる。
前者は毎ターン1番近い人を追いかける。冒険者と重なると攻撃し、消滅する。また、30~40ターンで自然消滅する。
後者も基本の移動は共通だが、視界に冒険者が入ると2ターンのためののち、まっすぐに突進攻撃してくる。(突進に限って1ターンの移動制限がない)その後スタンする。また、消滅しない。各冒険者の正気度が最初に200を下回った瞬間にその冒険者と同じ場所に出現する。
どちらのモンスターも出現後6ターンは行動しない。
敵に攻撃された際のダメージは20ダメージである。
フィールドは空きマス、壁、モンスターのスポーン地点、シェルターで構成されている。
トンベリは5ターンに一度任意の冒険者から一番遠いスポーン地点から出現する。
シェルターは重なると上にいる冒険者の体力を5回復する。しかし、シェルターは50ターンに10しかエネルギーが回復せず、最初はエネルギー切れしている。
冒険者は毎ターン周囲1マス以内に動くか、特技を発動することができる。
PLAN…5ターンの間自分の周囲2マス以内の冒険者を3回復させる。2回使える。
LIGHT…3ターンの間他の冒険者がいるとよい範囲が4マス伸びる。3回使える。
YELL…2ターンの間周囲1マスの冒険者の動きを止める。何度でも使えるが同じ相手には1度しか効かない。
やったこと
ちょっと遅れて参加したので参加したころにはSILVERまで解放されてた。
開始時
トンベリを避けつつほかの冒険者と群れるのが一番大事だと考えたのでトンベリと他の冒険者だけを考えてマップに評価値を定めた。
具体的には任意のマスについて、任意のトンベリの最短攻撃到達時間、任意の冒険者からの最短距離を求め、敵に近すぎる場合は補正を加え、確実に安全なマスのみを通っていけるマスで評価値の一番いいところに近づくようにした。
このコードでSILVERまで上がった。
SILVER
死神についても最短攻撃時間を求め、トンベリのものと混ぜ、評価値を更新することにする。また、YELLを、自分が敵から2マス、ほかの冒険者が敵から1マスにいる且つほかの冒険者と接していてまだ使ったことがない相手であるときにYELLを発動することにした。
このコードでGOLDまで上がった。
GOLD
その場にとどまろうとするときにPLAN、LIGHTなどを使うようにした。
また、行き止まりに対してペナルティを定めた。(終了直前にわかったことだが不完全だった。)
パラメータガチャをしつつLEGENDにあがる。
LEGEND
シェルターの存在を忘れていたので実装するも劣化したのでシェルターを無視することにする。
また、行き止まり判定を行おうとしていたが、O(H^3 W^3)とかで悲惨だったため高速化するが、バグったためあきらめる。
やりたかったこと
・LEGENDでできなかったこと
・探索
レジェンドリーグまで上がって世界41位日本5位でした!うれしい!
Xmas Contest 2017
今年も出ました!
迷路君とkenさんとチームを組んで参戦。
とりあえず迷路君が1問目を、僕が2問目を、kenさんが3問目を見ようかな見たいな話になったのでBを見る。
文字列の長さが15で32文字までに収めてね!って言われたので明らかに2個+アスタリスクが2個だなあとなって、斜めに書いたら成功した。
kenさんにEが簡単っぽいよ、と言われたけど「Eはいつでも通りそうなのでHに挑戦する。」と言う。
迷路君がAを断念してGに挑戦。8分でACしててウケる。
Hをあきらめて微妙にやることがなくなったのでEを解くことに…
しかし、全然解けない!迷路君にチェンジ。
drkenさんはCの部分点を取っていて、うんうんうなっていたので僕も考えてみたらxorが実質引き算だねということに気が付いて投げたら通った。
drkenさんがさっそうとEを通す。かっこいい。
ここで15分ぐらいみんなでAとにらみ合うが解けない。
その後1時間ぐらい僕とkenさんで無限にHとにらみ合っていて、迷路君は無限にAとにらみ合っていた。
あきらめかけてHを乱択したら成功してテンションが上がっていた。
迷路君はFの部分点20点を取っていた。
あとは多分みんなで視力検査をしていたんだなあ。
楽しかったです。
Codeforces Round #450 (Div. 2) D問題
和がNで数列の全要素のGCDが1となる数列の数を求めたい。
a(n) = sum_{d|n} mu(n/d)*2^(d-1)
この式で表せるらしいが全然意味が分からなかったのでメモしておく。
d | n……dはnの約数という意味。
sum_{ }……{ }内のすべての要素について何か処理をする。
mu()……メビウス関数。
つまり、nの約数であるすべてのdについて、mu(n/d)*2^(d-1)の総和を求めたいらしい。
また、包徐原理を使うことで、2^(n-1)からd>1となるa(d)を引いても求められるらしい。
和がn/dだったときに(a,b,c)だったのがd倍すると(ad,bd,cd)となるからかなあ。