プルリクエストで意識していること

概要

相生葵の Advent Calendar 2020 10日目の記事です。

自分がプルリクエストで意識していることを書きます。

目次

  1. プルリクエストの目的
  2. コメントを書くとき意識していること
  3. コメントをもらうとき意識していること

1. プルリクエストの目的

  • 自分の技術向上のため

コメントする側でも、コメントされる側でもこの目的を意識しています。

2. コメントを書くとき意識していること

  1. 柔軟な姿勢
  2. 理由をつける
  3. 理由には記事のリンクもつける
  4. 具体的なコードも記載する

1. 柔軟な姿勢

絶対にこっちの方がいいと思ってコメントしていても、プロジェクトで決まっているコーディングルール以外は「直してください」という姿勢では書かないようにしています。

理由はもし今の方法にしていることに明確な理由があるにも関わらず、押しが強い姿勢でいってしまった場合、コメントを受けた側がコメントを書いた側の意見を圧によってうのみにしてしまう可能性があるからです。

もし、自分の書き方ではなく相手の書き方の方がよかったのにこうなってしまった場合、一つ技術向上の機会を逃すことになります。

2. 理由をつける

以下の2点を目的にしています。

  1. 根拠が自分の中にあることを確認すること、その理由が人に説明できるくらい自分の中で明確であること
  2. 相手に理解してもらいやすくすること

プルリクエストに根拠を書いてみて、あやふやだと感じたら、調べたり実際にコードを書いてみて明確にしていきます。

3. 理由には記事のリンクもつける

検証記事や公式の説明などがあればリンクをつけるようにしています。
これは、理由の補強です。

4. 具体的なコードも記載する

文章で書いていても、具体的にコメントを書いた側がどのように考えているのかが分からないことがあると思っています。
そのため、具体的なコードも必要そうであればつけるようにしています。

書き方が分からなければ、調べる必要があるので自分も書けるようになります。

3. コメントをもらうとき

  1. コメントには必ず何らかのアクションを返す
  2. 提案は受け入れるという姿勢でいる
  3. 提案されたものを受け入れるか判断に迷ったときは他のメンバーにも聞いてみる

1. コメントには必ず何らかのアクションを返す

コメントをスルーすると、次回から自分が書いたコードに違和感を感じてもコメントしてもらえない可能性があります。
そのため、必ずいただいたコメントにはアクションを返すようにしています。

2. 提案は受け入れるという姿勢でいる

自分の書き方が絶対という考え方は持たず、改善のため提案は受け入れるという姿勢でいます。

3. 提案されたものを受け入れるか判断に迷ったときは他のメンバーにも聞いてみる

自分の書いたコードにも理由があり、相手の提案にも理由がありどちらがいいのか迷うことがあります。

このときは、提案者以外のメンバーにもどちらの書き方がいいのかを聞いてみたりします。

機能をどう実現していくか考えるとき

概要

相生葵の Advent Calendar 2020 6日目の記事です。

機能をどう実現していくか考えるときどうしているかについて書きます。

手順

  1. 実現方法の書き出し
  2. 実現方法それぞれに対して、掘り下げる
  3. 不明点を潰す
  4. 実現方法を確定させる

1. 実現方法の書き出し

実現方法を思いつく限り書き出します。
この時点では、優先度はつけず、メリット・デメリットなども考えません。

2. 実現方法それぞれに対して、掘り下げる

「1」で書き出した実現方法に対して以下などを掘り下げていきます。

  • メリット
  • デメリット
  • 疑問点
  • 懸念点

3. 懸念点・疑問点を潰す

「2」で書き出した懸念点・疑問点を潰します。
コード内に答えがあることなら、コードを読んだり、人に聞いて確認できることなら人に聞いて確認したりします。
重要なことは、疑問点をもったまま先に進まないことです。
懸念点・疑問点を解消できるかどうかでどの解決策を選択するかの優先度が変わるためです。

4. 実現方法を確定させる

「2」で書き出したメリット・デメリット、懸念点を踏まえて最もよい解決策を選択します。
ここで一番重要なことは、自分の考えではなく、プロジェクトにとって最もよい選択肢を選ぶことです。

どのような方法がプロジェクト全体として、現実的で最もコスパよく達成・運用できるのかを考えます。

最後に

個人的に気をつけているのは、「3」と「4」です。
「3」については「疑問点・懸念点」があっても、確認せずに推測で無意識に進んでしまいそうになったりするので一旦考えたりして止めています。
「4」については、自分の中で完結する解決法を選びそうになるので、「プロジェクト」としてどうか？ということを意識して考えるようにしています。

分からないことがあるときどうしているか

概要

相生葵の Advent Calendar 2020 4日目の記事です。

分からないことがあるとき自分がどうしているかを書きます。

自分のスタイルについて

なるべく自分で解決しようというスタイルです。
分からないことをすぐ質問することに何かマイナス要素を見出しているわけではなく、自分で解決策を見つけられると楽しいからです。
質問をするにもある程度知識があると相手の言っていることをスッと理解できるので理解度が速い気はしています。

ただ、全ての問題に対してこのようなスタイルであるわけではなく、解決しなくても特に問題ない問題などは少し調べて分からなかったらまず人に聞いてみることもあります。

分からないことがあるときの行動

  1. 調べる、試す、考える
  2. 今の状態をまとめる
  3. 質問するために考えをまとめる
  4. 質問する
  5. 1に戻る

①調べる、試す、考える

分からないことがある場合、まず調べます。（ググりまくります）
解決の糸口になりそうな情報が見つかったときは試してみます。
試してだめであれば、調べたことと試したことを見返して次の手を考えます。

調べる→試す→考える
のサイクルを次の手が出てくる限り（調べるワードを変えてみる、問題を別の角度から見てみる、調べた情報の中にヒントとなるものがないかをもう一度考えてみるなど）は繰り返します。

②今の状態をまとめる

自分の中で手段が尽きたら、一度問題を整理します。
メモ帳などを開いて、文字を出しながら整理することが多いです。

何が今問題になっていて、なぜ問題になっているのか
試した手段、試した結果などを書き出しながら今の状況を整理します。

視覚的に見える形に整理すると、次の手が出てきたり、使えそうなもの、問題が別にあることなどに気づいたりします。
自分で解決できることなのか、人に聞かなければいけないことなのかなどを整理します。

③質問するために考えをまとめる

②で新しい手段が出てこなければ、質問をするための準備に入ります。
この時点で、自己解決は諦めて他の人の手を借りることを考えています。

以下を整理して書きます。

  • 何を解決したいのか（どんな問題が起こっているのか）
  • 調べたこと、試したこと
  • 問題解決につながりそうと考えている部分など

長くならないように、でも相手が欲しい情報は欠かさないようにということを意識して書いています。

④質問する

質問するには、以下の2手段が多くの場合あると思います。 1. チャットで聞く 2. 口頭で聞く

どちらでも問題なさそうな場合は、私はチャットで質問を投げておく場合が多いです。 理由は、以下です。

  • 相手の任意のタイミングでみられる
  • 相手のペースで考えられる

問題が複雑な場合や、③がまとまらなかった場合は口頭で質問しています。

質問をすると何らかのヒントや回答が得られるはずなので、また1にもどって繰り返します。

最後に

次の手段が自分の中にあるかを考えながら模索しています。
「試す」ときに勘で動くこともありますが、今の自分が試していることに意味があるのかをたまに考えて無駄な動きをあまりしないように気をつけたりしています。

伝える文を書く上で気をつけていること2（内容）

概要

相生葵の Advent Calendar 2020 2日目の記事です。

このページでは私が人に伝える文を書く上で意識していることを書きます。

文を書くときに考えていること

  1. 自分は何を伝えたいのか
  2. 相手の状況はどうか
  3. 最も伝わる方法は何か
  4. 曖昧な点をそのままにしていないか

①自分は何を伝えたいのか

1番初めに出てくることはこの項目です。
相手に対して自分が何を望んでいるのかを考えます。

例えば、以下のようなことが考えられます。

  • 質問がしたい
  • 確認をしてほしい
  • 報告を見ておいて欲しい

ここを明確にしておくと伝えたいことの軸ができるので、相手に伝わりやすくなると思っています。

②相手の状況を考える

相手に伝えるための文なので、この項目が何を書くかを考える上で一番大きいです。

相手のことを考えると、色々なことを考えて文を書くことになります。

  • なるべく相手に負担をかけないようにするにはどうしたらいいか
  • 相手は何を知っていて、何を知らないのか
  • どのような書き方が一番相手に伝わるのか

③最も伝わる方法はなにか

文以外にも伝えるための方法は複数あります。

  • 画像
  • 映像
  • 表


など
視覚的なものを文に添えるだけで分かりやすさが格段に上がります。

④曖昧な点をそのままにしていないか

分からないことを分からないままにして文を構成すると、はっきりとした書き方ができなくなります。
そのため、曖昧な点を見つけたら相手に文を送る前に解決しておきます。

最後に

自分が文を書くときは、以下のようになることが多いです。

  1. ①をまず考える
  2. ②を考えながら一度文を書く（同時にできなさそうなら、相手の状況を書き出して整理してから文を構成する）
  3. 文を見直してぼやかして書いている部分がないか確認する
    　→あれば、曖昧な部分なので解決しておく（④）
  4. 文を見直して、文以外の方法で伝えた方がいいものはないか確認する
    　→あれば、文を消して別の方法を添付する（③）

伝える文を書く上で気をつけていること1（形）

概要

相生葵の Advent Calendar 20201日目の記事です。

このページでは私が人に伝える文を書く上で意識していることを書きます。

伝える際の文の形

箇条書きで以下のように組み立てています。

  1. 導入
  2. 前提
  3. メイン
  4. 意図


例：夕飯を決めるために、相手が昼に何を食べたのかが知りたいとき
---------------------------------------------------------------

1点質問があります。　--①導入

■ 前提　--②前提
以下、お昼とは昼ごはんのことを指します。

■ 質問　--③メイン
今日のお昼は何を食べましたか？

■ 質問意図　 --④意図
夕飯が昼とかぶらないようにするために質問いたしました。

---------------------------------------------------------------

この形にする理由

各要素は「メイン」を正確に伝えるための部品です。
短い文は何を言っているのかが分かりやすいので、メインが短くなるように構成しています。

なぜ箇条書きか

一目で構造が分かるからです。
文章を読まなくても、どこに何が書いてあるのかが相手にすぐ伝わります。

各パーツについての説明

①導入

相手に何を伝えたいのかを一言でまとめます。
例えば質問をしたいときは、「質問が1点あります」と書きます。

導入の効果

  • この文が「質問」をするための文ということが明確に伝わる
  • この後に続く質問を受け入れる準備を頭の中でしてもらえる
  • 数を明確に提示することでいつまで続くのかという不安を消せる

②前提

これは、必要な場合とそうでない場合があります。
「メイン」を伝える上で、相手に前提の知識がない場合はこの項目を設けます。
「メイン」に入る前に知っておいて欲しいことを書きます。

前提の効果

  • 前提知識をメインと分けることにより、メインを短くすることができる

③メイン

短くまとめます。

文章が短いと、情報が正確に伝わりやすいです。

④意図

ここには「どうして伝えるのか」を書きます。

意図の効果

  • メインで伝えることをより正確にする（文脈の読み間違いですれ違いが起こることを防ぐ）

まとめ

言いたいことを端的にするために、項目を分けてまとめると言いたいことが的確に伝わりやすくなると思います。

D - Handstand

競プロ 累積和

はじめに

競技プログラミング、AtCoder Beginner Contest 124
D - Handstand
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

N 人の人が左右一列に並んでいます。
0, 1 からなる長さ N の文字列 S と正整数 K が与えられます。
左から i 番目の人は、S の i 文字目が 0 のとき直立し、1 のとき逆立ちしています。
あなたは K 回まで以下の指示を行います。一度も行わなくても構いません。

指示: 
1≤l≤r≤N を満たす整数 l,r を選ぶ。
左から l,l+1,...,r 番目の人の状態を反転する。
すなわち、i=l,l+1,...,r について、左から i 番目の人は直立していれば逆立ちし、逆立ちしていれば直立する。

K 回までの指示で、逆立ちした人を連続で最大何人並ばせることができるか求めてください。

制約

・N は 1≤N≤10^5 を満たす整数である。
・K は 1≤K≤10^5 を満たす整数である。
・文字列 S の長さは N である。
・文字列 S の各文字は 0 または 1 である。

入力

入力は以下の形式で標準入力から与えられる。

N K
S

出力

K 回までの指示で、逆立ちした人を連続で最大何人並ばせることができるか出力せよ。

解き方

以下を参考にしています。
https://img.atcoder.jp/abc124/editorial.pdf
競プロ参戦記 #41 Handstand | ABC124 - Qiita
AtCoder ABC 124 D - Handstand (400 点) - けんちょんの競プロ精進記録

解き方の流れ

以下では、累積和で解いています。

問題文より、
指示を出す際に
人の状態を反転する範囲を自由に決められることが分かるので
「逆立ちした人を連続で並ばせる数」を増やすには
直立している人の連なっている範囲を指定し、
直立の人を増やさずに
逆立ちしている人のみを増やしていくことを考えます。

また、
直立を逆立ちに変えるなら
一番近い直立の範囲を反転していきたいです。

出力例2を例とすると

入力例2
14 2
11101010110011

指示を出す際に
l=9,r=12で反転させると

11101010001111

となってしまい、
逆立ちの最大の連なりは4になりますが
l=11,r=12で反転させると

11101010111111

逆立ちの最大の連なりを6にすることができます。

また、
上の指示の後の
二回目の指示を
l=4,r=4とすることもできますが

11111010111111

というように
先程反転したものとは連ならない位置に
なってしまうため
逆立ちの連続する人数を最大化するには
指示の意味がなくなってしまいます。

そのため、
反転した位置と近い位置にあるものを
反転させて連続した逆立ちの数を増やしたいです。

二回目の指示を
l=8,r=8とすれば

11101011111111

逆立ちの連なりをさらに増やし、8にすることができます。

そのため、
直立、逆立ちがそれぞれ連なっている範囲を一つの塊とみなし、
その中の直立のどの範囲を逆立ちにするかの
累積和をとっていくことで答えを出すことができます。

以下の流れで行います。

① 直立、逆立ちそれぞれの連なっている部分を一つの塊と考え、リストに保存
② 累積和をとる

① 直立、逆立ちそれぞれの連なっている部分を一つの塊と考え、リストに保存

入力の保存

var nk = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
var N = nk[0];
var K = nk[1];
var S = Console.ReadLine();

リストに0と1それぞれの塊の連なりの数を保存

//直立と逆立ちの連なりの数を保存しておくリスト
var list = new List<int[]>();
//現在カウントしている数（0か1）
var currentNum = -1;
//現在カウントしている連なりのカウント
var currentNumCount = 0;
//0（直立）の連なりの数
var zeroCount = 0;
//0（直立）で始まっているかどうか
var isFirstZero = false;
//直立と逆立ちの連なりの塊を1としたときの、Sの中の塊の数
var allCount = 0;

//リストに0と1それぞれの塊の連なりの数を保存
for (int i = 0; i < N; ++i)
{
    //前の数字と今の数字の数が違ったら＝連なりが途切れたら
    if (currentNum != S[i])
    {
        allCount++;
        if (currentNum == -1) isFirstZero = S[i] == '0';
        if (S[i] == '0') zeroCount++;
        if (currentNum != -1) list.Add(new int[2] { currentNum, currentNumCount });
        currentNum = S[i];
        currentNumCount = 1;
    }
    //前の数字と今の数字の数が同じ
    else currentNumCount++;

    //最後の連なりは次に異なる数字が来ないので、indexが最後の場合に保存
    if (i == N - 1) list.Add(new int[2] { currentNum, currentNumCount });
}

変数が多いですが
後の累積和の部分で使用するためのものです。
ここで、重要なことは
0と1の連なりを一つの塊とみなし、
listに0か1かどうかと、
いくつ連なっているのかの数を保存しているということです。

② 累積和をとる

累積和をとります。

//答え
var ans = 0;
//isFirstZero のときlist内の偶数番目が0、そうでないとき奇数番目が0
//一番初め
var c = 0;
if (isFirstZero)
{
    var iC = 2 * K - 1;
    for (int i = 0; i <= iC; ++i) if (i < allCount) c += list[i][1];
}
else
{
    var iC = 2 * K;
    for (int i = 0; i <= iC; ++i) if (i < allCount) c += list[i][1];
}
if (ans < c) ans = c;

//直立を逆立ちにするパターンの数
var count = zeroCount - K + 1;
//累積和
for (int i = 1; i < count; ++i)
{
    //引く
    if (i == 1 && isFirstZero)
    {
        c -= list[0][1];
    }//偶数番目が0
    else if (isFirstZero)
    {
        c -= (list[(i - 1) * 2][1] + list[(i - 1) * 2 - 1][1]);
    }//奇数番目0
    else
    {
        c -= (list[(i - 1) * 2][1] + list[(i - 1) * 2 + 1][1]);
    }

    //足す
    //偶数番目が0
    if (isFirstZero)
    {
        var addIndex = (i + K - 1) * 2;
        c += list[addIndex][1];
        if (addIndex + 1 < allCount) c += list[addIndex + 1][1];
    }//奇数番目が0
    else
    {
        var addIndex = (i + K - 1) * 2 + 1;
        c += list[addIndex][1];
        if (addIndex + 1 < allCount) c += list[addIndex + 1][1];
    }
    //答えよりも大きかったら答えを更新
    if (ans < c) ans = c;
}

一番初めのところでは累積和の始点となる
単純に前からK個0の塊を1に変えたときの
逆立ちの連なりの数を出しています。

/答え
var ans = 0;;
//isFirstZero のときlist内の偶数番目が0、そうでないとき奇数番目が0
//一番初め
var c = 0;
if (isFirstZero)
{
    var iC = 2 * K - 1;
    for (int i = 0; i <= iC; ++i) if (i < allCount) c += list[i][1];
}
else
{
    var iC = 2 * K;
    for (int i = 0; i <= iC; ++i) if (i < allCount) c += list[i][1];
}
if (ans < c) ans = c;

listの偶数番目が0のときと
奇数番目が0のときでは計算方法が違うので分けています。

次に、
累積和をとり
前から後ろへと
0を1にする範囲をずらしています。

//直立を逆立ちにするパターンの数
var count = zeroCount - K + 1;
//累積和
for (int i = 1; i < count; ++i)
{
    //引く
    if (i == 1 && isFirstZero)
    {
        c -= list[0][1];
    }//偶数番目が0
    else if (isFirstZero)
    {
        c -= (list[(i - 1) * 2][1] + list[(i - 1) * 2 - 1][1]);
    }//奇数番目0
    else
    {
        c -= (list[(i - 1) * 2][1] + list[(i - 1) * 2 + 1][1]);
    }

    //足す
    //偶数番目が0
    if (isFirstZero)
    {
        var addIndex = (i + K - 1) * 2;
        c += list[addIndex][1];
        if (addIndex + 1 < allCount) c += list[addIndex + 1][1];
    }//奇数番目が0
    else
    {
        var addIndex = (i + K - 1) * 2 + 1;
        c += list[addIndex][1];
        if (addIndex + 1 < allCount) c += list[addIndex + 1][1];
    }
    //答えよりも大きかったら答えを更新
    if (ans < c) ans = c;
}

for文のループの回数を

//直立を逆立ちにするパターンの数
var count = zeroCount - K + 1;

としていますが、
これは例えば0の塊が5つあるとして
Kが3だとすると
5つの塊の中から連続して
3つを選ぶパターンは
5-3+1=3通りあるので
これをループをまわす回数としています。

ループの中では
K個に入る部分を入れ替えるため、
逆立ちさせる範囲に入らないものを引き
新たに逆立ちさせる範囲に入るものを足しています。

ここでも、
listの偶数番目が0のときと
奇数番目が0のときでは計算方法が違うので分けています。

後は、カウントしたものが
保存してあるansよりも大きいときに
ansの値を更新すれば答えが出ます。

全体のコード

using System;
using System.Linq;
using System.Collections.Generic;

class Dmondai
{
    static void Main()
    {
        var nk = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
        var N = nk[0];
        var K = nk[1];
        var S = Console.ReadLine();
        //直立と逆立ちの連なりの数を保存しておくリスト
        var list = new List<int[]>();
        //現在カウントしている数（0か1）
        var currentNum = -1;
        //現在カウントしている連なりのカウント
        var currentNumCount = 0;
        //0（直立）の連なりの数
        var zeroCount = 0;
        //0（直立）で始まっているかどうか
        var isFirstZero = false;
        //直立と逆立ちの連なりの塊を1としたときの、Sの中の塊の数
        var allCount = 0;

        //リストに0と1それぞれの塊の連なりの数を保存
        for (int i = 0; i < N; ++i)
        {
            //前の数字と今の数字の数が違ったら＝連なりが途切れたら
            if (currentNum != S[i])
            {
                allCount++;
                if (currentNum == -1) isFirstZero = S[i] == '0';
                if (S[i] == '0') zeroCount++;
                if (currentNum != -1) list.Add(new int[2] { currentNum, currentNumCount });
                currentNum = S[i];
                currentNumCount = 1;
            }
            //前の数字と今の数字の数が同じ
            else currentNumCount++;

            //最後の連なりは次に異なる数字が来ないので、indexが最後の場合に保存
            if (i == N - 1) list.Add(new int[2] { currentNum, currentNumCount });
        }

        //答え
        var ans = 0;
        //isFirstZero のときlist内の偶数番目が0、そうでないとき奇数番目が0
        //一番初め
        var c = 0;
        if (isFirstZero)
        {
            var iC = 2 * K - 1;
            for (int i = 0; i <= iC; ++i) if (i < allCount) c += list[i][1];
        }
        else
        {
            var iC = 2 * K;
            for (int i = 0; i <= iC; ++i) if (i < allCount) c += list[i][1];
        }
        if (ans < c) ans = c;

        //直立を逆立ちにするパターンの数
        var count = zeroCount - K + 1;
        //累積和
        for (int i = 1; i < count; ++i)
        {
            //引く
            if (i == 1 && isFirstZero)
            {
                c -= list[0][1];
            }//偶数番目が0
            else if (isFirstZero)
            {
                c -= (list[(i - 1) * 2][1] + list[(i - 1) * 2 - 1][1]);
            }//奇数番目0
            else
            {
                c -= (list[(i - 1) * 2][1] + list[(i - 1) * 2 + 1][1]);
            }

            //足す
            //偶数番目が0
            if (isFirstZero)
            {
                var addIndex = (i + K - 1) * 2;
                c += list[addIndex][1];
                if (addIndex + 1 < allCount) c += list[addIndex + 1][1];
            }//奇数番目が0
            else
            {
                var addIndex = (i + K - 1) * 2 + 1;
                c += list[addIndex][1];
                if (addIndex + 1 < allCount) c += list[addIndex + 1][1];
            }

            //答えよりも大きかったら答えを更新
            if (ans < c) ans = c;
        }
        Console.WriteLine(ans);
    }
}

D - Cake 123

競プロ

はじめに

競技プログラミング、AtCoder Beginner Contest 123
D - Cake 123
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

AtCoder 洋菓子店は数字の形をしたキャンドルがついたケーキを販売しています。
ここには 1,2,3 の形をしたキャンドルがついたケーキがそれぞれ X 種類、Y 種類、Z 種類あります。
それぞれのケーキには「美味しさ」という整数の値が以下のように割り当てられています。

・1 の形のキャンドルがついたケーキの美味しさはそれぞれ A1,A2,...,AX
・2 の形のキャンドルがついたケーキの美味しさはそれぞれ B1,B2,...,BY
・3 の形のキャンドルがついたケーキの美味しさはそれぞれ C1,C2,...,CZ
高橋君は ABC 123 を記念するために、1,2,3 の形のキャンドルがついたケーキを 1 つずつ買うことにしました。
そのようにケーキを買う方法は X×Y×Z 通りあります。

これらの選び方を 3 つのケーキの美味しさの合計が大きい順に並べたとき、
1,2,...,K 番目の選び方でのケーキの美味しさの合計をそれぞれ出力してください。

制約

・1≤X≤1000
・1≤Y≤1000
・1≤Z≤1000
・1≤K≤min(3000,X×Y×Z)
・1≤Ai≤10,000,000,000
・1≤Bi≤10,000,000,000
・1≤Ci≤10,000,000,000
・入力中の値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

X Y Z K
A1 A2 A3 ... AX
B1 B2 B3 ... BY
C1 C2 C3 ... CZ

出力

i 行目に、問題文中の i 番目の値を出力せよ。

解き方

以下を参考にしています。
https://img.atcoder.jp/abc123/editorial.pdf
提出 #4865465 - AtCoder Beginner Contest 123

解き方の流れ

以下では、解説の中の「解法 #1 – 工夫したソートで 𝑶(𝑲^𝟐𝐥𝐨𝐠 𝑲)」で解いています。

ケーキの選び方のパターンを全探索し
おいしさの大きい順番に並び替えれば、この問題は解けますが
時間制限に引っかかってしまいます。

そのため、少し計算量を減らす工夫が必要になります。
全探索をする時間はないので、工程を以下のように分けます。

① A+Bのケーキの組み合わせのパターンを全て出す
② ①で出した組み合わせのパターンを「美味しさ」が大きい順に並び替える
③ ①で出したA+Bの組み合わせのパターンに、Cのケーキの組み合わせを足す


① A+Bのケーキの組み合わせのパターンを全て出す
A+Bのケーキの組み合わせのパターンを全て出し、配列に保存します。

入力の変数の保存

var line = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
var X = line[0];
var Y = line[1];
var Z = line[2];
var K = line[3];
var A = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
var B = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
var C = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).OrderByDescending(x => x).ToArray();

A+Bのケーキの組み合わせのパターンを全て出し、配列に保存

//A+Bのケーキのおいしさを保存する配列
var array = new long[X * Y];
var index = 0;
//Aのケーキ
for (int i = 0; i < X; ++i)
{
    //Bのケーキ
    for (int j = 0; j < Y; ++j)
    {
        array[index] = A[i] + B[j];
        index++;
    }
}


② ①で出した組み合わせのパターンを「美味しさ」が大きい順に並び替える
①で配列に保存したケーキの組み合わせのパターンを「美味しさ」が大きい順に並び替えます。

//A+Bのケーキの組み合わせのおいしさを保存する配列を
//おいしさが大きい順に並び替える
Array.Sort(array);
Array.Reverse(array);

この問題で「OrderByDescending().ToArray()」を使用すると
TLEしてしまうので、
「Array.Sort(),Array,Reverse()」で並び替えています。

③ ①で出したA+Bの組み合わせのパターンに、Cのケーキの組み合わせを足す

//A+BのおいしさにCのおいしさを足すループの長さ
//なるべくループしないように、KかX*Yの小さいほうをとる
var arrayLength = Math.Min(K, X * Y);
//A+B+Cのケーキのおいしさ
var arrayAll = new long[arrayLength * Z];
index = 0;
//A+BにCのおいしさを足す
for (int i = 0; i < arrayLength; ++i)
{
    //Cのケーキ
    for (int j = 0; j < Z; ++j)
    {
        arrayAll[index] = array[i] + C[j];
        index++;
    }
}

Cのケーキの組み合わせを足すループをなるべく少なくするために
KかX*Yの小さいほうをループする回数にしています。

全探索するにはX×Yになりますが
この問題では「1～K番目の美味しさ」を出力すればよく、
A+Bの「美味しさ」にCの「美味しさ」を足した際の全体の「美味しさ」で
「1～K番目に入る美味しさ」は
A+Bの「美味しさ」では必ずK番目以内におさまるので
ループの回数を抑えることができます。

出力例2で説明すると、

出力例２

3 3 3 5
1 10 100
2 20 200
1 10 100

このときA+Bの配列は以下のようになります。

array={300,210,201,120,102,30,21,12,3}

Kは5なので
大きいほうから数えて5番目の102までが
Cを足すときの対象になります。

もしここで、
5個よりも小さい個数、例えば2個を
Cを足すときの対象とした場合
Cのケーキが一つしかなかったら
美味しさを1～2までしか出すことができません。

逆に、
5個よりも大きい個数、例えば8個を
Cを足すときの対象とした場合
Cのケーキが一つだとしても
美味しさを1～8まで出すことになってしまい
3個余分になってしまいます。

そのため、
なるべく無駄なく計算するために
ループの回る回数を
KとX×Yの小さい方としています。

最後に、
A+B+Cのケーキの美味しさを格納している配列を
美味しさが大きい順に並び替え、
K個出力します。

//A+B+Cのケーキの組み合わせのおいしさを保存する配列を
//おいしさが大きい順に並び替える
Array.Sort(arrayAll);
Array.Reverse(arrayAll);
//K個出力
index = 0;
foreach (var ans in arrayAll)
{
    Console.WriteLine(ans);
    if (K <= ++index) break;
}

全体のコード

using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var line = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
        var X = line[0];
        var Y = line[1];
        var Z = line[2];
        var K = line[3];
        var A = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
        var B = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
        var C = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).OrderByDescending(x => x).ToArray();
        //A+Bのケーキのおいしさを保存する配列
        var array = new long[X * Y];
        var index = 0;
        //Aのケーキ
        for (int i = 0; i < X; ++i)
        {
            //Bのケーキ
            for (int j = 0; j < Y; ++j)
            {
                array[index] = A[i] + B[j];
                index++;
            }
        }
        //A+Bのケーキの組み合わせのおいしさを保存する配列を
        //おいしさが大きい順に並び替える
        Array.Sort(array);
        Array.Reverse(array);
        //Cのケーキの組み合わせを足すループの長さ
        //なるべくループしないように、KかX*Yの小さいほうをとる
        var arrayLength = Math.Min(K, X * Y);
        //A+B+Cのケーキのおいしさ
        var arrayAll = new long[arrayLength * Z];
        index = 0;
        for (int i = 0; i < arrayLength; ++i)
        {
            //Cのケーキ
            for (int j = 0; j < Z; ++j)
            {
                arrayAll[index] = array[i] + C[j];
                index++;
            }
        }
        //A+B+Cのケーキの組み合わせのおいしさを保存する配列を
        //おいしさが大きい順に並び替える
        Array.Sort(arrayAll);
        Array.Reverse(arrayAll);
        //K個出力
        index = 0;
        foreach (var ans in arrayAll)
        {
            Console.WriteLine(ans);
            if (K <= ++index) break;
        }
    }
}