Joeの精進記録

旧:競プロ練習記録

Codeforces Round #517 (Div. 2)

久しぶりの投稿です(Codeforcesは久しぶりではない)

紫になりました。やったー!

D - Minimum Path

解法は以下のSlackのトークを参考にしてください。

f:id:xuzijian629:20181022113849p:plain

ところでこの問題を解いているときに、以前のHackerRankのUniversity Codesprint 5の問題を思い出しました(今回のこどふぉの問題よりずっと難しいしあんまり関係ない話です)。

www.hackerrank.com

これですね。今回はpathの長さが2n-1固定なので貪欲でいけましたが、どういう順序で回ってもいい場合は貪欲ではできません。その場合は、suffixに注目したDPをします。これは知っていたのですが、HackerRankはTLE解法を高速化して通したので、DPを書いたことがなく、今回の問題でけっこうびびりました。

DPにstringを保存する(つまり、dp[i]をi番目の頂点からゴールにいく文字列で最小のものとする)とMLEするので、何を保存するのかなと思いましたがdp[i]を、iから遷移できる頂点のうちもっとも辞書順で小さな頂点、としてできる。文字列の比較は、suffix arrayとかを使ってやる模様

↓↓参考↓↓

ei1333.hateblo.jp

情報理工院試レビュー

東京大学大学院情報理工学系研究科コンピュータ科学専攻の院試結果の開示が届きました。

自分が受験するときに全然点数情報がわからなかったので、来年度以降調べる人用に自分のものを開示しておきます。

f:id:xuzijian629:20181019230033j:plain

こんな感じです。第一志望の杉山研に受かりました。

数学と専門Iはまあこんなもんか、という感じでしたが専門IIでやらかしてしまい、まわりの人がかなり専門IIで得点をとっていたようなので 緊張してました。

何はともあれ合格してよかったです。

区間と区間がかぶる問題まとめ

【重要】面倒なので、区間の始点終点はすべて異なるとします。そうじゃない場合は適切にソートして順序付けとかしてやると大丈夫です。多分。

すでに区間がたくさんあって交差する回数を数えるやつ

No.743 Segments on a Polygon - yukicoder

  1. 区間を(start, end)のペアで持ち、小さい順にソートする
  2. 座標値が収まるようなセグ木を持ち、0で初期化
  3. (Ai, Bi)の区間の総和をcntに加算して、Biに1加算
  4. 最終的なcntの値が答え

すでに区間がたくさんあって、クエリが飛んでてきて指定された区間内にいくつ区間が入っているかを答える

多分一番楽?

  1. 座標値が収まるような配列を用意し、(Ai, Bi)に対してインデックスAiをBiにセットする
  2. (Pi, Qi)の間に区間がいくつ収まってるかカウントするときは配列のPi, Qiの範囲内でQi以下の要素の個数を数えます(セグ木とか使って)。

hama-du-competitive.hatenablog.com

ここにも永続セグ木を使うやつとかWaveletMatrixを使うやつなどが載ってます。

区間が動的に追加されていくやつ

無理じゃね?と思っている

競技SwarmerのためのTips

競技Swarmerを引退する(Swarm自体は続けます)のでこの機会に競技SwarmのTipsを残していこうと思います。 得点システムとかあんまり調べても出てこないと思うので自分が1年ぐらいやってわかったことなど思い出しながらまとめていきます。

競技Swarmとは

iOS/AndroidアプリのSwarmで週ごとのチェックインの総得点を競うhogeです。

チェックインしまくればいいだけでは?

競技Swarmerはプロ意識があるのでチェックイン詐称や、通過だけでのチェックインはしません。

競技Swarmerの見分け方

通常ユーザーと比較してみると得点の違いに気がつくと思います。

通常ユーザーのTL f:id:xuzijian629:20181010005940j:plain

競技Swarmerの場合 f:id:xuzijian629:20181010010052p:plain

まあ基本的に得点の高いチェックインが多いです。ユーザーにもよりますが、1チェックインで100程度まで一気に稼ぐことがおおいです。

得点の稼ぎ方

Swarmで効率よく得点を稼ぐためにはSwarmの得点システムをよく知る必要があります。Swarmには何種類もボーナスが用意されておりこれらを駆使することで得点を 3倍にも4倍にもできます。

ボーナス

ステッカー (×3)

これは一番有名なやつですね。Swarmに登録されているスポットには様々なカテゴリがありますが、その中でも代表的な100種類には、ステッカーが存在し、そのカテゴリに10回チェックインすると2倍ステッカー、25回チェックインすると3倍ステッカーがもらえます。ステッカーは他ボーナスと一緒に使うと最強ですが、次のセクションで説明するようにJapanese RestaurantステッカーはItarian Restaurantステッカーよりも使いやすいなどがあり、優劣があります。10回に満たなくても+2ポイントのボーナスがあります。また、ちょうど10回目、ちょうど25回目もそれぞれ2倍、3倍のボーナスが付きますが、このときチェックイン画面ではハイライトされないため、気づかずスタンプを使わないでいるとかなりもったいないです。あと何回でアップグレードかを常に確認しましょう。

f:id:xuzijian629:20181010011457p:plain

Week Streak (+15) for Category

ボーナスとしては3週目からカウントされます。そのジャンル(ステッカーが登録されていないジャンルでもよい)に連続何週チェックインしたかのボーナスです。過去最高の記録の場合+15, そうではない場合(一度途切れてしまったときなど)は3週目では+5です。また、最高記録依存ですが、最高記録に近づいたりある閾値を超えると+10, +15とボーナスが上がっていきます。

Week Streak (+15) for Spot

同様に、同じスポットに毎週チェックインし続けることでも3週目以降からボーナスが入ります。これは、StreakのUIからは確認できないので、検索欄にそのスポットの名前を入れるなりして自分で日々確認しましょう。ボーナスは同様で3週目以降からカウントされ、新記録の場合+15です。

Day Streak (+15) for Category / Spot

hoge日連続同じジャンルの場所にチェックインしてもボーナスが貰えます。同様に3日目以降からカウントされ、最高記録の場合+15です。スポットに関しても同様。

写真 (+5×枚数)

写真を撮ると1枚につき+5ポイント入ります。撮りすぎるのは得点のとり方がきれいじゃないのでやめましょう。

友達とチェックイン (+5×人数)

これはめちゃくちゃ強いです。友達と旅行するとチェックインする場所も普段よりたくさんあると思うのでいっきに得点が増えます。 友人の中で最初にチェックインによるボーナスは+2なので2人以上でチェックインする場合、あとにチェックインするのが好手です

メイヤー奪取 (+10)

これも強力です。複数人で協力してプレイする場合、毎日交互にチェックインすることで、先攻したほうがメイヤーになれ、後攻のほうが、友達とのチェックインボーナスを貰えるのでwin-winです。

移動距離 (+3 / +5 / +10 / +20)

1000マイル未満だと+3, 2000マイルまでが+5, 2000マイル超えたら+10, 4000マイル超えたら+20です。空港ステッカーは到着の空港で使うのが定石です。

ある複合施設内でのチェックイン (+1 / +2 / +5 / +10)

同じ日に複合施設内のスポットにチェックインすると、1回目には1ポイント、2回目には2ポイントとボーナスが貰えます。4回目のチェックイン以降は+10が常にもらえます。 かなり優秀なボーナスですが、案外こういう複合施設が身近になかったりします。

hoge回目のチェックイン (+5)

ジャンル、スポットともに存在するボーナスです。また、同じ友人とのチェックインに関しても、回数がカウントされ、同様のボーナスが貰えます。あまり自信はないですが、5回, 10回, 20回, 30回, ...と100回までカウントされます。200回目でボーナスはもらえませんでした。友人とのチェックインに関しては10回目からカウントスタートです。基本的に+5なんですが、回数がかなり増えると+10になった気がします(未確認)。

シェア (+2)

ツイッターなどでシェアするとボーナスが貰えます。まあ得点が上がるので嬉しいけどあまりシェアしすぎるとうるさいのでたまにだけにしてね

ここ以下はそんなに役に立たないボーナスです

メイヤー存続 (+3)

ないよりはマシという程度。

初チェックイン (+5)

まあ、記録狙いなら、同じスポットに毎週/毎日チェックインするのが正解なので活用する機会はあまりないかもしれませんが、万が一Streakを切らしてしまったときにステッカーの使い道がなくなったら初チェックインに被せます。

hogeヶ月ぶりのチェックイン (+2)

完全に不要

Trendsetter (+10)

登録されてから最初の50人のチェックインだともらえるボーナス。自分で場所を追加する場合は自明にもらえるがそうでない場合はもらえたらラッキーという程度。

FourSquare Day (+18)

4/16にもらえるという運営会社FourSquareのボーナス。+18が謎すぎる。このボーナスまで意識しだしたら相当の競技Swarmer

Happy Birthday (+20)

登録した誕生日になったらもらえる。さすがにここをいじって得点調整するのは競技Swarmerとしてやっちゃだめ

Anniversary (+5)

登録した日から1年記念にもらえる。

アドバイス

まあということでボーナスはざっくり説明しましたけどこれらをうまく複合させて使いこなすことが重要です。明らかに、努力対効果がもっとも大きいのは+15のWeek/Day Streakですが、さらにこれにも工夫できる点があります。 まず、Categoryは階層構造になっているということです。たとえば、Japanese Restaurantの親としてAsian Restaurantがあり、Ramen Restaurantの親としてJapanese Restaurantがあります。これは何を意味するかというと、たとえばラーメン屋に3日連続チェックインすると、Ramen Restaurantの記録が得られるだけではなくJapanese RestaurantおよびAsian Restaurantの連続記録も得られます。同様の階層構造でよく使うものには次のような例があります。

  • Asian Restaurant > Japanese Restaurant > Udon Restaurant
  • Asian Restaurant > Japanese Restaurant > Ramen Restaurant
  • Asian Restaurant > Japanese Restaurant > Donburi Restaurant
  • Asian Restaurant > Chinese Restaurant
  • Italian Restaurant > Pizza Place
  • Bar > Beer Garden
  • Bar > Sake Bar

基本的に3段階の階層構造を持っているのはJapanese Restaurantしかありません(他知らないです)。ですから、効率よくポイントをためたいときは日本食を食べまくりましょう。

また、週明けは0時に得点がリセットされますが、それ以外の日の場合、日ごとの記録がリセットされるタイミングは午前4時です。なので、チェックインを忘れてもあせらないでください。まだ午前4時を回っていないなら間に合います!

さいごに

1回のチェックインでのこれまでの最高記録です。まあここまでに書いたことを完璧にマスターすればそんなに苦労せずとも抜けると思います。

f:id:xuzijian629:20181010022325p:plain

f:id:xuzijian629:20181010022239p:plain

Hello Barcelona Day4

Day3はLink-Cut木コンテストだったんですが、むずすぎたのでもうちょっと理解してから記事にしようと思います。 Day4はstereometry(空間の幾何?)コンテスト

A - Elementary

問題

4点与えられるのでそれらを頂点とする四面体の体積を求めて、という問題

解法

三重積を計算して6で割るだけ

B - Cross Spider

問題

 1 \le n \le 100000点が与えられるので同一平面上にあるか判定せよ。XYZ座標はそれぞれ絶対値が1000000以下。

解法

座標が大きく、内積外積の演算をするとdoubleでは誤差が心配(ギリギリいけそうだけど)なのでlong longで計算する。 平面の法線ベクトルが確定したらあとはそれと直交するかをみればいいだけ。

C - Line Teleportation

@kenshinが知らない間に通してた。

D - Segment Distance in 3D

この前まとめました。

xuzijian629.hatenablog.com

E - 3D Printing

問題

30面程度の凸な多面体が与えられるので体積を求めよ、という問題

解法

@oginginが通してくれた。

H - Connected Rings

リングが2つ与えられるので、鎖状につながっているか判定せよ。リング同士が交点をもつことはない。

解法

@kenshinが気合で座標計算し、通してくれた。プロすぎる。

感想

この日は自明問題しか貢献できなくて厳しい気持ちになった。

Hello Barcelona Day2

Day1の内容はJAG合宿Day3と全く同じだったようです。なので記事はDay2からにしようと思います。

beta.atcoder.jp

A - Alice and Maze

問題

 n頂点 m辺の無向グラフが与えられる。各頂点に報酬、各辺にコストが設定されている。 頂点を訪れるたび、その報酬が貰え、辺を通るには、そのコストを支払わなければならない。 スタートは頂点1でゴールは頂点 nとする。Aliceはスタート時点で k円持っており、お金を最大化した後 ゴールから出たい。スタートとゴールの頂点を含め、同じ頂点や辺は複数回通ってもよい。 そもそもゴールにたどり着けない場合は-2, いくらでもお金を増やせる場合は-1, 有限のお金まで増やせる場合は、その金額を出力せよ。

制約

  • 4秒
  • 10テストケース
  •  2 \le n \le 1000
  •  2 \le m \le 100000
  • 初期のお金、報酬、コストはそれぞれ1円以上 10^7円以下

解法

問題は無向グラフで与えられているが、進む方向によって実質かかる費用は異なるので、辺数を2倍にした有向グラフで考える。 ベルマンフォードをやるだけだが、更新時に、現在の所持金が辺のコスト以上かどうかをチェックし、その場合のみ更新するようにする。

さらに無限大に発散するループが存在する場合、 n(頂点数)回目のループで更新された頂点を列挙し、これらのうち1つ以上がゴールから到達可能な場合、 いくらでも所持金を多くしてゴールに到達可能であることがわかる。

計算量はベルマンフォードは本質で O(nm) かなりギリギリ(テストケースを考慮すると 10^9オーダーだし)だけど想定解だった。 最初、無限ループ検出のときに、 n回目のループだけではなく、 nから 2n回目までのループで更新された頂点を全列挙していたが、この場合TLEした。 @oginginがそれ n回目だけでよくね?と言ってくれてプロだった。

B - Buggy Stack Machine

問題

PUSH, POP, ADD, EMPTYの命令(ADDは、上2つPOPし、それらをADDしたものをPUSHする命令)があるスタックがあるが、上からk個の数の2進数での1の位を並べたものが  b_1b_2\ldots b_kとなった瞬間、これらk個の数がすべて消えてしまう、というバグを持っている。 クエリが与えられるので、それぞれのPOPクエリに対して、POPされる値を答えよ。しかし、それまでに不可能な操作(たとえば空のスタックに対するPOPや、要素が1以下のスタックに対するADD)が呼ばれた場合には、ERRORを答えよ。

制約

  • 5秒
  • 50テストケース
  • クエリの数は100000以下
  •  1 \le k \le 10000
  • 入力文字列は60 mebibytes以下

解法

@kenshinが最初これを担当していて、bitsetを使って1の位を覚えておくのは間に合う?と聞いてきた。見積もってみるとかなりギリギリだったけど、まあいけそうかなと言って実装する。 C++の標準のbitsetでは、大きさが異なるbitset同士を比較できないのでかなり困った。大きい方のbitsetに合わせてコンストラクトし直して比較するとTLEするので(定数倍で10倍かかる)、 頑張って比較を実装する。@kenshinが終了間際にWAで苦しんでいたのでソースコードを読んでみると、if (s.size() - (9999 - j) >= 0)というヤバそうな部分を見つける。intにキャストしたらACした。残り4分だった。

感想

さすがに想定解じゃなかった。他チームでもbitsetで書いたところが多かったみたいだが、ほとんどがTLEしてたらしい。 想定解はKMP法だったが、チームメイトは誰もKMP法を実装したことがなかったのでかなり厳しかった。

C - Constellation

読んでない。@oginginが知らない間に通してた。

D - Domination

読んでない。 @kenshinが知らない間に通してた。

E - Elevator

問題

202階のビルがあってエレベーターに n人が1階から乗る。それぞれの人には行きたい階があるが、ちょうどその階に止まらなくても、1階分だけなら階段を使って下に降りることができる。 エレベーターは1階を除いて最小でいくつの階に止まるか。

制約

  • 1秒
  • 100テストケース
  •  1 \le n \le 10000

解法

貪欲にやるだけ。202階が謎制約すぎる。

G - Good Substring

問題

ある文字列がgoodであるとは、そのいかなる部分文字列も長さ2以上の回文を含まないことである。文字列と、クエリ( i番目の文字を cに変えるというもの)が与えられるので、各クエリ後の 最長のgoodな部分文字列の長さを答えよ。

制約

  • 2秒
  • 1テストケース
  • 文字列の長さ、クエリの数ともに 10^5以下

解法

ある文字列が部分文字列に回文を含む必要十分条件はaaもしくはaba型の部分文字列を含むこと(お な じ み)なので、クエリのたびに、この位置を更新し、これらの位置の間隔で最長のものを答えればいい。 問題を言われてhoge秒で解法がわかったが、コンテスト中に読んでなかったので通せなかった。本当にもったいない

蟻本リーディング 組み合わせ編

飛行機の移動が暇なので蟻本を読んでまとめることにしました。

今回は組み合わせ問題編です。

分割数

問題

 1 \le n \le 1000個の互いに区別できない品物を 1 \le m \le n個以下に分割する方法の場合の数を 2 \le mod \le 10000で割ったあまりを求めよ。 たとえば、4つの品物を(1, 1, 2)と分割するのと(1, 2, 1)と分割するのは同じ分割だと数えます。

解法

mod素数の場合、combinationが O(1)で求められることにより、事前計算も込みで O(n + m)で解くことができます。 modが素数でない場合は、コンビネーション計算時に逆元が求まらないので、DPをします。

 dp[i][j] = i番目までの品物をちょうど j個に分割する分割数とします。

ちょうど j個に分割する方法は、 i - 1番目までの品物が j - 1個に分割されていて i番目の品物を別の1グループとする場合と、  i - 1番目までの品物が jグループに分割されていて、i番目の品物をどれかに追加する、という場合になります。

したがって、 dp[i][j] = dp[i][j - 1] + dp[i - 1][j]となります。 こうして O(nm)でこの問題が解けました。

重複組合せ

 (1 \le n \le 1000)種類の品物があり、 i番目の品物は 1 \le a_i \le 1000個あります。異なる種類の品物は区別できますが、同じ種類の品物は区別できません。これらの品物の中から 1 \le m \le 1000個選ぶ組み合わせの総数を 1 \le mod \le 10000で割った値を答えなさい。

解法

 dp[i][j] = i種類目までから j個選ぶ組み合わせというDPを考えます。この数え上げを、 i種類目のものを選ぶ場合とそうでない場合に分けて考えます。  i種類目のものを選ばない場合は dp[i - 1][j]通りですね。 i種類目のものを1つ以上選ぶ場合、 dp[i - 1][j - 1] + dp[i - 1][j - 2] + \ldots + dp[i - 1][max(0, j - a[i])]通りです。これは累積和を同時に求めながら計算すると O(nm)で計算できます(蟻本にはp.67にはこれを上手く変形して累積和なしで計算する方法も載ってあります)。