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

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

次の未だ解いていない問題をターゲットに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

No.254 文字列の構成 - yukicoder

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

Problem - A - Codeforces

Problem - B - Codeforces

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

No.2 素因数ゲーム - yukicoder

No.17 2つの地点に泊まりたい - yukicoder

No.59 鉄道の旅 - yukicoder

  • http://yukicoder.me/submissions/174015
  • RMQを使う.
  • Wの範囲が広いので,セグメントツリーを使うとMLE,TLEする可能性がある.
  • 座標圧縮して,Wの範囲を縮めておくと,Nぐらいで抑えられるので,セグメントツリーが使える.

yukicoder No.7 プライムナンバーゲーム / No.11 カードマッチ / No.43 野球の試合

☆2でも引っかかるところがあるのでメモ記事.

続きを読む

yukicoder No.476 No.477 No.478 No.479

No.476 No.478 No.479のwriter,No.477のtesterをしました.

人との繋がりがないのでtester集まりませんでした

yukicoder contest 155 - yukicoder

解説はyukicoderの方を参照してください.本記事では問題に絡むネタを紹介します.

もちろん,ネタバレを含みます.

続きを読む

No.459 C-VS for yukicoder

Advent Calendar Contest 2016の10日目の問題のwriterをしました.

No.459 C-VS for yukicoder - yukicoder

問題文・想定解法はリンク先の通りです.

本記事ではフローを用いた別解について書きます.結局年明けになってしまった.

続きを読む

yukicoder ☆1埋め

8つほど埋めていなかったので,今日埋めました.

ほぼ全部rubyで埋めました.inject最強.

☆1なのでやるだけ,といったところでしょうか.

No.296に関して,Ruby関連で気になった所があるので,別ブログに記事書きます

このブログについて

競技プログラミングsubmit記録としてブログ記事を上げていこうと思います.

既に多くの競プロer勢が分かりやすい解説記事をうpされているので・・・何書こう?