buyoh.hateblo.jp

残念な競技プログラミング参加者

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

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

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

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

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}への最大流量を解く.