0x19f (Shinya Kato) の日報

主にプログラミング関連の話をします

7/22 ソフトウェア工学と言語処理系の期末おわり

ソフトウェア工学は微妙, 言語処理系はぼちぼち(?).

ソフトウェア工学は正直ただの暗記ゲーで内容的にもそんなに面白いものではないので退屈だった.

言語処理系はちゃんと勉強してみると面白かったのだけれど, もう少しちゃんとしたレジュメ配って欲しいっす.

あと, 試験問題はバリエーションがなくてめちゃくちゃ退屈.

 

ABC/ARC D問題埋め

  • D: Alice&Brown - AtCoder Regular Contest 072 | AtCoder [解答]
    MiniMaxで全探索するプログラムを書いて0 <= X, Y <= 20ぐらいの答えを全部試してみたら, |X - Y| <= 1の時はBrownが, それ以外の時はAliceが勝ったのでそこから答えを推測.
    たまには試してみるのも大事ですね.

  • D: 井井井 / ### - AtCoder Regular Contest 071 | AtCoder [解答]
    あるi, jについてx = X[i], x = X[i+1], y = Y[j], y = Y[j + 1]で囲まれる長方形が何回足されることになるかを考える.
    これはこの長方形を含むような長方形がいくつあるかと同じなので, (i + 1) * (N - i - 1) * (j + 1) * (M - j - 1)と等しくなる.
    よって, 求める値は\sum_{i = 0}^{N - 1} \sum_{j = 0}^{M - 1} (i + 1) * (N - i - 1) * (j + 1) * (M - j - 1) * (X[i + 1] - X[i]) * (Y[i + 1] - Y[i]).
    この式をよく見るてiとjをそれぞれ総和と関係ないところから外すと, (\sum_{i = 0}^{N - 1} (i + 1) * (N - i - 1) * (X[i + 1] - X[i])) * (\sum_{j = 0}^{M - 1}  (j + 1) * (M - j - 1) * (Y[i + 1] - Y[i]))となる.
    あとは, X/Y方向の総和をそれぞれ求めて最後に掛け合わせれば, O(N + M)で求められる.

  • D: Maximum Average Sets - AtCoder Beginner Contest 057 | AtCoder [解答]
    平均の方は価値の降順にソートして, 先頭からA個の平均を求める.
    組み合わせの数は, 基本的にはコンビネーションを求めて足し上げるだけ.
    ソート列のA番目の値がN個の中にいくつ含まれるか(=d)と先頭からA個までの中にいくつ含まれるか(=c)を数える.
    平均を求めるときに, 2種類以上の価値のものを使っていれば答えはcombination(d, c).
    そうでない場合は, 全て同じ値を使う組み合わせをA個からB個まで足しあげれば良い.