#172870 (C++14) No.421 しろくろチョコレート

提出ソース

結果

問題	No.421 しろくろチョコレート
ユーザー	👑 はまやんはまやん
提出日時	2017-05-09 12:53:56
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	6 ms / 2,000 ms
コード長	8,176 bytes
コンパイル時間	2,238 ms
コンパイル使用メモリ	186,336 KB
実行使用メモリ	4,348 KB
最終ジャッジ日時	2023-10-24 14:54:02
合計ジャッジ時間	3,874 ms
ジャッジサーバーID （参考情報）	judge14 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,348 KB
testcase_01	AC	3 ms 4,348 KB
testcase_02	AC	2 ms 4,348 KB
testcase_03	AC	2 ms 4,348 KB
testcase_04	AC	2 ms 4,348 KB
testcase_05	AC	2 ms 4,348 KB
testcase_06	AC	2 ms 4,348 KB
testcase_07	AC	3 ms 4,348 KB
testcase_08	AC	2 ms 4,348 KB
testcase_09	AC	2 ms 4,348 KB
testcase_10	AC	2 ms 4,348 KB
testcase_11	AC	3 ms 4,348 KB
testcase_12	AC	2 ms 4,348 KB
testcase_13	AC	2 ms 4,348 KB
testcase_14	AC	2 ms 4,348 KB
testcase_15	AC	2 ms 4,348 KB
testcase_16	AC	4 ms 4,348 KB
testcase_17	AC	4 ms 4,348 KB
testcase_18	AC	4 ms 4,348 KB
testcase_19	AC	2 ms 4,348 KB
testcase_20	AC	4 ms 4,348 KB
testcase_21	AC	4 ms 4,348 KB
testcase_22	AC	3 ms 4,348 KB
testcase_23	AC	2 ms 4,348 KB
testcase_24	AC	2 ms 4,348 KB
testcase_25	AC	2 ms 4,348 KB
testcase_26	AC	2 ms 4,348 KB
testcase_27	AC	1 ms 4,348 KB
testcase_28	AC	2 ms 4,348 KB
testcase_29	AC	3 ms 4,348 KB
testcase_30	AC	3 ms 4,348 KB
testcase_31	AC	4 ms 4,348 KB
testcase_32	AC	3 ms 4,348 KB
testcase_33	AC	3 ms 4,348 KB
testcase_34	AC	2 ms 4,348 KB
testcase_35	AC	2 ms 4,348 KB
testcase_36	AC	3 ms 4,348 KB
testcase_37	AC	4 ms 4,348 KB
testcase_38	AC	5 ms 4,348 KB
testcase_39	AC	3 ms 4,348 KB
testcase_40	AC	3 ms 4,348 KB
testcase_41	AC	2 ms 4,348 KB
testcase_42	AC	2 ms 4,348 KB
testcase_43	AC	3 ms 4,348 KB
testcase_44	AC	4 ms 4,348 KB
testcase_45	AC	2 ms 4,348 KB
testcase_46	AC	2 ms 4,348 KB
testcase_47	AC	3 ms 4,348 KB
testcase_48	AC	4 ms 4,348 KB
testcase_49	AC	2 ms 4,348 KB
testcase_50	AC	2 ms 4,348 KB
testcase_51	AC	4 ms 4,348 KB
testcase_52	AC	3 ms 4,348 KB
testcase_53	AC	2 ms 4,348 KB
testcase_54	AC	2 ms 4,348 KB
testcase_55	AC	2 ms 4,348 KB
testcase_56	AC	2 ms 4,348 KB
testcase_57	AC	2 ms 4,348 KB
testcase_58	AC	3 ms 4,348 KB
testcase_59	AC	3 ms 4,348 KB
testcase_60	AC	5 ms 4,348 KB
testcase_61	AC	6 ms 4,348 KB
testcase_62	AC	2 ms 4,348 KB
testcase_63	AC	2 ms 4,348 KB
testcase_64	AC	2 ms 4,348 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

/*                                                                                 `
                                                                                ``  `
                                                                          . `   .g,`
                   Welcome To My Coding Space!                          .MMe  `(F(#~ `.J,
                                                                       `.M/7b. dD.N; (#=#:
                                                                     ``  db (m.#` Wl(@ jF    `
                                            ``    `  `          `   ..+kMMN;_(Y> `(TD  d$..gHN_
                                     `   ``   ......   `  `  ` `..gMB61+1+dK `- `.    .TM@^(d%
                               `` `` ..JggHHMMHHYYTHMMMNmgJ.. .kB6z?1+z1+<dD ..` .  ``.` `.V'
                              ``..+HMBYC1?1+???=?====????1vTHMNe+1+dMB"BMMM% .`je. `.. ..+@`
                            `..gM9C1+?==??==?==?=?===??=??=?1?zTMNeJTHg..``...`.,S._`.` d$  `
                      ` ` .(kBY1+==????=?=??=?=??=???=?=?=?=????+zTMm+?TMm..   ` d[ .``.M}
                       `.(M9++?=????==???=?=??=?=?=?=?=?=?=?===?==1+7Mmx?MN,``..._^`.. (F      `
     ` ` ` ` `  `      (M8++z11==?==??==??=?==?=?=?==??=??=??==??==?=+7Mm<dNg, ` .`.. (#!   `
   ` `    ..(JgH@MMMMMMB1+=??=??=?????==11??1=1?1?=1+=11?1==?=1=??=??11+WNJdMt .``.` J#! `
      .(HHYYC?1+??z>+H8+=??=?=?=???=?=?=z1&z1?==?1<dNs111?==1ux?==?=?==1zdNcW%  ..`. J#~`
     `.WNx<?1?==1=zdMD+=?==?===?=?==?===<dNNx1z??==+WMN+g&&&xdMk1??=1===???MN}`.`.`. J#` `
  `     ?MNc1=1?z?jH8+==?=?==??=jQ21=?=?(M$?WNx<1=zudMMMszOCvTHMmx+?1?z+1?zd#:..`.`. J@       `
     `` .M81==?==>dM<??===?=?=?+dNy+?=?jM@ ` ?WNe+zO>dNcHmJ1+1JMMR1?z??Ne1<d#~.`..`. dF
       (M3+1+?==?jMD+=?z1&&?v1+jMMb+=?1d#!`..``?HNx+?+HR ?Mm+1<dMMp?==<dNc<d#_.`..`.`dF  `
      ,MHmax111=<dNC?=?=(M#ugH9M#W#6+?(M'`.`.... ?WNe<dM: .TNm<dN?Nm<=zzMR+M@` .``.. dF `
   ` ``  _CM$+??1d#<==?=>dM9+?(MF(MI+jMf .`.``.`.. (TNaHr`.`.TNmN:(MR+?zMK(M$` `.`.``dF        `
          J#<=1<jME+1?=1d9Mn1<jN! qN(d@_.`..`.`.`.```-7Y5.....,TB! (MmJ+MH(M: ...`.`.d$`
     `   .M$iggWWMR+1?<dDjMNxjMB  .NgN``..``.`.``....`.d#Y"""YWNg.  .WNxW#J@ .`.`.``.H: `
         _Y""!  .M$jm+?1zd#TNzM}.. ?M% .`..`.`..``.`..  .+NMNg,.?Mm._ ?NMNM$ ..`..``.#    `
                .HPj#z=?<d#_WM#:.JgHH6 .  `.`.`..``.`.`jMMF`.MMN..TN,  ?@jM}`..`.`.`JD   `
           ` `   dbjMI?=+MF`.7XME^_.--,. ..`.``.`..`.`.M#XNgjNdMR. ?N-.  (#~``.``.. d%
              `  d#<WR1z(Mt` (#' (MMBTHNe.`..`..`.`.` .M#UMMMM#W#_. zN.  dF`.`...`..H}  `
                 ?MO(N+?jM:`.M!`.M9N+.-MMR `..`..`.`.`_?MmTMMMwM#~...H: .H}`..`..` (#`
          `  `  ` WNJMR<dN_ JB  dNwMMMMNdM[`.`.`.`.`..  ,TNNggMB! .` ~ `(M `.`.``. dF
                 `.MdMNoW@ `JP `(MKdMMNMdM}`.`..`.`.`.... .??!`.`.`..`..dD .`....`.W'
                   ?MMMMMP `(R`..?MmyUWQMB ..`..`.`.`..`..`..`.`.`_`-.gM#!.`.``.``.@
             `   `` _7NTMN.`.H/`. ,TMMB"! .``.`.`..`.``.``.`..`.`. .,NIdb` .`..`  j$
          `           Wm.M;`._!..`.`...`_`...``..   ...(+ga,`.....``(NjMr`..`... .#:
                      .MpdN_.`. ``.``.`..`..(-JggkWY9YC<>;?Wp .``.` J#>dN, ..``.`dF`
                      `_UmMn .`..`..`..`. JMYT1<;;;>>>>>;>>?Wo ..`. dK1=dN,`..``.MN+
                        .dMMe .`.``.`.`.` d#<;>>>>;>>>>;>>>>(N,`.. -MK1llvWm.   JM?Mp. ` `
                     ` .M9+?Me`.`..`.`.`` JN(>;>>;>>;>>>;>>><db` (kH5lllllzXMm.-NNszWm ` `
                `     (#1+???Hm, ..`..`..`(N:>>>>>;>>>>>;>>><d@_.JNZIlllllllzvTWB6zlJMp      `
                ` `` j@1+==?1zvHm.`...`....Hc<>>>>>>>>>>>>><(W$(M8TIllllllllllllllllzvMo ` `   `
                    (#1?==1?===z?TNa,.` `` (Ne<<>>>>><;><;jgMMY1HK1lllllllllllllllllllJMp `
                   .Ne&g&x1=?=?==?1zTHNmJ-...dNgJ++++&ggMH9=~ .M9Izlllllllllllllllllll1WF    `
                `   _???MK<=??=??1z?(MM@!d#M#Y""""=<!!~```  .d8Illllllll=lll=lllllllzudY `     `
                `       dH<?+uev?=1uMM^  d@vN&.`...`.`.`.-JH91zzl=llllllllllll=lzllzd#'  `  `
                        ,MNMBHNIvjdB(D ` d#=zTNm.....JgHM9Izlllludk=zl=ll=llllllvug#^
                     ` `    `.MmgM=+M$ ` d#zzO1vUUUU9TI=lllzzO1dKT#zOlllll=llll=dM=
                         `   `(Y^ JBdr ` dNmxzIlllllllllllz1ug#= .My1llllllllllzdD `
                           `     j@1dR ``(#~THaxl=lzzlzzzugW"!` ``,Nzlzz=lllllzd#:  `
                            ` ` .#z=d# ``(#_` .7THWQkWHB"^ ` `   ` ?NsIzzlll=ljM\
                       `   ``  (M6zldN_` .M| `    ``    `           .WezllzllzH% `` `
                     `    `  .+#Czl=dM;`  dR                    `     4m+zll1dD
                        `  `.d@1llzvdMb   ,#   `                   `   ?Wmxzdf                     */
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
template<class V> struct MaxFlow {
    struct edge { int to, reve; V cap; edge(int t, int r, V c) : to(t), reve(r), cap(c) {} };
    int MV; vector<vector<edge>> E; vector<int> itr, lev;
    MaxFlow() {} MaxFlow(int n) { init(n); }
    void init(int n) { MV = n; itr = vector<int>(MV), lev = vector<int>(MV); E = vector<vector<edge>>(MV); }
    void add_edge(int x, int y, V cap, bool undir = false) { E[x].push_back(edge(y, (int)E[y].size(), cap));
        E[y].push_back(edge(x, (int)E[x].size() - 1, undir ? cap : 0)); }
    void bfs(int cur) { rep(i, 0, MV) lev[i] = -1; queue<int> q; lev[cur] = 0; q.push(cur);
        while (q.size()) { int v = q.front(); q.pop();
        for(auto e : E[v]) if (e.cap>0 && lev[e.to]<0) lev[e.to] = lev[v] + 1, q.push(e.to); } }
    V dfs(int from, int to, V cf) { if (from == to) return cf;
        for (; itr[from]<E[from].size(); itr[from]++) {
            edge* e = &E[from][itr[from]]; if (e->cap>0 && lev[from]<lev[e->to]) { 
                V f = dfs(e->to, to, min(cf, e->cap));
                if (f>0) { e->cap -= f; E[e->to][e->reve].cap += f; return f; }
            } } return 0; }
    V maxflow(int from, int to) { V fl = 0, tf;
        while (1) { bfs(from); if (lev[to]<0) return fl;
            rep(i, 0, MV) itr[i] = 0; while ((tf = dfs(from, to, numeric_limits<V>::max()))>0) fl += tf;
        }
    }
};
struct BipartiteMatching {
    int N, M; MaxFlow<int> mf;
    BipartiteMatching(int n, int m) : N(n), M(m) { mf.init(n + m + 2); }
    void add_edge(int a, int b) { mf.add_edge(a, N + b, 1); }
    int match() {
        rep(a, 0, N) mf.add_edge(N + M, a, 1);
        rep(b, 0, M) mf.add_edge(N + b, N + M + 1, 1);
        return mf.maxflow(N + M, N + M + 1); }
    int whois(int a) { // マッチング相手を返す(無いなら-1)
        for (auto e : mf.E[a]) if (e.cap == 0) return e.to - N;
        return -1;
    }
};
//---------------------------------------------------------------------------------------------------





int H, W;
string S[50];
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { -1, 0, 1, 0 };
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(i, 0, H) cin >> S[i];

    vector<int> b, w;
    rep(y, 0, H) rep(x, 0, W) {
        if (S[y][x] == 'b') b.push_back(y * W + x);
        if (S[y][x] == 'w') w.push_back(y * W + x);
    }
    sort(b.begin(), b.end());
    sort(w.begin(), w.end());

    BipartiteMatching bm(b.size(), w.size());
    rep(y, 0, H) rep(x, 0, W) if(S[y][x] == 'b'){
        rep(i, 0, 4) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx < 0 || W <= xx) continue;
            if (yy < 0 || H <= yy) continue;
            if (S[yy][xx] != 'w') continue;

            int bb = lower_bound(b.begin(), b.end(), y * W + x) - b.begin();
            int ww = lower_bound(w.begin(), w.end(), yy * W + xx) - w.begin();
            bm.add_edge(bb, ww);
        }
    }

    int p100 = bm.match();

    int rb = b.size() - p100;
    int rw = w.size() - p100;
    int p10 = min(rb, rw);

    int ans = 100 * p100 + 10 * p10 + (b.size() - p100 - p10) + (w.size() - p100 - p10);
    cout << ans << endl;
}

yukicoder

結果

テストケース

ソースコード