足跡-sokuseki-

りかの日進月歩の記録

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にもうさ耳を持って行こうと思いましたまる

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

競技プログラミング AtCoder

B - 異世界数式

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

問題概要

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

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

解法

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

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

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

競技プログラミング AtCoder

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 - 「みんなのプロコン」本選 オープンコンテスト