4ACした(21ACする:その2)
次の未だ解いていない問題をターゲットに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で割っても同じ問題で考えることができる.
- 割った後の値は105ぐらいまで落ちるので,普通の動的計画法が使える.
- …はずだが,その部分がうまくできず,解説見た.
- (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解いた.
- 解説と若干異なって見えたので,詳しく書く.
- 『今乗っている葉と同じ行または同じ列に浮かんでいる葉へジャンプする』を『今乗っている葉と同じ行,列に移動できる廊下がある』と読み替えたい.
- を足場の数とする.頂点数,辺の数
- 全てのセルのそれぞれに2つの頂点とを割り当てる.
- 各行に頂点,列に頂点を割り当てる.
- もしtex:(y,x)]に足場があるなら,
- からへ流量1の辺をつなぐ.
- から,からへ流量infの辺をつなぐ.
- から,からへ流量infの辺をつなぐ.
- からへの最大流量を解く.