足跡-sokuseki-

りかの日進月歩の記録

AGC019 C Fountain Walk

競技プログラミング AtCoder

C - Fountain Walk

問題概要

東西方向と南北方向にそれぞれ 10^8本の道路があり、となりあう道路間の距離は 100 メートルである。すべての東西方向の道路はすべての南北方向の道路と直交し、すべての交差点は、交差する南北方向の通りの番号を x 、東西方向の通りの番号を y として組 ( x , y ) で表される。

N 個の噴水があり、 i 番目の噴水は交差点( X_i, Y_i)に設置されている。
噴水がある交差点には、交差点を中心とした半径 10 メートルの円が噴水の外周として描かれており、その内部に道路はない。

交差点( x_1 , y_1 )から交差点( x_2 , y_2 )に移動するのに歩く最短距離を求めよ。

制約

1 \le N \le 200,000
0 \le x_1, y_1, x_2, y_2 \le 10^8
0 \le X_i, Y_i \le 10^8
i \neq j のとき X_i \neq X_j
i \neq j のとき Y_i \neq Y_j
交差点( x_1 , y_1 ) , ( x_2 , y_2 ) は異なり、どちらも噴水は設置されていない

解法

交差点で曲がるときは、噴水のある交差点で曲がる方が歩く距離は短くすむ。
交差点で曲がらない場合は噴水がない方が距離は短くすむ。

よって、( x_1 , y_1 ) から ( x_2 , y_2 )に向かうときに、できるだけ噴水のある交差点を通りながら曲がりたい気持ちになる。
このとき、経由する噴水の数を最大化すると最短距離となるので、噴水の最大の数を求めたい。

簡単のため、( x_1 , y_1 ) が左下、 ( x_2 , y_2 )が右上にあるとすると、右方向と上方向の移動だけ考えればよい。
よって最短距離に関係のある噴水は、( x_1 , y_1 ) を左下、 ( x_2 , y_2 )を右上とする長方形領域に含まれる噴水のみである。

長方形の左下から右上に移動する際に経由できる噴水に最大数は、噴水の座標の集合をx座標でソートして、y座標でLISを求めてあげるとよい。（制約よりx座標やy座標が等しくなる噴水は存在しないので、特別な処理はいらない）
よって、噴水がない場合の( x_1 , y_1 ) から ( x_2 , y_2 ) への最短距離から、LIS の数だけ噴水を経由する距離を引いてあげ得ると答えがでる。（ x_1 = x_2 または y_1 = y_2 で、長方形領域（実際は直線）に噴水が含まれる場合に注意する）

LISを求めるのは O(N log N) でできるので、全体の計算量は O(N log N) となる。



Submission #2866777 - AtCoder Grand Contest 019

AGC026 B rng_10s

競技プログラミング AtCoder

問題概要

はじめジュースの在庫が A 本ある。
毎日 B 本購入され、購入後 C 本以下になると夜に D 本補充する。
永遠にジュースを B 本購入され続けるか。
クエリは T 個。

制約

T \le 300
1 \le A, B, C, D \le 10^{18}

解法

まず、 A < B の場合は、初日に B 本購入できないので、必ず No になる。
また、そうでなくても、 D < B の場合は、補充数が購入数に追いつかないのでいつか B 本購入できなくなるので、 No になる。
逆に、上の2つを満たさない場合で C \geq B-1 の場合、常に補充が間に合うので永遠に B 本購入でき、 Yes となる。

この3つの場合を除くと、残りは A \geq B かつ D \geq B かつ C < B-1 の場合である。

このときジュースを B 本買えなくなるのは、前日購入後にジュースが C 本より多くて補充されずに、かつ当日 B 本未満だったときのみである。（ D < B より補充されていないことがわかる）
つまり、ジュースの残数が C+1 以上 B-1 以下になってしまうと No となる。

y 日後までに x 回補充されたときにジュースの残数が C+1 以上 B-1 以下になったとすると
C+1 \le A + Dx - By \le B-1
が成り立つ。 mod B をとると
C+1 \le A + Dx \le B-1
となる。
式変形すると、 mod B において、 Dx が [ C+1-A , B-1-A ]の範囲に含まれると No である。
mod B において Dx のとる値は gcd( B , D ) の倍数なので、mod B において、gcd( B , D )が [ C+1-A , B-1-A ]の範囲に含まれると No であると言える。


mod B において、
l := C+1-A
r := B-1-A
とおくと、

l \le r のとき、

  • l を gcd( B , D ) で割った商と r を gcd( B , D ) で割った商が異なる
  • l が gcd( B , D ) で割り切れる

のどちらかを満たす場合のみ、 gcd( B , D )が [ l , r ]の範囲に含まれる。

l > r のとき、[ l , r ]の範囲は [ (C+1)-A + Bk , (B-1)-A + B(k+1) ]の区間の集合となっていて、これは B(k+1) を含むので、かならずgcd( B , D )が [ l , r ]の範囲に含まれる。


各クエリごとの計算量は O(1) なので、全体の計算量は O(T) 。

Submission #2864673 - AtCoder Grand Contest 026


ABC038 D プレゼント

競技プログラミング AtCoder

問題概要

N 個の箱が与えられる。 i 番目の箱は縦 h_i cm × 横 w_i cmで、縦と横を入れ替えることはできない。
ある箱は縦・横ともにより大きいサイズの箱にのみ入れることができ、ある箱は1つまでしか他の箱を入れることはできない。
このとき、箱を最大で何重の入れ子にできるかを求めよ。

制約

1 \le N \le 10^5
1 \le h_i \le 10^5
1 \le w_i \le 10^5

部分点は N \le 1000

部分点解法

dp[i][j] :=  縦icm × 横jcm の箱に入る箱の数

としてdpをする。
h_i と w_i は大きいのでそのままではdp配列の添字にはできない。よって、 N \le 1000 を利用して座圧を行う。

Submission #2825855 - AtCoder Beginner Contest 038

満点解法

「ある箱は、縦・横ともにより大きいサイズの箱にのみ入れることができる」という性質から、入れ子にする箱を小さい順にならべると、 h_i と w_i がともに単調増加になっていることがわかる。つまり、縦の長さで昇順になるように並び替えた後、横の長さでも昇順になるように順番に箱を選んでいけばいいことがわかる。

ただし、縦の長さが等しい2つの箱があった場合、どちらか片方の箱しか選択できないことに注意しなければいけない。

普通の昇順ソートを行うと、キーを2つもつ場合は、 h_i = h_j かつ w_i < w_j のとき i が先に来るように並び替えられてしまうが、これだと縦の長さでソートしたあとに横の長さだけに着目して箱を選ぶと、縦の長さが等しい箱を2つ以上選んでしまう危険性がある。
よって、 h_i = h_j かつ w_i < w_j のとき j が先に来るように並び替えるようにする。
このように縦の長さでソートした後は、横の長さのみに着目しても「ある箱は、縦・横ともにより大きいサイズの箱にのみ入れることができる」を達成することができる。

あとは横の長さを数列の要素とした最大増加部分列（LIS）を求めてあげると、それが答えとなる。


Submission #2856054 - AtCoder Beginner Contest 038

感想

この問題を機にLISを真面目に勉強してスライドをつくったので下手ですが見てください
LIS.pdf - Google ドライブ

ACM-ICPC 2018 国内予選 参加記

参加記 競技プログラミング

「priMe.caT*1」というチームで人生3回目の国内予選に参加しました。

2018年国内予選 | ACM-ICPC 2018 Asia Yokohama Regional

 

チームメンバー

ixmel先輩…主に実装担当。

T.M先輩…主に考察担当。

ぼく…テンプレ写経やサンプル図示やデバッグなどを担当。 雑用係。

 

先輩方がM1で今年でICPC引退なので、今年限りのチームです。

 

国内予選まで

 

5月中旬ごろにチームメンバーが決まったので、そこから（部の活動も含めて）週3くらいでチーム練をはじめる。あと国内予選対策のための部内合宿を行ったりした。

 

練習のおかげか、国内予選1週間前にあった模擬国内予選*2では、国内予選の参加資格のあるチームの中で7位という素晴らしい成績をとれた。いえい！w

模擬国内後はライブラリを少し追加したり去年の国内予選の後ろのほうの問題を解いたりしていた。

 

国内予選

 

大雨の影響で大学が休講&JR運休で参加が危ぶまれていたものの、3人とも大学にたどり着くことができたので、ixmel先輩の研究室で出ることに。（研究室には作業している人が何人かいて、うるさくして少し申し訳なかったです…）

 

コンテストが始まって、ぼくがテンプレを写経している間、先輩がABを読む。テンプレ写経が終わってすぐixmel先輩がAを書いてAC。その後Bの実装方針をixmel先輩と一緒に考えながら実装していた。T.M先輩はCとDの考察をしていた。Cが全探索でできそうだと言われたので、解法をきいて、Dの考察をしてもらう。Bの実装が終わってサンプルを試すと、半分より右側や上側で折った時にバグってることがわかったので（というか考慮してなかったので）、そこを直して提出してAC。ixmel先輩にCの解法を伝えて実装してもらう。Dは各チームの勝ち数はわかるので枝刈り全探索で解けることがわかって、T.M先輩にEFの考察をしてもらう。CはすぐACしたので、ixmel先輩にDを実装してもらう。Dの実装が終わってサンプルを試してみるとだいぶ遅いので枝刈りを強化したりする。その後提出するとAC。このとき全体4位で結構盛り上がった。

 

この段階でEとFの両方ともの解法がわかっていなかったので3人で考える。Eは繰り返し二乗法で二進数の足し算をやればいいのかなあという話になってixmel先輩が実装を始める。（実装だいぶ手こずっててつらそうだった。）実装が終わってサンプルを試すとサンプルがあわない。つらい。Fが1辺の長さを二分探索して下辺のy座標を決め打ちしてしゃくとりっぽくやるとできそうと思いつく。Eの考察を再びT.M先輩に任せてixmel先輩とFの実装をする。つらそう。なんとか実装を終える。サンプルをためすと合うけど遅い。計算機パワーを信じて提出することにする。Fはpcしゃんにがんばってもらう*3。T.M先輩がEの解法を思いついたのでixmel先輩が実装する。実装つらそう。実装がおわってサンプルを試すとサンプルが再びあわない。かなしいね。Fのデータセット1つめがおわりません。コンテスト時間がおわりました。（Fの計算量がやばだったことがあとで判明しました。）

 

結果は4完23位。（4完最速）

 

f:id:wk1080id:20180708164824p:plain

4完した時点で2時間くらい残っていたのであと1~2問は解きたかったなあという気持ち。4完後の考察&実装の練習をたくさんしたんだけどなあ。

 

おそらくアジア地区大会には行けるので、英語力を強化して、アジア地区では良い成績をとりたいです。先輩方は2回目のアジア地区、ぼくは初めてのアジア地区です。がんばるぞー！

 

 

*1:twitterにチーム名を書くとリンクになるのがおもしろかった

*2:2018/Practice/模擬国内予選/案内 - ACM-ICPC Japanese Alumni Group

*3:お願い、死なないでpcしゃん！あんたが今ここで倒れたら、F問題はどうなっちゃうの？時間はまだ残ってる。ここでACできたら5完できるんだから！次回「Fの解法、死す」。デュエルスタンバイ！

AOJ 2748 夏合宿の朝は早い

競技プログラミング AOJ

夏合宿の朝は早い | Aizu Online Judge

問題概要

N 人それぞれの寝坊する確率と、連絡先を知っている人が与えられる。
起きた人が連絡先を知っている人すべてにモーニングコールをするとき、全員が起きられる確率を求めよ。

1 \le N \le 100

解法

  • 誰にも起こしてもらえない人（誰にも連絡先を知られていない人）は自分で起きなければならない
  • ループしている人は、確率をまとめて1人として扱って良い

f:id:wk1080id:20180411112043p:plain

よって、連絡先を知っているという関係を有向辺にしてグラフで表現して、強連結成分（どの2頂点間も互いに行き来可能）を1つにまとめたグラフをつくり（強連結成分分解）、入次数が0の頂点の確率をかけてあげれば良い。


具体的な実装方針は

  • 強連結成分を調べるために、各頂点からdfsをしてあげて、互いに行き来可能な頂点同士をUnion-Find木で管理する（親が等しい頂点同士は同じ強連結成分に属する）
  • 各強連結成分ごとの確率を調べ、その強連結成分の入次数が0ならば、確率を答えにかけあわせる

計算量は、dfsパートは辺の数は高々 N^2 本なので O(N (N+ N^2)) 、Union-Find木を構成するパートは O(N^2 ) 、強連結成分ごとの確率を求めるのと入次数が0かどうか調べるパートが O(N^3) なので、全体で O(N^3) になる。 N が小さいので間に合う。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2770535#1

PHPでHello Worldした

PHP触ったのでメモ

拡張子は .php で、 < ?php と ? > の間にコードを書く。
test.phpという名前で以下のコードを書く。

<?php
echo "Hello World!";
?>


実行は php コマンドでできる。

$ php ./test.php
Hello World!
$

RUPC2018参加記

参加記 競技プログラミング

3/26-28に立命館大学で行われたRUPC2018に参加したので参加記を書きます。

 

day ?

ATND（https://atnd.org/events/94033 ）を公開したら尋常じゃないスピードで埋まったので怖かった。（例年の参加者は40人くらいなのに公開3日で60人に到達するというバグが発生、原因不明）

 

day1 立命館大学セット

 

はじめの自己紹介フェーズではTwitterでよく聞く名前の人がたくさんいて楽しかった。

とくに名前を言っただけで笑われてる人とかなりきりして自己紹介してる人とかいて面白かった。

 

コンテストはジャッジ側だったので、とくに何もしてなかった。clar来ないかなーと思ってAOJを眺めてた。

今年は風船配りがなかったのでゆっくりお菓子食べたり全完したチームの人とおはなししたりしてた。

3時間セットなのに40分で全完しててすごいなーと思った。

B問題はね、ぼくも何書いてるかよくわからないね、あれなに。（数学苦手並感）

 

懇親会は学内で立食形式だったので、うしうくびーとらてまるたとかと一緒にいた。

目の前でふぁぼ爆するの面白いね。

 

懇親会終わるの思ってたより早かったし草津のゲーセンに行ってマッチングをしました。

day2 会津大学セット

 

ご注文はうさぎですか？っていう素晴らしい作品があって、その主人公の香風智乃ちゃんっていう子がかわいいです。たくさん写真をとりました。

なんかうさ耳とティッピーのぬいぐるみが好評だった。

 

 

らてあさんとTABさんと事前にチームを組んでいたのでガチャ要素なし。

 

らてあさんがA担当、ぼくがB担当、TABさんがC担当して、終わったらみんなでDやるかーって言ってて、順当にABCを通す。

Dを読んで全然解法が浮かばないし他のも読むかーってなってHくらいまで分担して読む。

Fが一番できそうで、「あみだくじを1つ以上選ぶ」っていうのを見落としていることに気づいた後、3要素の置換だからあみだくじの種類は高々6種類で、それぞれは高々3つを使えば元に戻るってわかったので、あみだくじの種類を数えてあとは場合分けすれば解けるとわかる。らてあさんに実装をたのんで、TABさんと他の問題をみてた。

TABさんがHが解けそうと言っていたので方針を聞く。長さがL以下の数がSにいくつ含まれているかをO(N)で計算できればにぶたんしてできそうみたいな感じだったのでFが終わったら実装してもらうことにする。

Eがなんかグラフっぽいけどコストとかどうするんだってなって詰む。

らてあさんがFの場合分けつらそうだったのでTABさんと一緒にみてた。

Fが通った後、TABさんにHを任せて、らてあさんとGの考察をしてた。いろいろ考えた結果、2つの操作のうち前者をできるだけしてから、後者をいい感じに選んでやるのがいいとわかる。2つの組み合わせを重複無しに作っていくから2部グラフのマッチングみたいになりませんか？って言ってたけどこれ二部グラフとは限らなくない？ってなったので一般マッチングどうするの…ってずっと言ってた。

Iは幾何だしやりたくないねー(´・ｪ・｀)って言ってた。なんかN個の頂点をM個に分けて、その最小半径を求めて、その最大値の最小値を出せばよくね？ってなったけどこれ計算量間に合うのかなあって言ってた。

 そのままコンテストが終わってABCFの4完でした。

 

始まる前にコンテスト中にどれだけ長くティッピーを頭に乗せていることができるか勝負しようとか言っていた気がする。誰と勝負するつもりだったんだろう。実際はティッピーは観賞用でした。

 

懇親会は南草津駅近くの焼肉で、席が自由だったのでまたうしうくらてまるたと一緒にいました。どうすれば強くなれるかみたいな話をらてさんがしていてためになるな〜と思ってた。ぼくはキャベツを食べていました。

 

懇親会が終わった後は膳所のゲーセンに行ってマッチングをしました。紫レになりました。やったね。

 

day3 北海道大学セット

 

3日目はうしさんとチームを組む約束をしていたんですが、うしさんが2日目に遅刻してて、怖いなあと思ったのでモーニングコールをしました。電話するって事前に言ってたのにビビっててウケる。

お菓子と飲み物が尽きそうだったので学内コンビニに買いに行きました。結局それでも飲み物が足りなかったけど。

 

 うしさんとolpheさんと事前にチームを組んでいたのでガチャ要素なし。

 うしさんはAのFA担当、ぼくがB担当、olpheさんがC担当であとは適当に、っていう戦略だった。

コンテストが開始して、AをFAしてBCも通って、Eはなんかうしさんがライブラリ貼るだけって言ってて通してた。Dはグラフみたいに考えればできるってolpheさんが言ってて通してた。

あとFとGで、Fは最短路に使われる辺のうちいい感じのやつをコスト+1ずつしてあげるとよくて、それってフローに帰着できるみたいなことをolpheさんがいっててすごいなーってなった。

olpheさんがFを実装してる間、うしさんとGを考える。Gはうしさんがこれ蟻本にあるやつと全く同じじゃんって言ってて、制約が大きいのと、Pの文字列に含まれる文字とは違う文字に変換するってところが違うってことがわかる。Pに含まれる文字と違うってことは文字を変えた後に別のPと一致するというのがありえないから貪欲でできそうってうしさんに伝えたら、なんかいい感じに実装してくれた。文字列マッチング？とかよくわからないけどチーム戦なのでまあ。

Fがバグっててつらそうだったのでうしさんが先にGをとおして、みんなでFデバッグした。全完。いえい！w

 

解説が終わって、解散して、運営だったので会場の片付けをして、ゲーセン勢と合流して京都に行った。楽しかったです。

 

まとめ

 

チームガチャはできなかったけどチーム戦は楽しめたのでよかった。

知ってる人と交流するのが多かったので、知らない人にも勇気を出して話しかけような（なおコミュ障

あとうしさんのうさ耳がとてもかわいかったので次のACPCにもうさ耳を持って行こうと思いましたまる