2017-06-12

2部グラフ上の重み付き最小点カバー問題を解くアルゴリズム

※ 2017/12/11更新：指数時間アルゴリズムについて記述

※ 2018/02/21更新：全体的に書き直し

※ 2018/11/02更新：2部グラフのケースのみ残し，タイトルを変更．

最小点カバー問題

辺集合E，頂点集合V，頂点重みw(v)から成るグラフGが与えられる．
頂点集合S⊆Vを考える．
全ての辺e∈Eが，Sに含まれる頂点の少なくとも1つに接続している時，SはグラフGの頂点被覆と呼ぶ．

頂点集合Sの重みの総和が最小であるようなグラフGの頂点被覆Sを1つ求めてください．

2017-06-07

7か月GitHubのContributions埋めをしました

日記?

GitHubのプロフィールページの下の方にあるやつ

他の方がやっているのをブログで見て，自分もノリで始めていました．

2017-05-22

Python3の勉強をyukicoderでやる

pythonは正直あまり好きな言語ではなかったのですが，numpyが魅力的すぎるため，競技プログラミングで少し勉強してみました．

大学の講義内容がさっと手元で動かせないんですよね．octaveは重すぎるし．

記事を書いている人の前提知識度

昔に少しだけ書いたことがあります．簡単なゲームを作りました．

notepad.exe [WP]no.014 python独習

『なんかブロックをインデントで判定してる』『タプルとかリストとかの概念がある』という雰囲気は覚えてますが，実用面は全く忘れました．

solve

No.268 ラッピング（Easy） - yukicoder

http://yukicoder.me/submissions/174424
昇順，降順ソートしたい問題．
Python2とPython3でかなり違うらしい．input()ですら違いがある．
aa.sort()でリストをソートできる．reverse=Trueと指定すれば逆順になる．
- 辞書っぽい引数の指定面白い
- 破壊的．破壊出来ないリスト(例:10行目)に対してソートしたい場合，sorted(arr)をやる．
range(N)は，Rubyでいう(0...N)みたいなもの
print aという記法はPython3では使えない．

No.136 Yet Another GCD Problem - yukicoder

http://yukicoder.me/submissions/174503
$K$ は2に固定して良い．あとは全ての組み合わせを全探索する．
PyPy3がRuntimeError．math.gcdを使うにはバージョンが足りないらしい．
- Python3は通った．
- import mathすると使える．
割り算をすると，例え整数同士でもFloat型になる．
- int(nm)でキャストできる．
maxは普通に関数として使える．Rubyみたいなインスタンスメソッドではない．

No.80 四角形を描こう - yukicoder

http://yukicoder.me/submissions/174509
思考停止全探索．xとyを適当に全部回す．
if x*2+y*2>l : continueみたいな書き方ができる．HSP *1っぽい．
提出コードからは消したけれども，プログラムを中断させたいときは，import sysしたうえでsys.exit()する．
- うっかりsys.exitと書くと終了しない．

No.204 ゴールデン・ウィーク(2) - yukicoder

http://yukicoder.me/submissions/174566
- 途中で実装方針を変えたため無駄な記述がある．
D日すべて使う必要があるかどうかが問題文・テストケースから分からない・・・と思ってたら『最大』って書いてあった．
- test13.txtを見れば分かるように，D日すべて使う必要は無い．
有給休暇を挿入する始点xを全探索する．
input()は改行文字を含まない．
++varは+ + varとして解釈される．もちろんvar++はエラー．
strのi番目の文字はstr[i]として取り出せるが，書き換えは出来ない．
- 文字列の部分書き換えをするには，str[:i]+'o'+str[i+1:]と書く必要がある．
Ruby同様，文字列の掛け算ができる．
文字列の範囲に-1を指定すると，末尾を指定したことになる．Rubyと同じ．

No.77 レンガのピラミッド - yukicoder

http://yukicoder.me/submissions/174570
理想のピラミッド△を作っておいて，差分を求めることでコストを得ることができる．あとは全探索．
- 予めブロックが足りるかどうか判定したうえで，『ブロックを除去する』を1コスト，『ブロックを積む』を0コストとして計算．
sample5.txtのように，フィールドは無限大に広いものとして考える必要がある．しかし，制約から199で抑えて良い．
- 提出コードではaa+=[0]*100という感じで無理やり増やしてる．
sum(aa)で総和が取れる．
0はFalseとして解釈される．

No.290 1010 - yukicoder

http://yukicoder.me/submissions/174571
http://yukicoder.me/submissions/174573
00,11,0101,1010が存在するかどうか調べる．
存在するかどうか調べるために，正規表現を使う．
- import reをしておく．正規表現リテラルなんてものは無い．
- r'str'と書くと，\がエスケープしなくなる．
- re.match(r,s)を使うと，先頭からのマッチしか判定しない．.*を加えるか，re.search(r,s)を使う．
  - re.search(r,s)なら場所が分かる．ただし，先頭マッチ時は0が返ってFalse扱いになるので，Noneと比較する．

*1:HotSoupProcessor

2017-05-21

4ACした(21ACする:その2)

atcoder free : yukicoder ☆3☆4 codeforces

次の未だ解いていない問題をターゲットに13AC(21-8)する．

~~yukicoder☆2（コンテスト中を除く）~~
yukicoder☆3,4
~~AtCoder ARC C（コンテスト中に解けなかったものだけカウント）~~
AtCoder ARC D,E,F
~~AtCoder AGC B,C,D~~
codeforces 不問（A問題でもカウント．英語補正）
~~codeIQ ☆3以上~~

問題名はリンクになっており，クリックすると問題ページに飛べます．

No.41 貯金箱の溜息（EASY） - yukicoder

http://yukicoder.me/submissions/174158
1円以外の通貨は111111の倍数なので，111111で割っても同じ問題で考えることができる．
割った後の値は10⁵ぐらいまで落ちるので，普通の動的計画法が使える．
…はずだが，その部分がうまくできず，解説見た．
- (111円を1個，222円を1個，111円を1個．という数え上げも含めてしまう…で悩んでた)

Problem - C - Codeforces

Educational Codeforces Round 21
http://codeforces.com/contest/808/submission/27197010
『Friend with cup i won’t be satisfied, if …』を見落とした．
codeforcesでgetchar_unlockedが使えないことを忘れてた．

No.102 トランプを奪え - yukicoder

http://yukicoder.me/submissions/174234
nim
愚直に出来ず工夫がいる．カードの枚数を4で割った余りとしても良いことに気づく必要がある．
- 弱体化デバフを掛けてメモ化再帰して解く問題は少なくないっぽい

C: Chocolate Bar - AtCoder Regular Contest 074 | AtCoder (ノーカウント)

http://arc074.contest.atcoder.jp/submissions/1295821
一瞬二分探索を書こうとした
線形探索でいける．4パターンある．

F: Lotus Leaves - AtCoder Regular Contest 074 | AtCoder

http://arc074.contest.atcoder.jp/submissions/1299054
最大流問題．初めてF解いた．
解説と若干異なって見えたので，詳しく書く．
『今乗っている葉と同じ行または同じ列に浮かんでいる葉へジャンプする』を『今乗っている葉と同じ行，列に移動できる廊下がある』と読み替えたい．
$M$ を足場の数とする．頂点数 $2HW+H+W$ ，辺の数 $5M$
全てのセルのそれぞれ $(y,x)$ に2つの頂点 $U_{(y,x)}$ と $V_{(y,x)}$ を割り当てる．
各行に頂点 $R_{y}$ ，列に頂点 $C_{x}$ を割り当てる．
もしtex:(y,x)]に足場があるなら，
- $U_{(y,x)}$ から $V_{(y,x)}$ へ流量1の辺をつなぐ．
- $V_{(y,x)}$ から $R_{y}$ ， $V_{(y,x)}$ から $C_{y}$ へ流量infの辺をつなぐ．
- $R_{y}$ から $U_{(y,x)}$ ， $C_{y}$ から $U_{(y,x)}$ へ流量infの辺をつなぐ．
$V_{S}$ から $U_{T}$ への最大流量を解く．

2017-05-17

8ACしました(21ACする:その1)

free : yukicoder ☆3☆4 codeforces

次の未だ解いていない問題をターゲットに21ACする．

~~yukicoder☆2（コンテスト中を除く）~~
yukicoder☆3,4
~~AtCoder ARC C（コンテスト中を除く）~~
~~AtCoder ARC D,E~~
~~AtCoder AGC B,C,D~~
codeforces 不問（A問題でもカウント．英語補正）
~~codeIQ ☆3以上~~

問題名はリンクになっており，クリックすると問題ページに飛べます．

No.111 あばばばば - yukicoder

http://yukicoder.me/submissions/173765
n = 1..10のケースを眺めると等差数列になっているので頑張る．
実は提出コードは偶数ケースで誤り．

No.254 文字列の構成 - yukicoder

http://yukicoder.me/submissions/173772
abababacdcdcdefefefefexyzみたいな感じの文字列を作りたい．
abababaの回文の出現回数はno111で作った関数を基に簡単に作れる(一致しない)．
二分探索を使って，どこまで減らせるかを求めて，求めた度にアウトプットする．
適当に書いても文字は足りるらしい．
クソみたいなWAした

Problem - A - Codeforces

Educational Codeforces Round 21
http://codeforces.com/contest/808/submission/27171479
全然わからない．俺たちは雰囲気ですら英語が読めない．
結局googletranslate使った
chomp忘れでWA連発

Problem - B - Codeforces

Educational Codeforces Round 21
http://codeforces.com/contest/808/submission/27171627
読めない・・・

No.324 落ちてた閉路グラフ - yukicoder

Ruby書いたらTLEした http://yukicoder.me/submissions/173807
ので，C++1zで http://yukicoder.me/submissions/173934
解説見てからACしました．この解法は思いつくべき…

No.2 素因数ゲーム - yukicoder

http://yukicoder.me/submissions/174004
愚直Nimでも通った．
いつもの戦略『愚直アルゴリズムを作って小さな解を列挙・観測』がうまく行かなかった． http://yukicoder.me/submissions/174001
もっとあたまをつかいましょう．
Nimはライブラリ化した方がよさそう．