はまやんはまやんはまやん

hamayanhamayan's blog

Swap and Flip [Keyence Programming Contest 2020 D]

https://atcoder.jp/contests/keyence2020/tasks/keyence2020_d

前提知識

解説

https://atcoder.jp/contests/keyence2020/submissions/9583217

とある性質がある。
「位置が1だけずれると同時に裏返されるため、位置と色のパリティ(2で割った余り)は必ず一致するか、必ず異なる」
つまり、0,2,4番目にあるカードは0,2,4では赤であるが、1,3,5では青になる。
そして、これが満たされれば操作によって、その位置を実現できる。

制約からBitDP感が伝わってくるので、その方針で考えるといける。
以下、0-indexedで考える。

dp[msk][lst] := 既に整列済みの集合がmskで、最後の値がlstであるときの操作の最小値
これで、未選択のi番目のカードを列の末尾に追加することを考える。
既にdone枚選択されている場合、done番目に追加されることになる。
もともとi番目にあるので、abs(i - done)が位置の差となる。
このパリティが0であれば、赤が表になっていて、1であれば青が表になっている。
赤青が分かるということは数が確定するということである。
末尾はlstであるので、これ未満であれば置くことはできない。
さて、おける時に、操作の回数はどうなるだろうか。
今回も問題はバブルソートと実はほぼ同じである。
バブルソートでは転置数の総和が最小総和回数である。
よって、今の段階での転置数を見よう。
i番目より前のカードについて(元々前にある)、選択されていない(その数より大きい位置に置かれる予定)ものの数が転置数である。
これを愚直に数える。

セオリー通りに計算量解析すると、O(2N N3)であり、厳しい気もするが、
DP更新時に更新元がINFであれば計算しないなどの枝刈りを行うと通る。

int N, AB[18][2];
int dp[1 << 18][51];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> AB[i][0];
    rep(i, 0, N) cin >> AB[i][1];

    rep(msk, 0, 1 << N) rep(lst, 0, 51) dp[msk][lst] = inf;

    dp[0][0] = 0;
    rep(msk, 0, 1 << N) rep(lst, 0, 51) if (dp[msk][lst] != inf) {
        int done = 0;
        rep(i, 0, N) if (msk & (1 << i)) done++;

        rep(i, 0, N) {
            if (msk & (1 << i)) continue;

            int p = abs(done - i) % 2;
            if (AB[i][p] < lst) continue;

            int c = 0;
            rep(j, 0, i) if (!(msk & (1 << j))) c++;

            chmin(dp[msk | (1 << i)][AB[i][p]], dp[msk][lst] + c);
        }
    }

    int ans = inf;
    rep(lst, 0, 51) chmin(ans, dp[(1 << N) - 1][lst]);

    if (ans == inf) ans = -1;
    cout << ans << endl;
}

Subarray Sum [Keyence Programming Contest 2020 C]

https://atcoder.jp/contests/keyence2020/tasks/keyence2020_c

解説

https://atcoder.jp/contests/keyence2020/submissions/9582827

問題にかなりの弱点がある。
0≦K≦Nの部分である。
よって、大体はSをK個並べて、残りをINFにすればいい。
INFは最大が109なので、これにしておく。

この場合、S=109の時におかしくなる。
SをK個並べて、残りは1にしておこう。
1を集めても109にすることはできないためである。

int N, K, S;
int MA = 1000000000;
int ans[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K >> S;

    if (S == MA) {
        rep(i, 0, K) ans[i] = MA;
        rep(i, K, N) ans[i] = 1;
    }
    else {
        rep(i, 0, K) ans[i] = S;
        rep(i, K, N) ans[i] = MA;
    }

    rep(i, 0, N) {
        if(i) printf(" ");
        printf("%d", ans[i]);
    }
    printf("\n");
}

Robot Arms [Keyence Programming Contest 2020 B]

https://atcoder.jp/contests/keyence2020/tasks/keyence2020_b

前提知識

解説

https://atcoder.jp/contests/keyence2020/submissions/9582655

DPをしよう。
200点でなので想定解は貪欲なんだろうという気もするが、DPでさくっとかけるので書いてしまう。
dp[i] := i番目まで残すか確定していて、i番目のロボットを残した場合の個数最大値

どうやってこれで解くんだろうというのを説明する。
ロボットを左から残していくかを考えると、i番目のロボットを置くと、X[i]+L[i]-1までは占領してしまう。
かつ、i番目のロボットがおけるのは、最後にロボットとその手がかかる領域がX[i]-L[i]までの場合である。
これは既に置かれているロボットのX[i]+L[i]-1が関係してくる。
つまり、順番はX[i]+L[i]の昇順に置かれることになる。
よって、これでソートしておくと、順番に置くかどうかの問題となり、DPに帰着させることができる。

dp[i+1]を更新したい時に、i番目のロボットがおけるかを考えたいが、lower_boundを使って、pre番目のロボットまでおけることを調べよう。
すると、dp[i+1]はmax(dp[0], dp[1], ..., dp[pre]) + 1となるが、計算しながら、
dp[i] := i番目まで残すか確定している場合の個数最大値
を累積和っぽく求めておくと、達成できる。

追記:区間スケジューリング問題でしたね。ホントやわ。
{ X[i]+L[i], X[i]-L[i] }で配列入れて、ソートして、区間の右端が小さいものから貪欲に取って、カウントしていく。

int N;
pair<int, int> robots[101010];
int dp[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) {
        int x, l;
        cin >> x >> l;
        robots[i] = { x + l, l };
    }
    sort(robots, robots + N);

    rep(i, 0, N) {
        chmax(dp[i + 1], dp[i]);
        
        int x = robots[i].first - robots[i].second;
        int l = robots[i].second;

        auto ite = lower_bound(robots, robots + N, make_pair(x - l, inf));
        int pre = ite - robots;
        chmax(dp[i + 1], dp[pre] + 1);
    }

    cout << dp[N] << endl;
}

Painting [Keyence Programming Contest 2020 A]

https://atcoder.jp/contests/keyence2020/tasks/keyence2020_a

解説

https://atcoder.jp/contests/keyence2020/submissions/9581432

なるべく最小回数でマスを塗っていきたいが、縦横塗れるのが大きい方でずっと塗ればいい。
これが上界であることは自明なので、H,Wの大きい方で、Nを切り上げで割ればいい。
a/bの切り上げは、(a+b-1)/bとすると求められる。

int H, W, N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> N;

    int ma = max(H, W);
    int ans = (N + ma - 1) / ma;
    cout << ans << endl;
}

ロギングベストプラクティスの個人的所感

LOGGING BEST PRACTICES: THE 13 YOU SHOULD KNOW

  • https://www.scalyr.com/blog/the-10-commandments-of-logging/
  • ロギングに関するプラクティス集
  • 原文はCC BY 4.0であるので、本記事もそれを継承しておく(CCってライセンスの継承義務ってあるんかな?)
  • 日本語訳はしっかりしたやつが2つもあるので、完璧な本文は書かない 1 2
  • 所感を以下に書いていく

所感

基礎的なことが網羅されてた。
ラクティス集の全項目に対しては完全肯定であり、自分の考えを追記していると明記しておく。

1. 自前でログを書くな

  • ライブラリを使え
  • printfは最悪
  • ローテーション機能とかのことも書いてあった。
  • 確かに、printfっぽいやつ使うにしてもラッパは必要。出力先も変わるかもしれないしね

2. ログレベルを入れる

  • TRACE, DEBUG, INFO, NOTICE, WARN, ERROR, FATALが紹介されてる
  • 主要なロガーでは採用されているので、なんとなく理解してるだろう

3. 適切なログカテゴリに入れよ

  • あまり馴染みがない概念だったが、Javaのロギングライブラリだと、com.daysofwonder.rankingのように階層化して定義できる?
  • カテゴリごとにconfigutrationが作れるっぽい
  • 確かにログを追っていく時にグループや包含関係などがあると読みやすくなる
  • jsのログはそんな感じにできたはず

4. 意味のあるログメッセージを書こう

  • そうは言ってもという感じがある
  • これを実現するには、改善するための情報(おそらく状況の改善)を入れたり、操作の目的を入れる
    • 確かにエラーメッセージには、状況とその対処が含まれてることが望ましい
  • 重要なこととして他のメッセージとつながっているように出力しないことが挙げられている
    • ログレベルの違いで同時に出ない、非同期処理だと順番が乱れる可能性があるので、見にくくなる
    • なるほど。確かに

5. 英語でログを書こう

  • 文字コードによらずASCIIは使えるため
  • あと、翻訳も必要ない
  • あと、略語が使えるってのもいいらしい

6. ログメッセージにコンテクストを含める

  • 日本人が良くわからない英単語No.1「コンテクスト」
  • 結果だけを書くなというtips
  • 「Transaction failed」だけじゃ何もわからない
  • 「Transaction 234532 failed: cc number checksum incorrect」とするとコンテクストが分かる
  • 確かにという感じ。Exceptionのスタックトレースを出力すればコンテクストは分かるが、そうじゃないやつは確かに気をつけなくては

7. 機械がパース可能なログを残す

  • ドラゴンクエストXを支える技術」で書かれていたロギングノウハウを思い出す
  • ログは障害修正だけでなく、様々な用途で使用される
  • で、常時出てるログは得てして莫大になる
  • 機械が扱えるようになっているのは当然だろう
  • 疑問だが、ExceptionをToStringそのままで出すとログカチャカチャになるけど、各所どういう対応してるんだろう

8. でも、人間も読みやすく

  • この辺は7との兼ね合いもあるかなとも思うのだが、readableであるというのはどういうことでも重要
  • ただIDを出力するより、ユーザー名を添える方が分かりやすいかもしれない
  • 機械的なIDも必要だが、時にはパット見て分かるような配慮もあって然るべきだろう

9. 多すぎず、少なすぎず

  • それはそうという感じ
  • ログを出力しすぎて問題が発生することもあるし、少ないと障害特定に結びつかないかもしれない
  • 機械によるアシストがあっても、最終的に読むのは人間である。過不足無いデータが最適
  • (とは言っても難しいよね)
  • 個人的にはログローテーションとログを残したい期間を決めて、ちゃんと残る量で最大量出せばいいんじゃないかなと思ってる
    • ランニング試験でログの量を確認する感じ

10. 観客を考える

  • どういった人が読むのかを考える
  • readableと同じような感じであるが、エンドユーザーが読むのか、システム管理者が読むのか、開発者が読むのかでは変わってくる
  • ログといえば、管理者か開発者が読むものというイメージがあるが、こじつけで考えると、エンドユーザーがログイン記録などのログを確認する機会もあるだろう
  • ログレベルとセットで考えていけばいいのではないか

11. ログは障害調査目的だけではない

  • 3つの例が紹介されている
  • 監査目的:例えばログイン記録のようなもの。ActiveDirectoryみたいなやつを運用してたりすると、あれねという感じがする
  • プロファイル目的:性能を確認する目的がある。ログは時間も記録する。この時間を使って性能を見ることもできるだろう
  • 統計目的:ログを見ることでシステム全体の動作状況が把握できる。これを活用すれば、負荷がかかっている時間帯やリクエストの偏りなどの統計情報も得られる
  • ただ、取っていけば上が実現できるというものでもないので、あらかじめ目的がはっきりとしたログを取るべき

12. ベンダーロックインを避ける

  • ログに限ったことではないが、ロギングは広域に渡って使われるので、特にラッパーのようなものを用意しておくべきであるという話だろう

13. センシティブ情報を含めない

  • パスワードがクレジット番号など、ヤバい個人情報はロギングしない
  • デバッグログなどにも含めてはいけない
  • この辺はどこまでOKか難しいよね。IPアドレスは大丈夫か?とか
  • ヤバそうだけどどっかに書いとかないといけない場合は、暗号化してDBに入れよう
  • GDPRへのリンクもあった。そういえばそれもあったな

補足

ロギングの記事を書こうとしていた最中に記事を発見してしまったので、上にかかれていなくて、元々書こうとしていた事項も補足しておく。

ログ出力のオーバーヘッドに注意する

  • ドラゴンクエストXを支える技術」にしくじり先生が書いてある
  • ほんとに開発時だけログを出したいし、スピードを落としたくない場合は、ログのところを#ifdefみたいなやつで根こそぎ抜く技もある
  • Effective C++にゼロコストのログ削除方法が書いてあったような気がするけど、10年以上前の記憶なので定かじゃないな…

クライアント環境で起こった障害ログをどう送るか

  • クラッシュレポートを送ってもらう術がある。iOSだといろんなライブラリを使ったことがあるが、実際のアプリではどれくらい使われているんだろうか
  • winアプリとかだと障害ログを送ってもらう仕組みも含めたりする(クラッシュレポートか、やりすぎな感じもするけど)
  • 必要かどうか。送るまでやらなくても障害情報をまとめる機能があってもいいだろう。QA部門からの障害レポートでも役立つだろう

時間を遡ってログはとれない

  • 場合によってはエラーが発生したときには、重要な情報が失われていることがある
  • 多少の無駄があっても、エラーが発生した時に必要な情報は全てログで出せるようにしておこう
  • 障害発生時に、ここがみたいんだよなぁってのがある

ディスク容量は有限

  • ログでは長期運用が考えられる場合は、ログローテーションなどのログの容量管理を行おう
  • とりあえず出して測定しながら調整するのがよい
  • 何が必要かってのは分かりにくいよね

選び方のスコア [yukicoder 972]

https://yukicoder.me/problems/no/972

解説

https://yukicoder.me/submissions/419463

難しい問題でした。

まず、kは奇数個のみ考えればいい。
kが偶数個の場合は中央値の計算に使われる2つのうち、大きい方を削除してもSの値が変わらないためである。
これで中央値はある要素になることが確定したので、
中央値を全探索対象とする。

A[i]を中央値としたとき、残る変数はkである。
kは奇数であるとわかっているので、k=2s+1としておこう。
すると、残りの選択肢は、A[i]未満の数をs個、A[i]より大きい数をs個選択できる。
これで最適な選択はなんだろうか。
A[i]未満の数-A[i]は必ず負になるが、これは最小化したい。よって、A[i]未満の数は大きい方からs個取ればいい。
A[i]より大きい数-A[i]は必ず正になるが、これは最大化したい。よって、A[i]より大きい数は大きい方からs個取ればいい。

sを変数とすると、
(A[i]未満の数の大きい方からs個の総和) + (A[i]より大きい数の大きい方からs個の総和) + A[i] - A[i] (2s + 1)
より、
(A[i]未満の数の大きい方からs個の総和) + (A[i]より大きい数の大きい方からs個の総和) + - A[i] 2s
となる。
これに立ち向かうが、解説では、差分を取ると単調減少することが紹介されている。
なるほどという感じである。差分が単調減少するということは上に凸になるので、自分は三分探索した。

考察時にはA[i]の値が全て異なるっぽく考えてるが、実際には同じ値のものもある。
これを解消するには、A[i]をソートしておき、A[i]<A[j]と考えていたところを、i<jであればA[i]<A[j]と解釈すれば
上手く扱うことができる。これは競プロにおいて、一般的なテクである。

int N, A[201010];
//---------------------------------------------------------------------------------------------------
ll B[201010];
// [l,r]
ll get(int l, int r) {
    ll res = B[r];
    if (l) res -= B[l - 1];
    return res;
}
//---------------------------------------------------------------------------------------------------
int cent;
ll f(int s) {
    if (s == 0) return 0;
    ll res = get(cent - s, cent - 1) + get(N - s, N - 1) - 1LL * A[cent] * s * 2;
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    sort(A, A + N);

    B[0] = A[0];
    rep(i, 1, N) B[i] = B[i - 1] + A[i];

    ll ans = 0;
    rep(i, 0, N) {
        cent = i;

        int ma = min(i, N - i - 1);

        int s = findMax(0, ma + 1, f);
        chmax(ans, f(s));
    }
    cout << ans << endl;
}

いたずらっ子 [yukicoder 971]

https://yukicoder.me/problems/no/971

解説

https://yukicoder.me/submissions/418655

まず、重要な性質に気づく必要がある。
「いたずらっ子によって最初の場所に戻されたとしても、始点から終点まで通るパスは、毎回同じである。」
戻されたときに違うルートを通った方が最適な場合は最初からそのルートを通るのが最適であるためである。

あとは、DPで計算していく。
dp[y][x] := 区間(y, x)に移動するのにかかる最短時間
移動はy++かx++しかないので、グラフはDAGとなる。
よって、ダイクストラまでは必要なく、DPで計算すればいい。
いたずらっ子によるロスタイムは、区間(y,x)で捕まったら、(x+y)である(x,yは0-indexed)。

int H, W;
string A[2020];
int dp[2020][2020];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> A[y];

    rep(y, 0, H) rep(x, 0, W) dp[y][x] = inf;
    dp[0][0] = 0;

    rep(y, 0, H) rep(x, 0, W) {
        int d = A[y][x] == 'k' ? x + y : 0;
        if (x) chmin(dp[y][x], dp[y][x - 1] + 1 + d);
        if (y) chmin(dp[y][x], dp[y - 1][x] + 1 + d);
    }

    cout << dp[H - 1][W - 1] << endl;
}