AtCoder: ABC176-D Wizard in Maze (400)

問題はこちら

atcoder.jp

縦マス、横マスからなる迷路がある。マス(i, j) は # のとき壁であり、. のとき道である。ます目 (C_h, C_w) から(D_h, D_w) に移動することを考える。

以下の二つの移動方法がある。

• 移動A: 現在いるマスと上下左右に隣接する道のマスへ移動する。
• 移動B: 現在いるマスを中心とする 5*5 の範囲内にあるマスへワープできる。

移動Bを最低で何回使う必要があるか答えよ。 (D_h, D_w) にたどり着けない場合は -1 を出力せよ。

考え方

1. まず、「なるべく移動Bを使わないで移動できるならそうした方が良い」というのがわかる。よって、まずは移動Aによって幅優先探索を行う。

2. そして、移動Aで訪れることのできるマスがなくなったとき、移動Bを使って移動することを考える。移動Bに関しては、今まで移動Aで訪れてきたマスを全て調査すれば良い。

3. 移動Bで訪れることのできるマスを探索し終えたとき、訪れることのできるマスに対してを移動Aを行う（つまり1に戻る）

以上を繰り返すことで移動Bを使う回数を求めることができる。

1, 2を行うので全てのマス目に対して二回探索をする可能性が生じるが、それでも計算量は高々 なので間に合う。

解答

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll ll_inf = ll(1e9) * ll(1e9);
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)

int main() {
    ll h, w;
    cin >> h >> w;
    ll startX, startY, endX, endY;
    cin >> startX >> startY >> endX >> endY;
    startX--, startY--, endX--, endY--;

    vector<vector<char>> s(h, vector<char>(w));
    rep(i, h) rep(j, w) cin >> s[i][j];

    vector<vector<ll>> cnts(h, vector<ll>(w, ll_inf));  // 魔法使った回数
    queue<P> q, visited;
    // q: 移動Aでの幅優先探索用
    // visited: 移動Bでの幅優先探索用
    q.push(P(startX, startY));
    cnts[startX][startY] = 0;

    while (!q.empty() || !visited.empty()) {
        ll nowX, nowY;
        if (!q.empty()) {
            nowX = q.front().first, nowY = q.front().second;
            visited.push(P(nowX, nowY));
            q.pop();
            rep(i, 4) {
                ll nextX = nowX + dx[i], nextY = nowY + dy[i];
                if (0 <= nextX && nextX <= h - 1 && 0 <= nextY && nextY <= w - 1) {
                    if (s[nextX][nextY] == '#') continue;
                    if (cnts[nowX][nowY] < cnts[nextX][nextY]) {
                        cnts[nextX][nextY] = cnts[nowX][nowY];
                        q.push(P(nextX, nextY));
                    }
                }
            }

        } else {  // 今まで通った道から魔法で行ける道を全て調べる
            nowX = visited.front().first, nowY = visited.front().second;
            visited.pop();
            for (ll ix = -2; ix <= 2; ++ix) {
                for (ll jy = -2; jy <= 2; ++jy) {
                    ll nextX = nowX + ix, nextY = nowY + jy;
                    if (0 <= nextX && nextX <= h - 1 && 0 <= nextY && nextY <= w - 1) {
                        if (s[nextX][nextY] == '#') continue;
                        if (cnts[nowX][nowY] + 1 < cnts[nextX][nextY]) {
                            cnts[nextX][nextY] = cnts[nowX][nowY] + 1;
                            q.push(P(nextX, nextY)); // 移動Bのあとは移動Aをしたいのでそちらの候補に入れる
                        }
                    }
                }
            }
        }
    }
    if (cnts[endX][endY] == ll_inf) {
        cout << -1 << '\n';
    } else {
        cout << cnts[endX][endY] << '\n';
    }
    return 0;
}

Submission #16164015 - AtCoder Beginner Contest 176

LeetCode: Number of Good Leaf Nodes Pairs (Midium)

問題はこちら

leetcode.com

二分木とそのルートのノードが与えられる。二つの葉のノードは、その最短距離が distance 以下だったときに「良いペア」となる。この「良いペア」となる葉の数を求めなさい。

考え方

dfsする。今見ているノードに対して左側と右側の子ノードを探索し、その左右の葉に対する距離を足して、distance 以下だったときに求めるものをインクリメントする。

dfsの関数が返すのは、「左側に存在する全ての葉への距離 + 1」と、「右側に存在する全ての葉への距離 + 1」。これは、親から自分への距離を足して返している。（親のノードに関数が帰った時を考えると理解しやすい。）

解答

class Solution {
public:
    int countPairs(TreeNode *root, int distance) {
        int ans = 0;
        
        auto rec = [&](auto &&f, TreeNode *node) -> vector<int> {
            // そもそもノードが存在しない
            if (node == nullptr) return {0};
            // 葉
            if (node->left == nullptr && node->right == nullptr) return {1};
            vector<int> l = f(f, node->left);
            vector<int> r = f(f, node->right);
            for (const auto &a : l) {
                for (const auto &b : r) {
                    // 右側と左側の距離を足して、条件を満たすか
                    if (a && b && a + b <= distance) ans++;
                }
            }
            vector<int> ret;

            // 親ノードへの伝播
            for (const auto &a : l) {
                if (a && a + 1 < distance) ret.emplace_back(a + 1);
            }
            for (const auto &b : r) {
                if (b && b + 1 < distance) ret.emplace_back(b + 1);
            }
            return ret;
        };

        rec(rec, root);
        return ans;
    }
};

3ヶ月でやった事を振り返る - 入社1年目4~6月

はじめに

入社してから試用期間の3ヶ月が過ぎて、無事に採用されたので、この3ヶ月でやったことを振り返って書いてみました（一応上司確認済み）。
ベンチャーにサーバーサイドエンジニアとして入社した自分が、まとまりなく社内・社外でやったことを書き連ねるだけの記事です。

研修

ベンチャーながら、新卒入社の自分に対して教育リソースをかけてもらっていることがとても嬉しかったです。

研修では、大きく分けてビジネス研修とエンジニア研修をやりました。それぞれ1ヶ月で終了しました。

ビジネス研修

ビジネス研修では「コンサル一年目が学ぶこと」という本を輪読して行う形式で行いました。この本はコンサルに対して書かれた題名ですが、実際は社会人全てに共通するような大事な事柄が詰まっていて、最初に読むことができて良かったと感じました。

コンサル一年目が学ぶこと

また、輪読の形式として、以下の形式を取りました。記憶は感情が動くと定着しやすいため、「話し合う」というプロセスは記憶の定着に対して非常に良いアプローチだという感想を持ちました。

• 各々が担当部分を読んできて簡単にスライドにまとめる
• 週1で開かれる研修中はスライドの内容に対して自分たちの考え方を交えて話し合う
• 先輩が実際の事例を話してくれる

エンジニア研修

エンジニア研修では、新しく以下のような内容をやりました。実は、自分はWebアプリケーションを作ったことがないので、初めてのWebプログラミングになりましたが、1ヶ月弱で広く浅く学べて勉強になりました。

メンターさんについてもらって、毎日1on1をしながら進めてもらいました。技術的な疑問点が解消できたり、何より会社内に話せる人が身近にいる安心感を感じることができました。

• Scalaの基本文法
• Scalaを用いたWebアプリケーション作成の基礎
  • 簡単にAtCoderのレート遷移を返すAPIを実装
  • MySQL, Redisなどの基本知識とアプリケーションへの実装
  • Docker-composeを書いて立ち上げる
  • Github Actionを使ってmasterにプルリクが出るたびにテストを回す
• Reactのチュートリアル
• アサインされる予定のプロジェクト周りの知識input
  • GraphDBでクエリを書く方法
  • プロジェクトのlocal開発環境の構築

お仕事

5月からは実際のプロジェクトにアサインされてお仕事をしていました。途中でインターン時代に作っていたものの不具合修正などが入ってきてドタバタする時もありましたが、基本的には腰を据えて一つのプロジェクトに対して集中していました。優秀な方々と一緒にお仕事ができていて日々勉強になり楽しいです。

新機能の機能・設計・実装を任されていたので、まずはそこの機能実装のために教育に関するリサーチをしたり、論文を読んだりしました。そのあとで自分なりのアルゴリズムを考えてプロトタイプ作成して関係者の合意をとり（ここは可視化とかもあってPythonでやりました）、ようやくScalaでの実装を始めました。

実装はTDDでテストベースでレビューをしてもらいながら進めています。TDDは心理的な不安が少なく開発できるのでとても良いなと思っています。

他にも、自由参加のプロジェクトが複数あり、それに参加したりしています。エンジニアにとどまらず、全社的な改善プロジェクトに今から関われるのはとても楽しいです。

お勉強

業務に関係しそうなことをたくさん勉強していました。

「Scalaスケーラブルプログラミング」：380ページくらい読みました（これでもまだ半分で道のりが長い...）。Scalaの基本文法に対して、言語設計や設計思想にも言及しながら説明がされており、個人的には読み物として気に入っています。

Scalaスケーラブルプログラミング第3版

テストは何を測るのかー項目反応理論の考え方：項目反応理論に関係するところまで読みました。そもそもテストの平等性や公平性ってどうやって担保するか？というのは難しい問題です。TOEICなどは同じ点数だったとしても問題の難易度が違えば、スコアが意味をなさなくなってしまいます。これを統計学的アプローチで解決できるのが項目反応理論（IRT）で、統計×教育という分野で興味深く読みました。

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

ゼロからできるMCMC：MCMCはパラメータ推定などでよく使われるアルゴリズムです。個人的にはどこかで使えると良いなと思って、最近出版された本を読んでみました。アルゴリズムを使うだけではなく、中身の原理や実際に使う時の注意点などを知ることができました。

ゼロからできるMCMC マルコフ連鎖モンテカルロ法の実践的入門 (KS理工学専門書)

進化する勉強法：ファクトに基づいた勉強法を紹介している本です。論文で効果があると実証されている教育法や勉強表について、図やグラフも用いてわかりやすく説明されており、広く浅く知るのに良い本だと感じました。

進化する勉強法: 漢字学習から算数、英語、プログラミングまで

原因と結果の経済学：相関と因果は違うんだよーということを様々な事例を用いて説明していました。簡単目ではあったけど、実験における「内的妥当性（同じ集団に対して再現性がある）」と「外的妥当性（異なる集団に対して再現性がある）」という言葉の定義などは初めて知ることができました。

「原因と結果」の経済学―――データから真実を見抜く思考法

趣味

競技プログラミング

AtCoderで競技プログラミングをして、なんとレートを1年以上前まで戻してしまいました（パソコンが落ちまくってて難し目の問題だけ解けたと思って提出したら死んだので1問も正解していないw）。

ただいま〜！😭😭

hiramekunさんのNOMURA プログラミングコンテスト 2020での成績：6025位
パフォーマンス：10相当
レーティング：1262→1158 (-104) :(#AtCoder https://t.co/gGOIfEU3wH pic.twitter.com/vWaJYycTBb

— ひらめくん🐟 (@hiramekun1995) May 30, 2020

ここまでくると逆に気楽にコンテストに参加して、ゆるゆると水色に戻れればいいなと思いながらエンジョイ勢をやっています。社会人になってからの方が精進できているのはちょっと面白いですね。引き続き楽しんでやってます。

🤔🤔 pic.twitter.com/6EdiFKwysF

— ひらめくん🐟 (@hiramekun1995) June 27, 2020

あとは、友人に勧誘されてLeetCode始めました。こちらの方が個人的には出てくる問題が好きかもしれません。こちらもゆるゆると参加していきたいと思います。

スマブラ

スマブラSPをやっていて、今はクマメイトでいう、「VIP安定層（中）」です。 ここからVIP上位に行くにはもっと操作精度を上げたりトレーニングモードでの練習をする必要があると感じていますが、なかなかトレモに時間を割こうとは思えず...

とにかくキャラクターが多いので、今は配信者の動画を見たり、使用キャラのグループに入ったりして楽しみながら強くなりたいなと思っています。

スマブラ世界戦闘力のVIPボーダー、変動数、段位 - クマメイト

『理論と事例でわかる自己肯定感』を読んだ

本はこちら

booth.pm

自己肯定感には大きく分けて二つある

1. 「とても良い」という気持ち
2. 「これで良い」という気持ち

この二つが両方十分な状態にあるのが良い心理状態。両方とも足りていないときには、まずは早く上がりやすい「とても良い」という気持ちをあげることに専念すると良い。

「とても良い」という気持ち

「とても良い」という感情は他の人と比べて自分が何が優っているのかなどであり、主に結果から生まれる感情。成功体験がこれを主に向上させる。

ただ、結果が同じでも人によって受け取り方が異なる。その結果がその人に対してどれくらい重要なのか？によって成功体験か否かは変わってくるということ。なので、「とても良い」気持ち = 結果 * 重要度 ということになる。願望を小さくしたり、重要ではないとこにフォーカスしないといった手法をとることで改善が可能になる。

「これで良い」という気持ち

「これで良い」という感情は自分が認められている、ありのままの自分で良いという感情で、主にプロセスから生まれる感情。他人との共有体験（空間的、時間、知識、感情など...）がこれを向上させる。「とても良い」という感情を上げようとするあまり背伸びをしてしまうと、こちらの気持ちが阻害されてしまう。

感想

自己肯定感に2種類あり、それを分けて考えるのは、フレームワークとして身につけておきたいなと感じた。また、結果が同じであっても、自身の期待値調整によって自己肯定感をうまくコントロールできる気がしたので、やってみたい。

『How Google Works』まとめ

本はこちら。Googleの人事周りの思想についてまとまっている。

How Google Works (日本経済新聞出版)

文化と戦略

企業を立ち上げる時には企業文化を明確にするべき

• 一度できた企業文化を変更することは難しい。
• 大切なものは何か、信念は何か、どんな存在になりたいのか。を尋ねる。
• 会社のミッションは本音を書こう。
• できたビジョンは繰り返し伝える。

オフィスは狭い方がいい

• オフィスの広さを重視する文化はやめる。
• 狭い場所での交流によってクリエイティブになる。
• 一人になれる時間もしくは場所の提供は重要。
• 社員同士の交流を増やすことによってアイディアが生まれる。

能力主義について

• 一番偉い人の役割は、自分のアイディアが最も優れたものでないとわかった時には邪魔をしないように身を引くこと。
• 異議を唱える文化。異議を唱えることを義務にすることで、言いやすい雰囲気づくり。
• マネージャーは最低7人の部下を持つべし。

チームについて

• 小さなチームにするべき。
• 一番影響力の大きい人を中心にして組織を作る。
• 一番優秀な人材により多くの責任を与える。
• 悪党はすぐに退治せよ。
• 悪党は誠実さの欠如から生まれるが、ディーバは個人とチームどちらも成功させたいと思っている。これを簡単に排除してはいけない。ここの見極めが重要。

働きすぎについて

• 燃え尽き症候群の原因は働きすぎではなく、自分にとって本当に大切なことを諦めなければならなくなった時に起こる。
• 責任と自由を与え、決定権を持たせる。自分にとって好ましい働き方を考えてもらう。
• しっかり休暇を取るべき。休暇を取る人間が必要不可欠な人間であったなどということはありえなくするべき。代わりの人を用意する。

イエスの文化

• ダメは会社が活気を牛なた証。
• なるべく頻繁にイエスと言うような文化を作る。

仕事は楽しくあるべき

• 同僚と一緒に笑ったり、仕事をすることの楽しさが重要。
• 楽しさはあらゆるところから生まれてくる。
• 許されることの境界を広げておくことで、楽しさが生まれる余地が上がる。

リーダーはついてこい！の姿勢

• 平等精神を身を以て示す。情熱が欠かせない。会社を大切だと思うべき。

事業計画は間違っていて当然

• その計画をどうやって修正するかが重要。
• また、やっているうちにわかるだろうという考え方を好む。
• 事業計画の基礎を明文化すること。
• 顧客の要望に応えるより、顧客が思いつかないような、あるいは解決できないと思っていた問題へのソリューションを提供するのだ！

組み合わせ型イノベーション

• 現在ある技術を組み合わせてイノベーションを起こす。
• 面白いものを見つける
• 小さな問題の解決策に注目し、その適用範囲を広げる方法を考える。
• 技術的なアイディアを元にプロダクト戦略を立てる。

採用は一番大切な仕事

組織より人

• その人に見合うポストがあるかないかに関わらず、優秀な人材を採用する。
• 人材は会社の最も重要な資産だが、メンバーを採用する仕組みを見直す必要がある。

群れ効果

• 最高の人材と一緒に働きたい人が集まってくるのでその人を採用すれば良い。
• 採用の基準を思い切り高くし、世間にアピールする。

情熱について

• 情熱があることが優秀な人の特徴。
• 自分が興味あることについて永遠に語ることができる傾向。
• 情熱を追求するスタイルを真剣に聞くべき。

ラーニングアニマルを採用する

• 頭脳ゲームで対戦したくない相手、自分より優秀な人間を採用するべし。
• 「何を知っているか」よりも「これから何を学ぶか」が重要。
• 学習を続け、それを楽しむ人間。
• 過去に同じような仕事で実績を上げた人を選びがちだが、専門能力よりも知力を優先するべき。

面白い人間を採用する

• 一緒に話をしていて楽しいか。
• いい人である必要はない。または好きになれる人間とは限らない。面接するときには先入観を意識して客観的にみる。

発掘

• どのような候補者を探しているか、明確に定義する。
• 絞りを広くして、当たり前の候補者以外（将来性を見る）からも適任者を探す。
• 優れた採用文化を醸成する第一歩は、候補者を発掘する上で採用担当者が果たす役割を正しく理解すること。
• 候補者の発掘は採用担当者の独占的業務ではない。
• 全社員が一人ずつ優秀な人を連れてくればいい。

面接のスキルは最も重要

• きちんとした面接をするには自分の役割を理解し、候補者の履歴書を読み、何を聞くかを考えなければならない。
• 候補者が答えるのに苦労する質問を投げかける。
• バックグランドを聞くときは、そこから何を学んだかを説明してもらう。
• 自分も相手から見られていることを意識するべし。
• 相手が的を射た質問をするかどうかも見てみよう。
• 面接の時間は30分でいい。

採用の仕組みづくり

• リーダーシップ、職務に関する知識、全般的な認知能力、らしさ。
• 意見ではなくて、データに基づいて採用する。
• 一人ではなくて、委員会の承認などを経て採用する。

報酬について

• 最高のプレイヤーには十分な報酬を支払うべき。
• 最初は低いところから始めるべき。というよりも他の惹きつける要因を探した方が良い。

優秀は人間を引き止めるには

• 全力で引き止める。
• 特別任務を与えて、日常に刺激を与える。
• 新しい挑戦を求めているときは組織がそれに合わせる。

退社について

• 相手の話をよく聞く。
• 会社の代弁者に立つのではなくて、相手の立場に立つ。
• クビを言いつける必要のある人間は最初から採用しなければ良い。

意思決定

正しい意思決定とは

• 正しい選択をすることだけに集中してはいけない。判断に到達するプロセス、判断を実行に移す方法も重要。
• 結果がわかっていても、決定に至るまでが大事。

データに基づいで判断する

• 意見ではなく、データに基づく。データを参加者に見せる。
• まずはデータに基づいて事実をしっかりと抑えることが重要。

正しい判断とは最高の判断であり最低限の妥協案ではない。

• 出席者全員がイエスと言っても全員が合意したとは限らない。
• 最適解に到達するには、出席者が自分の意見や反対意見を述べなければならない。
• 特に静かな人、発言していない人を指名しよう。
• 間抜けな変化球を投げて、意見を言うのことに抵抗をなくす。

意思決定者はプロセスを管理する。

• 期限を設定し、プロセスを取り仕切る。
• 行動志向とは、ある行動をとるか正しいか確信が持てないなら、一番いいのは実践してみて 結果に応じて軌道修正すること。
• 意思決定の数は減らすべき。また関与する人数も減らすべき。

どちらも正しい

• 相手の行動を変えたいなら、説得力のある主張をするだけではなく、相手のハートに触れなければならない。
• どちらも正しいと言うことによって、自分の意見を受け入れてもらえたと感じてもらう。

悪い知らせをリーダーに伝えやすくする

• 情報伝達プロセスがきちんと機能している必要がある。
• 辛い真実をトップに報告しやすい環境を作る。
• 反省会を行う。誠実なコミュニケーションを行う。
• 直接経営陣に厳しい質問を匿名でできるようなシステムを作る。

会話は重要

• 新入社員にはリーダーの方から手を差し伸べる必要がある。
• 会話のきっかけづくりをどんどん行う。

コミュニケーーションは過剰であるべき

• リーダーは常にコミュニケーション過剰になるべき。
• コミュニケーションは重要なテーマを強調するものか。
• 面白いコミュニケーションか。
• 心を込める。
• 正しい相手に届いているか。
• 新しい職務についたら部下の人となりを知り、信頼を勝ち取る。周囲を笑顔に。

自分なら自分の元で働くか？

批判をされないのは質の高い対話をしなかった証拠。

LeetCode: Avoid Flood in The City (Midium)

問題はこちら

leetcode.com

湖が無限個存在している。その全ては今水は入っていない（=空）だが、 番目の湖に雨が降ると満杯になる。

満杯の状態の湖に雨が降ると、洪水が起きてしまう。

以下のような rains 配列が与えられるので、洪水を避けるようにしたい。

• rains[i] > 0: rains[i] 番目の湖に雨が降る。
• rains[i] == 0: 雨が降らず、好きな湖を一つ空にすることができる。

答えとしては、以下のようなans 配列を返す。

• ans.length == rains.length
• ans[i] == -1: rains[i] > 0 の時
• ans[i]: rains[i] == 0 の時、 日目に空にした湖の番号

考え方

空である湖 に雨が降った時は何も気にしなくて良い。しかし、次に湖 に再び雨が降った時、考えなければならない。よって、同じ湖 に雨が降った時に、それより前にある「空にする日」を用いて、その湖 を空にできなかったかを考える。そうすることで、空の湖に雨が降ることになるので洪水を避けることができる。

具体的には、次のような「空にする日」を選ぶのが良い。

• 前回湖に雨が降った日 prev_day よりも後。
  • 雨が降った日より後でないと、空にする意味がないため。
• かつ prev_day から一番近い日。
  • greedyに考える。 prev_day よりも遠いところにあるものほど、のちに使える可能性が高い。よって、なるべく使えるならば早めに使ってしまう方がよい。

実装方針

上記のような、「ある時点からもっとも近い時点を高速に求める」のは lower_boundを使えばできそうで、「空にする日」を set に入れることで探索を実現できる。

また、prev_day を求めるために、毎回雨が湖 に降った場合、その日付を記録しておく map を用意しておく。詳しくはコードを見た方が良いと思う。

解答

class Solution {
public:
    vector<int> avoidFlood(vector<int> &rains) {
        int n = rains.size();
        vector<int> v(n);

        // 「空にする日」を入れておく
        set<int> drydays;

        // full_lakes[i]: 今までで、湖iを水で満たした最後の日を持つ
        unordered_map<int, int> full_lakes;

        for (int i = 0; i < n; ++i) {
            if (rains[i] == 0) {
                drydays.insert(i);
                // 適当に入れる。後で書き換わる可能性あり
                v[i] = 1;
            } else {
                if (full_lakes.find(rains[i]) == full_lakes.end()) {
                    full_lakes[rains[i]] = i;
                } else {
                    if (drydays.empty()) return vector<int>();

                    // 前回に湖を満たした日を求める
                    int prev = full_lakes[rains[i]];

                    // prev以降でもっとも近いところに存在する、「空にする日」を探して、
                    // 空にする日はrains[i]を空にすることにする
                    auto itr = drydays.lower_bound(prev);
                    if (itr == drydays.end()) {
                        return vector<int>();
                    } else {
                        v[*itr] = rains[i];
                        drydays.erase(*itr);

                        // 湖を満たした日をアップデートする
                        full_lakes[rains[i]] = i;
                    }

                }
                v[i] = -1;
            }
        }

        return v;
    }
};

AtCoder: ABC149-D Prediction and Restriction (400)

問題はこちら

atcoder.jp

回じゃんけんを行う。買った場合、以下のように点が与えられる。

• グーで勝った時、 点
• チョキで勝った時、 点
• パーで勝った時、 点

ただし、ちょうど 回前に出した手と同じ手は出せない。

相手の出す手が事前に全て文字列 で与えられている時、最適に選ぶと最大何点得る事ができるか求めよ。

考え方

DPすればいいなという見方にはなる。普通にやると 回前に出した手を覚えておければいいのだが、DP遷移がうまく実装できない。

そこで、今回は一回ずつの試行は 回前の試行にのみ依存し、そのほかの回数とは独立であることに注目する。これを手がかりとすると、「 回前と同じ手は出せない」 → 「 で見たとき、前回と同じ手は出せない」となることに気づく。

こうなればあとは普通のDPと一緒で、 の世界でそれぞれに対して前回と同じ手を今回は選ばないように遷移して数え上げ、最後にその和を取れば答えになる。

解答

#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;
    ll r, s, p;
    cin >> r >> s >> p;
    string t;
    cin >> t;
    const ll RR = 0, SS = 1, PP = 2;

    ll ans = 0;
    for (ll i = 0; i < k; ++i) {
        vector<vector<ll>> dp(n / k + 10, vector<ll>(3));
        ll tmp = 0;
        for (ll j = i; j < n; j += k) {
            ll idx = j / k;
            rep(now, 3) {
                rep(prev, 3) {
                    if (idx > 0 && now == prev) continue;
                    dp[idx + 1][now] = max(dp[idx + 1][now], dp[idx][prev]);

                    if (t[j] == 'r' && now == PP) {
                        dp[idx + 1][now] = max(dp[idx + 1][now], dp[idx][prev] + p);
                    }
                    if (t[j] == 's' && now == RR) {
                        dp[idx + 1][now] = max(dp[idx + 1][now], dp[idx][prev] + r);
                    }
                    if (t[j] == 'p' && now == SS) {
                        dp[idx + 1][now] = max(dp[idx + 1][now], dp[idx][prev] + s);
                    }
                }
                tmp = max(tmp, dp[idx + 1][now]);
            }
        }
        ans += tmp;
    }
    cout << ans << '\n';
    return 0;
}

Submission #14117271 - AtCoder Beginner Contest 149

別解

greedy解もあるらしい。 回先で同じ手で勝てるなら、早いうちに手を出して勝ったほうが得になるので、

• 今勝てるなら勝てる手を出す。
• 勝てる手を出せない場合は、次の 回先の手で勝ちたい。なので、 回先の手を邪魔しない手を出す。