LeetCode: Max Dot Product of Two Subsequences (Hard)

問題はこちら

leetcode.com

二つの配列 nums1 と nums2 が与えられる。同じ長さの空でない部分列を nums1, nums2 から順序を変えずに選んだ時の内積の最大値を求めよ。

• 
• 

考え方

DPの典型問題（解けませんでしたが... ）

LCSと関わりが深いので、こちらの記事でLCSについて勉強しておくと良いかもしれない。

hiramekun.hatenablog.com

全ての部分列を考慮する方法だと、 程度かかり到底間に合わない。

ここで注目したいのが、nums1[i1] と nums2[i2] を使用した時、次に使用するのはそれぞれ i1, i2 以降のindexになるということだ。つまり、 「index(i1, i2) という状態は、それ以前のindexからしか到達しない」 ということ。

ここまでわかると、DPで解けることがわかる。というのも、題意をみたすように index i1, i2 の状態に来るには、なるべく大きい値を取るようにして遷移してくればよいためだ。

よって、DPの遷移は以下のようになる

• dp[i1][i2]: nums1 の 番目、 nums2 の 番目 までの部分列における内積の最大値。
• nums1[i1] と nums2[i2] を使用する時
  • 題意では空でない部分列を求めるため、使用する場合は今までの値を使うか、それともこの場所から使用をスタートするかを選ぶことができる。
  • dp[i1][i2] = max(dp[i1][i2], max(0, dp[i1 - 1][i2 - 1]) + nums1[i1 - 1] * nums2[i2 - 1]
• nums[i1] とnums2[i2] を使用しない時
  • それぞれ、一つ隣のindexから遷移し、大きければ採用する。
  • dp[i1][i2] = max(dp[i1][i2 - 1], dp[i1][i2])
  • dp[i1][i2] = max(dp[i1 - 1][i2], dp[i1][i2])

解答

https://leetcode.com/submissions/detail/343972017/

class Solution {
public:
    int maxDotProduct(vector<int> &nums1, vector<int> &nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, INT_MIN));
        dp[0][0] = 0;
        for (int i1 = 1; i1 <= n1; ++i1) {
            for (int i2 = 1; i2 <= n2; ++i2) {
                dp[i1][i2] = max(dp[i1][i2 - 1], dp[i1][i2]);
                dp[i1][i2] = max(dp[i1 - 1][i2], dp[i1][i2]);
                dp[i1][i2] = max(dp[i1][i2],
                                 max(0, dp[i1 - 1][i2 - 1]) + nums1[i1 - 1] * nums2[i2 - 1]);
            }
        }
        return dp[n1][n2];
    }
};

『テストは何を測るのか - 項目反応理論の考え方』まとめ1

項目反応理論のお勉強。公平な試験をどのように作っていくのか、理論的背景を学ぶ。

テストは何を測るのか―項目反応理論の考え方

第1章 試験という「道具」を理解する

1.1 試験は「能力を測定するための道具=問題」の集合体

• 受験者間で比較可能な尺度を用意し、その尺度を用いて受験者の能力を表示する。
• 【構成概念】：一つの尺度で表すことができる対象。
• 試験の設計とは、測りたい対象を構成概念として定義しておき、多数の問題に対する受験者の反応を手がかりに、尺度を構成する手続きのこと。

1.2 試験と擬似性格検査とアンケート

能力をどうやって問うのか？

• 【擬似性格検査】：結果も重要視されないような性格検査のこと。（本書定義）
• 擬似性格検査は問おうとしている構成概念に対して、明確な定義を与える必要がある。
  • 【概念的定義】：他の事象との関連性を列挙することで、抽象的概念を具体化していく定義の方法。
  • 【操作的定義】：問題に正解できれば能力が高いとする定義の方法。
    • 【妥当性の検証】：概念的定義に基づいて操作的定義が成り立つのであり、操作的定義により作成された問題が、概念的定義に基づく「本当に測りたい内容」と一致しているのかどうか検討する必要がある。

1.3 単一の尺度のによる測定

何が測定される対象かということが重要な検討要素。全ての試験において、試験で測定しようとしている構成概念を統一する必要がある。

• 尺度は階層性を持つ（英語能力という上位尺度に対して、スピーキングが下位尺度、のように）。
• 統一された単一尺度を扱うことで、試験のスコアに具体的な意味づけをすることが可能。
• 学力の規準となる集団を定め、その集団と比較可能なように尺度を作ることが必要。
  • 【標準化】：規準となる集団と比較可能なように尺度を構成する手続き。
• 多くの試験では、「スコアのでたは、今たまたま選ばれた受験者の実力を反映したものであり、その背景には多数の受験者が存在する。そして、それら多数の受験者の能力は、正規分布をしている」という仮定を置くことが一般的。
  • テストを受けていないが存在を仮定することができる多数の受験者を母集団と呼ぶ。
  • 実際に試験を受験したものをサンプルと呼ぶ。
• 【標準化テスト】：規準集団を決め、学力の尺度を規準集団上で表示する標準化の手続きを経た試験。
• 受験者の能力レベルに依存しない形の問題の難易度がわかれば、その難易度を調整することにより、複数の試験のスコアを比較することができる。→ 因子分析（後述）
• 問題にはそれ固有の特性（項目特性）がある。難易度、識別力等々。 規準集団における原点と単位を定義し、続く試験の原点と単位を規準集団上に合わせる。
• 尺度得点の計算
  • 規準集団の受験者が問題を解いた場合の、それぞれの問題に関する難易度の情報が必要。規準集団の受験者にとってどの問題がどの程度難しかったかがわかれば、試験の結果得られた受験者の正誤データを手掛かりに、受験者の能力が規準集団状でどこに位置するかを推測することができる。

1.4 ハイ・ステークスな試験のために：信頼性と妥当性の確保

「質の良い試験」とはなにか？そのためには「信頼性」と「妥当性」の観点からの議論が有用。

• 【ハイ・ステークスな試験】：受験者にとって結果が人生を左右するような試験。逆はロウ・ステークス
• 【信頼性】：常に受験者の能力の大小を言い当ててている。
• 【妥当性】：試験で問われている内容と、実際に測定されるべき能力とがマッチしている。
• 信頼性の確保
  • 試験問題に対する正解・不正解が能力の大小によってばらつくかどうかの程度をテストの信頼性という。
  • 同じ概念に対して複数の問題を出題し、正誤データに高い正の相関が見られた時 → 信頼性が高い。 （問題を複数出すことで、問題によるばらつきを抑えていく）
  • 信頼性の指標としては、試験問題の冊子全体に一つの値が与えられる。
    • 問題冊子全体の信頼性は、個々の問題文の信頼性の積み重ね。
• 妥当性の確保
  • 構成概念妥当性がその試験にどの程度あるかが重要。
  • ある集団の測定結果を基にした尺度が、他の集団に対しても適用できるか？などなど
  • 数値的に表すことが難しい。
  • 統一的な見解がなされていない。

『教育の効果 メタ分析による学力に影響を与える要因の効果の可視化』まとめ

とっくのとうに読み終わっていたのですが、記事は途中なので随時更新します。まだ自分用のメモ程度です。

教育の効果: メタ分析による学力に影響を与える要因の効果の可視化

学習者要因の影響

生涯にわたって15000時間を子供は学校で過ごすが、これは起きている時間の約3割が教師に委ねられているという計算になる。しかしながら、ここでは学校に入学する前にすでに子供に培われた要因について論じている。

過去の学力

過去の学力は大きな影響を持ち、2/3の学力の伸びを説明するという内容は恐ろしい内容だが、残りの1/3はそのあとに変わると考えると、意外と悲観することでもないかもしれない。

• 過去の学業成績は学習の習熟を最も予測する変数である。
• 過去の学力はその後の学力の伸びを68%説明する。逆に32％は過去の学力からは説明できない。しかしながら、就学前教育や遺伝的要因は入学後の学力をかなり左右する。
• 22ヶ月時点での能力が26歳時点の学力を十分に予測していたことが明らかとなった。

態度と気質

言われれば確かにその通りという内容が多いが、データとしてきちんと客観的に示されていることは大きい。動機付けをどのようにして促進していくかは教師にとって大事な能力であると感じた。

• 不安、独りよがりの傾向、外交性などと学力の関係はほぼ見られない。
• 自己効力、自己概念、動機付け、学業達成への粘り強さなどは学力と高い相関が見られる。
• ビッグファイブ（神経症傾向、外交性、開放性、調和性、勤勉性）のうち、勤勉性以外は学力に与える効果は小さかった。
• 普段から幸福感を覚え楽しい気分でいる人は創造的で効率よく問題解決を行う傾向が見られる。
• 自己効力感（できる、したいといった信念）が、自己に対する認識の面では学力と一番関係が強い。しかしながら、自己効力感と学力はお互いに影響を及ぼし合っているので、単純な因果関係ではない。
• 学習者が有能さを感じている時、自律性を十分に感じている時、やりがいある目標を設定した時、適切な評価を得た時、そして他者から認められた時に、動機付けは最も高くなる。
• 学習は自己責任において行うものであると考えている度合いと学力のとの間には相関が見られる。
• 明確な学習目的と、わかりやすい到達基準があり、学習者にとって学習が見通しのあるものにすることが、学習者が学習に対して積極滝に取り組めるようにするためには必要不可欠。

就学前教育

新しいことに挑戦するという姿勢自体が、早い時期から育まれるべきものであるということは大事。

• 早期教育の全体的な効果は教師の効果を上回る。しかしこの効果は学校に上がって学年が進みにつれて減少する。
• 保護者が関与することで早期教育の効果が高まるということについてエビデンスはない。

家庭要因の影響

子供に伝わる保護者の後押しや期待は大きな影響を持つということについて語られている。

社会的な地位

• 学習者の学力に対して顕著な影響がある。
• 地位によって就学時点で語彙力が倍近く違った。
• 学習者の方が家庭の経済的・文化的背景に伴う違いによる不公平感を低く見積もる。
• 学校側から教育用語や学校とはどのような場であるかを親に知ってもらう取り組みが効果を上げている。
• 保護者自身の学習に対する働きかけも効果があった。

生活保護

• 目に見えるほどの差ではないが、優位に低い値が出ている。

家族構成

一番影響が大きいのは、子供に対して保護者が願望と期待をかけること。家庭条件よりもはるかに大きな影響をもたらす。

• 養子に入る年齢が遅ければ遅いほど、学力が下がる。
• 一人っ子である子供は、兄弟のいる子供と比べて学力と知能が高い。しかし効果は小さい。
• 母親としての子供との養育的な関わり、日課の多様性、適切な遊具の用意が学力をあげた。（しかし、父親に関しては言及されていない。）
• テレビ視聴の適正時間は年齢が上がるに連れて短くなる。視聴時間が週に35-40時間を超えると負の効果量が大きかった。
• テレビ視聴が社会的に良い行動に与える効果は、反社会的行動に対する効果を上回る。
• 保護者による勉強の監視は、思春期の学習者の希望や意欲に対して負の影響を与える。
• 保護者が期待をかけることは影響が大きい。
• 保護者は子供に読み聞かせをすることよりも、はるかに、読み方のコツを教えることが効果的である（10倍近くも...！）

学校要因の影響

マルチレベリング手法によって分析が行われてきた←要勉強。 児童生徒の学力の分散は学校間要因よりも、学校内要因によって説明される部分が大きいことを明らかにした。

学校構成の効果

• 高校の学校規模が学力に与える効果は大きい。
• 学校に在籍する児童生徒が経済的に恵まれているほど適正となる集団規模は大きくなる。
• 学校外で行われる学習プログラムによってもたらされる学力の伸びは小さい。

学級構成の効果

• 学級規模が学力に与える効果は一貫して小さい。
• 学級規模が小さく変わっているのにも関わらず、それに合わせて授業の方法を大きく変えていないことが原因の一つとして考えられる。
• 能力別学習集団編制の効果は極めて小さく、また低学力集団の生徒に関してはより学習を遠ざけている。なぜなら、低学力の生徒に対して教師は何も期待しないからだ。
• 複数の学年の児童生徒が同一の教室で同一の授業を受けるシステムでも、効果は低かった（つまり、負の効果も与えなかった）。
• 小集団に対して課題を与え、自力で解決させる場合は、大学生に対する効果量が大きかった。

学級の風土

• 児童生徒に対して教師が敏感になること、適切な心構えを持つこと（これはなんだろう...）、規律的介入をすること、などなど...規則や行動規範を示すことも大事である。
• 一心に目標に向かおうとする態度、前向きな人間関係、社会的な支援が学習をより良いものにする。集団のまとまりは学力に大きな影響を及ぼす。

AtCoder: ABC164-D Multiple of 2019 (400)

問題はこちら

atcoder.jp

1から9までの数字からのみなる、文字列 が与えられる。
次の条件を満たす整数の組 の総数を求めよ。

条件: の 文字目から 文字目までを10進法の整数としてみると、この整数は2019の倍数である。
制約:

考え方

はじめに

を二重ループで全ての通り試して、その数が2019で割り切れるかを試す方法が真っ先に思い浮かぶが、計算量が となり今回は間に合わない。

桁を増やしながら何か数えることができれば、計算量が減りそうだと考える。そこで、桁を一つ増やすごとにどのように状態が変わるかに注目してみる。

簡便化のために、 の長さを 、 の右から 番目の数を とし、を次のように表す。

着目点

今回、「2019という数は10と互いに素な数になっている。なので、 が2019の倍数の時、 も2019の倍数になっている」ことがポイント。

例えば4038000(=2019*2*1000) を考えると、これが2019の倍数の時、4038が2019の倍数になっているということ。当たり前のように感じるが次のように役立つ。

• 4038333のような数が出てきた時、4038333 - 333 = 4038000 が2019の倍数だったならば、4038は2019の倍数となり、題意をみたす。
• 右からどこまでを0にするか？に注目しそうである（右からどこまでを引き算して0にしまうか？）
• 4038333 - 333 % 2019 == 0
• 4038333 % 2019 == 333 % 2019
• 余りの等しい連続する部分列のペアを取ってくれば良い！

言い換え

このことから、次のように言い換えることができる。

1. が2019の倍数である。
2. が2019の倍数である。（これを とおく。）
3. が2019の倍数である。（→累積和と似たような考え方になる。）
4. 
5. 

同じ余りとなる のペアを探せば、題意を満たす整数の組になるということがわかる。

これは右の桁から順に数字を見ていき、2019で割った余りを とすると、map[m]++するなどして管理し、最後に各余りについて、二つ取る組み合わせを計算して足し上げれば良い。注意として、余りが0の数の場合、他の数とペアにしなくてもその数だけで題意を満たすため、map[0]=1 と初期化しておくことで他の場合と同じように計算ができる。

計算量は、となり、間に合う。（unordered_mapを使うとlogが取れる。）

この一連の求め方は、A - Zero-Sum Ranges でも同じような流れを踏むので見ておくと良いかもしれない。また、E - Divisible Substringでも似たような問題だったらしいがまだ解いていない。

解答

文字列だと右側から見ていく必要があるために、最初に文字列をreverseしてindexを扱いやすくしている。

また、桁数が非常に大きいため、桁数については別途modを取るようにしている。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define each(i, mp) for(auto& i:mp)

int main() {
    string s;
    cin >> s;
    map<ll, ll> mp;
    mp[0] = 1;
    reverse(s.begin(), s.end());
    ll now = 0, ten = 1;
    each(e, s) {
        now = (now + (e - '0') * ten) % 2019;
        ten *= 10;
        ten %= 2019;
        mp[now]++;
    }
    ll ans = 0;
    each(e, mp) {
        ans += e.second * (e.second - 1) / 2;
    }
    cout << ans << '\n';
    return 0;
}

Submission #12407239 - AtCoder Beginner Contest 164

AtCoder: ABC161-D Lunlun Number (400)

問題はこちら

atcoder.jp

以下の条件を満たす正の整数のうち、小さい方から 番目のものを求めよ。

• を10進数で表した時、隣り合うどの二つの桁の値についても、差の絶対値が1以下。

考え方

基本的に解説放送を聞いて自分の言葉に直しただけ。

www.youtube.com

まずは桁ごとに考えてみる。すると、今までに列挙した数の後ろに、条件を満たすような数を付け加えていけば良いということに気づく。

1 -> 10, 11, 12
10 -> 100, 101
11 -> 110, 111, 112
12 -> 121, 122, 123

今まで条件を満たしていた数 の一の位 は 。
よって、次に条件を満たす数は を10倍した数に、次に条件を満たす をつけたものになる。

これを全列挙しても 個程度までに答えが得られるので、間に合う。

解答

個全列挙するため、桁ごとに列挙したものの数を減らしていき、 が列挙してある数よりも小さくなった時、値を出力する。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ll k;
    cin >> k;
    vector<ll> a;
    for (ll i = 1; i <= 9; ++i) a.emplace_back(i);

    while (k > a.size()) {
        k -= a.size();
        vector<ll> old = a;
        a = vector<ll>();
        for (ll x: old) {
            for (ll i = -1; i <= 1; ++i) {
                ll d = x % 10 + i;
                if (d < 0 || 9 < d) continue;
                ll nx = x * 10 + d;
                a.emplace_back(nx);
            }
        }
    }
    cout << a[k - 1] << '\n';
    return 0;
}

Submission #11557806 - AtCoder Beginner Contest 161

AtCoder: ABC147-E Balanced Path (500)

問題はこちら

atcoder.jp

マス に二つの数 が書かれている．一回の移動で または に移動する．マス から に移動しながら，数の片方を選び に．もう片方を に追加する．移動する経路を とする時，以下の値を偏りと呼ぶ．

• 

数を自由に選びながら移動した時の，偏りの最小値を求めよ．

制約は以下の通り．

• 
• 

考え方

まずは式変形から．

つまり，経路を辿りながら値の差を足し合わせ，最後に絶対値をとる事と等しい．全ての経路を全列挙するのは 程度かかるので間に合わない．今回の場合は，制約が非常に小さいことに注意する．具体的には，答えとなりうる偏りは最大でも .

そこで，今のマス目でありうる符号付偏りの値を，毎回更新することを考え，最後に絶対値をとることにする．具体的には，以下のようなbool配列でdpをする．

• dp[i][j][l] := マス目 で符号付偏り となるかどうか

（ が負の時はどうするのか？という話があるが，それは解答のところで説明することにする．一旦無視する．）

マス目 での符号付偏りが とする ．マス目 から に移動した時，そのマス目までで取りうる値は次のようになる．

• 
• 

よって，更新式は次の通り． を取りうる場合は，新しい値も更新するようにする．

if dp[i][j][l] == true then
 dp[i+1][j][l + B[i+1][j] - A[i+1][j]] = true;
 dp[i+1][j][l - B[i+1][j] + A[i+1][j]] = true;

マス目 に移動するときも同様に考えれば良い．

解答

実装上の注意として，経路の途中で負となりうる場合はどうするかというのがある．editorialだと毎回絶対値をとっていたが，自分の実装では配列を「最大の偏り * 2」だけのサイズを取り，全ての値に「最大の偏り」分を足すことで負のindexにアクセスしないようにした．

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

int main() {
    ll h, w;
    cin >> h >> w;
    int a[h][w], b[h][w];
    rep(i, h) rep(j, w) cin >> a[i][j];
    rep(i, h) rep(j, w) cin >> b[i][j];

    ll max_diff = 2 * 80 * 160;
    bool dp[h][w][max_diff];
    rep(i, h) rep(j, w) rep(l, max_diff) dp[i][j][l] = false;

    ll mid = max_diff / 2;
    dp[0][0][b[0][0] - a[0][0] + mid] = true;
    dp[0][0][-b[0][0] + a[0][0] + mid] = true;

    rep(i, h) {
        rep(j, w) {
            rep(l, max_diff) {
                if (!dp[i][j][l]) continue;
                if (i + 1 <= h - 1) {
                    dp[i + 1][j][l + b[i + 1][j] - a[i + 1][j]] = true;
                    dp[i + 1][j][l - b[i + 1][j] + a[i + 1][j]] = true;
                }
                if (j + 1 <= w - 1) {
                    dp[i][j + 1][l + b[i][j + 1] - a[i][j + 1]] = true;
                    dp[i][j + 1][l - b[i][j + 1] + a[i][j + 1]] = true;
                }
            }
        }
    }
    ll ans = 1e18;
    rep(i, max_diff) {
        if (dp[h - 1][w - 1][i]) ans = min(ans, abs(i - mid));
    }
    cout << ans << '\n';
}

Submission #8980170 - AtCoder Beginner Contest 147

参考

とてもわかりやすかった．

[AtCoder 参加感想] 2019/12/08:ABC 147 | maspyのHP

AtCoder: ABC146-E Rem of Sum is Num (500)

問題はこちら

atcoder.jp

長さ の整数列 と正の整数 が与えられる。 の空でない連続する部分列であって、要素の和を で割った余りが要素の数と等しくなるものの数を求めよ。

以下は0-indexで話を進める。

考え方

要素の和の余りに関する問題なので、とりあえず累積和を mod K で取り、式に起こしてみる。mod K における、index i までの累積和を とすると、以下のようになる。

• 区間 ] の和:
• 区間 ] の要素の数:

とすると、以下のように問題を言い換えることができる。
「mod K において、 となる に対し、 となるものの個数を求めよ。」

しかし、 を全探索すると計算量が になり間に合わない。そこで、片方の端点 を固定して、その条件を満たす の個数を数えることを考える。

ここでポイントは、 以下の二つ。

• 要素の数が 以上の時は、要素の和が必ず 以上になり、題意を満たすことはない。つまり、 である。
• の時、mod K において以下の式変形が成り立つ。

なので、今までに見た index における の値の個数をmapなどで管理すれば、map[d[r] - r] で条件を満たす の個数を数えられる。

の時には、要素の数が 以上になるので、queueに の値を入れておき、queueのサイズが 以上になったら、map[queue.front()]--; queue.pop()して要素を取り除いてあげる。

解答

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

int main() {
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n), d(n + 1);
    
    rep(i, n) cin >> a[i];
    rep(i, n) {
        d[i + 1] = d[i] + a[i];
        d[i + 1] %= k;
    }
    map<ll, ll> mp;
    ll ans = 0;
    queue<ll> que;

    rep(r, n + 1) {
        ll t = (d[r] - r) % k;
        if (t < 0) t += k;
        
        ans += mp[t];
        mp[t]++;
        
        que.push(t);
        if (que.size() >= k) {
            mp[que.front()]--;
            que.pop();
        }
    }
    cout << ans << '\n';
    return 0;
}

Submission #8703311 - AtCoder Beginner Contest 146

参考

とても分かり易かったです。

Rem of Sum is Num [AtCoder Beginner Contest 146 E] - はまやんはまやんはまやん