olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

AGC008-E Next or Nextnext

AtCoder

問題概要

サイズNの数列Aが与えられる。サイズNの1~Nの順列であるPの中で、

p[i]=a[i],p[p[i]=a[i]の少なくとも一方を満たすPの数を数える。

 

メモ

途中まではAtCoderの公式解説と同じ考察をする、「ただの閉路」の数え上げがDPで行える理由が分からなかったので(分かる人いたら誰か教えてください)、組み合わせで殴りたくなる。

 

サイズが3以上の奇数である閉路の数え上げ

閉路のサイズをS、そのような閉路の数がK個、その中からM個のペアを作る場合の数は

\frac{K! \times S^M \times 2^{K-2M}}{M! \times 2^M \times (K-2M)!}

となる。(2つの閉路を選んだ時のペアの作り方はS通りあるし、ある1つの閉路の使い方は2通りある。)

Mが1変わったときの差分は高速に求められるので、十分高速に全ての場合を計算できる。

 

それ以外の閉路の数え上げ

閉路のサイズをS、そのような閉路の数がK個、その中からM個のペアを作る場合の数は

\frac{K! \times S^M}{M! \times 2^M \times (K-2M)!}

となる。(2つの閉路を選んだ時のペアの作り方はS通りある。)

Mが1変わったときの差分は高速に求められるので、十分高速に全ての場合を計算できる。

 

閉路のサイズごとにこれらを求め、掛け合わせると答えが出てうれしいです。

ACの提出を載せます。

atcoder.jp

AtCoderで橙になるまでにやったこと

ポエム

橙になった記事が少ないので橙記事を書きます。

 

前回のみんなのプロコンで橙になりました。

 

 

簡単な自己紹介

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位だったのでめっちゃ強いじゃんとか言ってた。

 

当日

先輩たちから大量のエナドリの差し入れをもらいつつ準備

 

模擬国と同じくFまで印刷してもらい問題に目を通す。Fが幾何っぽかったのでferinさんのDと交換する。

 

 開始後一瞬でAとCが通る。すごい。Dは枝刈り全探索をしたくなったので書くと最悪ケースでかなり重い。微妙だったのでBの実装に入ってもらうもBも辛そう。

その後しばらく高速化をしていたが、最悪ケースを埋め込むと爆速になったので通す。

その後Bも通る。

この時点で1時間以上経っていて焦って順位表を見るもその時点では5完は結構少なく、また順位が29位でそこそこ余裕があったので一息つく。

 

Eはくり返し二乗法で解けなかったら解けないでしょ！と強硬に主張して実装に入る(←戦犯)

二人が残りの問題の考察を進めるも辛そう。

そのままEが通らず終了(それはそう)

33位

 

順位は厳しかったけど通過したので挽回のチャンスがありますね！

 

codingame (Code of Cutulu)

MarathonMatch

ルール

最初正気度を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でできなかったこと

・探索

 

レジェンドリーグまで上がって世界４１位日本５位でした！うれしい！

Xmas Contest 2017

参加記

今年も出ました！

迷路君とkenさんとチームを組んで参戦。

とりあえず迷路君が1問目を、僕が2問目を、kenさんが3問目を見ようかな見たいな話になったのでBを見る。

文字列の長さが15で32文字までに収めてね！って言われたので明らかに2個+アスタリスクが2個だなあとなって、斜めに書いたら成功した。

kenさんにEが簡単っぽいよ、と言われたけど「Eはいつでも通りそうなのでHに挑戦する。」と言う。

迷路君がAを断念してGに挑戦。8分でACしててウケる。

Hをあきらめて微妙にやることがなくなったのでEを解くことに…

f:id:olphe:20171225000817p:plain

しかし、全然解けない！迷路君にチェンジ。

drkenさんはCの部分点を取っていて、うんうんうなっていたので僕も考えてみたらxorが実質引き算だねということに気が付いて投げたら通った。

drkenさんがさっそうとEを通す。かっこいい。

ここで15分ぐらいみんなでAとにらみ合うが解けない。

その後1時間ぐらい僕とkenさんで無限にHとにらみ合っていて、迷路君は無限にAとにらみ合っていた。

あきらめかけてHを乱択したら成功してテンションが上がっていた。

迷路君はFの部分点20点を取っていた。

あとは多分みんなで視力検査をしていたんだなあ。

楽しかったです。

Codeforces Round #450 (Div. 2) D問題

Codeforces

和がNで数列の全要素のGCDが1となる数列の数を求めたい。

a(n) = sum_{d|n} mu(n/d)*2^(d-1)

この式で表せるらしいが全然意味が分からなかったのでメモしておく。

 

d | n……dはnの約数という意味。

sum_{ }……{ }内のすべての要素について何か処理をする。

mu()……メビウス関数。

メビウス関数 - Wikipedia

 

つまり、nの約数であるすべてのdについて、mu(n/d)*2^(d-1)の総和を求めたいらしい。

 

また、包徐原理を使うことで、2^(n-1)からd>1となるa(d)を引いても求められるらしい。

和がn/dだったときに(a,b,c)だったのがd倍すると(ad,bd,cd)となるからかなあ。

 

 

 

北大＆日立MMその1

MarathonMatch

1日目
King's Graphはどうでもいいので、2S*2S四方のフィールドに元のグラフの頂点を乗せていくことにする。
(King's Graphへの変換後に辺が伸びているかはチェビシェフ距離が1か否かで判定できる)
とりあえず愚直貪欲を書いてみようと思って、頂点0をフィールドの中央に置いた後、一番スコアの伸びるものを貪欲に配置していくことにした。
ここまでで153329点
時間の許す限り開始点を変えつつ、より重い辺がたくさん伸びている頂点から回すと155626点
ランダム2点swapを実装し、156150点
2点swapを全探索に変更しつつ高速化をして156658点
軽いケースで初期解の探索に時間をかけるようにすると156716点
この時点では3位狙えるんじゃね！？みたいに思っていた。
二日目
全探索3点swapをバグらせつつも書ききり157037点
全探索4点swapを実装すると同時に、2点swap～4点swapを関数化、ここで3,4点swapをバグらせる。が、スコア更新し157048点
全探索5点swapも実装したが効果がなさそうなので没に
三日目
方針が降ってこなくてお掃除をしていた。
1点moveを実装していないことに気づき1点ムーブを実装し157334点
moveとかswapの順番をいろいろいじってたら157483点
四日目
前日に引き続きいじっていたら157553点
そろそろ頭打ちだなあと思い始めたので、初期解の改善に取り組む。
配置していくにあたって共通の隣接ノードを持つ頂点同士を隣り合わせるように変更を加えると157599点
ずっとこれをいじる。
五日目
前日に引き続きいじっていたが芳しくない結果だったのでやる気を失いかける。
こどげに逃げようかな～とか考えていると、今の方針が特に意味のないものであることをゆる～く説明できるようになったので今の方針を捨てることを決意。
コードをグッと睨むと定数倍重くするだけ(約20倍)で初期解の探索時に深さ2の全探索を行えることに気づく。
六日目
ようやく深さ2の全探索の実装を終え、158413点。
すると4点swapがお役御免になったので4点swapに別れを告げる。
3点swapまでは最悪ケースでも約3000msで行えるので初期解の探索にもう少し時間をかけるようにすると158562点。
ケースハック(？)を試み始める(ア)
七日目
ひたすらケースのNの特定作業を行う。
あと、一番最初に配置するノードはどれがいいのか調べると、やはりより重い辺がたくさん伸びてる辺を最初に置くのがいい可能性が高いことが判明する。
N=3とN=7で全探索しようかな～とか考えていたけどすでに最適解が出ていた。
八日目
全ケースのNを特定するもシステスらしくて悲しいね
長さ3の全探索を実装しようとしていたけど場合分けが半端なくてあきらめた。
九日目
初日に捨てたビームサーチが案外うまくいくのでは！？みたいに思ったので実装を始める。
全然ダメだったので方針を捨てる。と同時に案が尽きたので終了
十日目
なんやかんやでMM復活
長さ3全探索の実装を再開。
十一日目
前日の続き
十二日目
前日の続き
方針を変えないまま実装の方針を変えることにする。
十三日目
実装成功するも何故かスコア落ちる。
さらに実装方針を変更する。

 

REが出て80位まで落ちた…悲しい…

よく考えたら焼き鈍しの問題なのに方針捨てたのはまずかったので次回以降気を付けような👊