足跡-sokuseki-

りかの日進月歩の記録

AOJ 2748 夏合宿の朝は早い

夏合宿の朝は早い | 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にもうさ耳を持って行こうと思いましたまる

COLOCON -Colopl programming contest 2018- Final B 異世界数式

B - 異世界数式

これ自力で思いつけたの嬉しい。

問題概要

数式  S が、単なる数字の列か、もしくは演算子 (+, -, *, / のいずれか) の直後で括弧(() を開き、その中に数式をいくつかカンマ (,) で区切って並べ、その後括弧 ()) を閉じるという形式で表されている。
この数式を通常の中置記法の数式に変換せよ。

制約
 1 \le |S| \le 10^5

解法

'+' '-' '*' '/'のいずれかの演算子が現れたとき、その演算子を使うのは、直後の括弧の中だけなので、スタックに積んでおき、','が現れたらスタックの一番上の演算子に置き換え、括弧が閉じたらスタックの一番上を廃棄すればよい。
さいごに、もともと数式に存在した括弧の直前の演算子を取り除けば良い(スタックに積む時に取り除いてもいいけど面倒)。

Submission #2164590 - COLOCON -Colopl programming contest 2018- Final(オープンコンテスト)

みんなのプロコン 2017 本選 A YahooYahooYahoo

A - YahooYahooYahoo

問題概要

文字列  S が与えられるので、 'yahoo'の繰り返しの文字列にするための編集距離を求めよ。

制約
 1 \le |S| \le 10^5

解法

dp[  i ][  j ] :=  S[0…i ] を「 'yahoo' の繰り返し + 'yahoo' の先頭  j 文字」の文字列にするための編集距離

としてDPする。

dp[0][0]は0、その他はINFで初期化する。

遷移は、dp[  i ][  j ] (  S[i ] と 'yahoo' の  j 文字目)を見ているとき

  • 削除 … 編集距離は1増えて、次は  S[ i+1 ] と 'yahoo' の  j 文字目を見る
  • 挿入 … 編集距離は1増えて、次は  S[i ] と 'yahoo' の  j+1 文字目を見る
  • 変更 …  S[ i ] が 'yahoo' の  j 文字目と同じならば編集距離は変化せず、異なるならば編集距離は1増える。次は  S[i+1 ] と 'yahoo' の  j+1 文字目を見る

となる(普通の編集距離のDPとほぼ同じ)。

注意が必要なのは挿入の遷移で、更新式が
dp[  i ][1] = min(dp[  i ][1], dp[  i ][0]+1);
dp[  i ][2] = min(dp[  i ][2], dp[  i ][1]+1);
dp[  i ][3] = min(dp[  i ][3], dp[  i ][2]+1);
dp[  i ][4] = min(dp[  i ][4], dp[  i ][3]+1);
dp[  i ][0] = min(dp[  i ][0], dp[  i ][4]+1);
dp[  i ][1] = min(dp[  i ][1], dp[  i ][0]+1);

と循環してしまうため、 j は0から4までを1周するだけでは足りない。(2周すれば大丈夫らしいけどたくさん回しました)


Submission #2164134 - 「みんなのプロコン」本選 オープンコンテスト

SoundHound Inc. Programming Contest 2018 (春) C 広告

C - 広告

問題概要

 r マス 横  c マスのグリッドがあり、それぞれのマスには ' * ' か ' . ' が書かれている。
' . ' のマスに、それぞれがとなり合わないように広告を打つとき、打てる広告の最大数を求めよ。

制約
 1 \le r, c \le 40

解法

' . ' のマスを頂点とし、となり合う ' . ' のマス同士を辺で結んでグラフを作ると二部グラフになる。
この問題はグラフの最大独立集合を求める問題に帰着するので、このグラフの最大マッチングを求めて、頂点数から引けばよい。

Submission #2161432 - SoundHound Inc. Programming Contest 2018 (春)

ARC061 D すぬけ君の塗り絵 / Snuke's Coloring

D - すぬけ君の塗り絵 / Snuke's Coloring

問題概要

 H マス 横  W マスの盤があり、すべて白く塗られている。
この状態から  N マスを黒く塗りつぶした。  i 番目の黒いマスは上から  a_i 行目で左から  b_i 列目のマスである。

 0 \le j \le 9 を満たす全ての  j について、盤の中に完全に含まれるすべての3行3列の連続するマス目のうち、黒いマスがちょうど  j 個あるものの個数を求めよ。

制約
 2 \le H, W \le 10^9
 1 \le N < min(10^5, H \times W)
 1 \le a_i \le H
 1 \le b_i \le W

解法


マス  (i, j) を黒く塗ったとき、3行3列の連続するマス目のうち関係するのは、中央が  (i-1, j-1), (i-1, j), (i-1, j+1),  (i, j-1), (i, j), (i, j+1),  (i+1, j-1), (i+1, j), (i+1, j+1) であるようなもの(で、かつ盤の中に完全に含まれるもの)である。また、1マスを黒く塗りつぶした時に関係がある行3列の連続するマス目は高々9個であり、  N マスを黒く塗りつぶした時に関係がある行3列の連続するマス目は高々  9N 個である。

よって、高々  9N 個を全列挙して数え上げれば、 1 \le j \le 9 を満たす全ての  j について、盤の中に完全に含まれるすべての3行3列の連続するマス目のうち、黒いマスがちょうど  j 個あるものの個数は求められる。
盤の中に完全に含まれるすべての3行3列の連続するマス目は  (H-2)(W-2) 個なので、 j = 0 のときは、「 (H-2)(W-2) -( 1 \le j \le 9 の時の答えの総和) 」が答えとなる。

Submission #2152583 - AtCoder Regular Contest 061