TOPSIC初心者による攻略

■はじめに

社でTOPSICが導入されたので普段プログラムの設計や実装に携わっていない方向けに、序盤に躓かない為のHOWTOを記したいと思います。問題は公開できないので問題の解説はできません。
尚、お断りしておくと、筆者自体もTOPSICやその他競技プログラミングの素人なので、その点ご了承ください。

■環境準備

切れないインターネット環境

挑戦中に切断されても救済措置はありません。

大きなモニター（デュアルモニタなら尚良し）

挑戦中は常に問題文を見ながらが望ましいです。問題文を表示するスペースとプログラミングや調査等の作業スペースを両方確保したいところ。
プリンタが近くにあるなら問題文を印刷してもいいですが、問題文の入力をコピペすることを考えるとデュアルモニタがベスト。

コードエディタ（コーディング環境）

TOPSICには当然ながら解答欄がコードエディタになっています。これが使いにくいのなんの。
使用言語やブラウザにも依存しますが、サジェスト（コードの自動保管）機能が貧弱です。Visual Studio Codeでもeclipseでも構いませんので自分の使用したい言語の実行環境を用意しておきましょう。
面倒な方はTOPSICのエディタとあまり変わらないけど paiza.io のオンライン実行環境の方がマシかもしれません。paiza.ioはTOPSICと同じくLinuxで実行されるのでその点ではメリットがあります。

図や式が描けるもの

思考が全て脳内で完結する人は要らないかもしれませんが、大抵の人は図を書いたりした方がロジックを纏めやすいと思います。
紙とペンでも、お絵描きソフトでも、ブギーボードのような電子メモでも良いでしょう。電子メモの場合は消しゴム機能や保存機能の有無が分かれますのでお好みで使いやすいものを。

■前提知識

使い方を学ぶ

やり方を知らないとどうにもならないのでまずはTOPSICの「使い方」について読んでおきましょう。

・受験ルール・用語
・受験チュートリアル
・練習問題

使用言語の選択

自分が得意な言語を選択するのが一番です（社から指定される場合はどうしようもない）。
但し、実行時間の制限というものがあり、Linuxの仮想環境上で起動されたプログラムの開始時刻から終了時刻までがその制限実行時間内でなければ「TLE (Time Limit Exceeded)」となり、事実上の不正解です。ついでに使用メモリの制限もあります。
TOPSICの場合、使用言語毎に差異なく一律固定の秒数となっていますので、非コンパイル言語の不利は否めません。

標準入出力の方法

各言語での標準入力、標準出力の方法を知っていないと回答すらできません。

前項の「練習問題」にご丁寧に各言語での入出力サンプルが問題文の中に掲載されていますので参考にしましょう。
以下はJavaの場合（TOPSICの練習問題コードを転載）。

import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int a = sc.nextInt();
		// スペース区切りの整数の入力
		int b = sc.nextInt();
		int c = sc.nextInt();
		// 文字列の入力
		String s = sc.next();
		// 出力
		System.out.println((a+b+c) + " " + s);
	}
}

Javaの場合ですが、クラス名はMainでなければなりません。パッケージ定義は不要です。
このコードをローカルのコードエディタに移植すると「スキャナーが閉じられていないよ」みたいなメッセージが出る場合があると思います。本来はtry-with-resource構文やtryのfinally句でクローズすべきなのかもしれませんが、少なくともTOPSICにおいては必須ではないです。逆にクローズした場合は、その後まかり間違って再度System.inから標準入力を読み取ろうとするとうまくいかなくなります。

【参考】try-with-resource構文

        try (Scanner sc = new Scanner(System.in)) {
            int a = sc.nextInt();
            …
        }

基本的にTOPSICで扱う『入力』においては「整数」「文字列」のいずれかになっていると思います（確約できないけど）。
標準入力を媒介してくれるScannerオブジェクトで使用するメソッドはせいぜい以下の3つになると思います。尚、内容欄は厳密に正しくはありませんが、雰囲気こんな感じです。

メソッド	内容
nextInt()	次のトークンをint型で取得する。 取得後に次のトークンの位置に移る。
next()	次のトークンをString型で取得する。 取得後に次のトークンの位置に移る。
nextLine()	次の改行文字の直前までの文字列をString型で取得する。 取得後に次の行に移る。

まずnextInt()とnext()についてですが、トークンというのは空白文字で区切られた単位、すなわち単語のようなものだとイメージしてください。
この空白文字にはスペースや改行も含まれます。よって前述の練習問題サンプルコードでは以下の形式のいずれも正常に読み取ることができます。変数aに1、bに23、cに456、sに"abcd"がセットされます。

1 23 456 abcd

1
23
456
abcd

1 23
456 abcd

一方、nextLine()はトークン単位ではなく、行単位で文字列を取得するメソッドです。取得内容にはスペースやタブ等の空白文字を含みますが、改行文字は含みません。
以下のサンプルコード2があったとします。

import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 文字列の入力
		String s1 = sc.nextLine();
		String s2 = sc.nextLine();
		// 出力
		System.out.println(s1 + " " + s2);
	}
}

先ほどと同じ入力パターンを試すと以下のようになります。

1 23 456 abcd

変数s1には"1 23 456 abcd"がセットされます。
2回目のnextLine()で読み取れる内容がなく、「java.util.NoSuchElementException」が発生します。

1
23
456
abcd

変数s1には"1"、s2には"23"がセットされます。
残りの標準入力は虚空に消えます。

1 23
456 abcd

変数s1には"1 23"、s2には"456 abcd"がセットされます。

ややっこしいのがnextInt()、next()と、nextLine()を混ぜて使用した場合です。

以下のサンプルコード3があったとします。

import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int a = sc.nextInt();
		// 文字列の入力
		String s = sc.nextLine();
		// 出力
		System.out.println(String.format("[%d] [%s]", a, s));
	}
}

先ほどと同じ入力パターンを試すと以下のようになります。

1 23 456 abcd

変数aには1がセットされます。
変数sには" 23 456 abcd"がセットされます（nextLineは先頭の空白文字も取得します）。

1
23
456
abcd

変数aには1がセットされます。
変数sには""がセットされます。なぜかというと、nextLine()は現在行の中で、次の改行文字の直前までの文字列を取得します。nextInt()を実行した時点で、Scannerの現在位置は1の後ろ、改行文字の手前という微妙なポジションになります。先頭の行の中で1より後ろで改行文字の直前までの文字は1文字もありませんので空文字になります。

1 23
456 abcd

変数aには1がセットされます。
変数sには" 23"がセットされます。
これまで解説したルール通りです。

標準出力についてはSystem.out.println()で十分です。

■事前準備

TOPSICは制限時間が割と厳しめ（難問単独より難問＋易問の方が易問の制限時間が合算できて時間的余裕ができたりする）。
できる限り時間短縮できるよう準備をしておきましょう。

検索画面の用意

他人に答えを聞くのは論外としても、ググるのは別に禁止されていません。
言語仕様、標準ライブラリの使用方法、アルゴリズム…わからんってなったら即検索。「java 部分配列」「java 重複検知」「java 二分探索」とか自分の使用する言語＋キーワードで検索すれば大抵のことは出てきます。

テンプレートの用意

いくら検索し放題とはいえ、検索して出てきた内容を理解していきなり使いこなすのは大変なものもあるので、基本的なこと、頻出内容については予めテンプレートを用意しておくのが良いでしょう。

標準入出力

どの問題も必ず「入力」と「出力」があります。
どうせ用意するのですから、前述のサンプルコードを参考に初っ端にペーストするテンプレートを用意しておきましょう。
入力に可変要素がある場合は、ほぼほぼ先頭行の第一要素にその可変要素数が来ると思って良いでしょう。
あとはその可変要素数分ループし、入力を取得すれば良いです。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            int n = sc.nextInt();
            List<String> inputList = new ArrayList<>(n);
            for (int i = 0; i < n; i++) {
                inputList.add(sc.next());
            }
        }
        System.out.println(inputList);
    }
}

import

javaならimport java.util.*;は最初に含めておきましょう。
そもそも入出力に必要なScannerがjava.utilパッケージだし、ListもMapも使わないケースの方が稀でしょう。
業務プログラムだと規約でimport xxx.*の使用が禁止されているケースもありますが、必要になってから書くのも鬱陶しいし、TOPSICにそんな縛りはない。
pythonならmath、decimal、bisect、functoolsあたり？これは必要になってからで十分かも。

型変換（文字列⇔数値）

大抵は入力された整数文字列の数値化でしょう。

// 文字列 ⇒ 数値 "123"⇒123
int i = Integer.parseInt(s);
// 数値 ⇒ 文字列 123⇒"123"
String s = String.valueOf(i);

パディング

大抵は前方0パディングでしょう。

// 5桁に揃える。 123⇒"00123"
String s = String.format("%05d", i);

文字列比較

javaの場合は==ではなく、String.equals()で比較することを忘れないようにしましょう。

文字列分割

javaの場合はString.split()を使います。参考までに、第1引数はデリミタで、正規表現です。

// 全文字をばらばらにする。 "abcd"⇒{"a", "b", "c", "d"}
String[] a1 = s1.split(""); 
// 空白で分割する。 "a b c d"⇒{"a", "b", "c", "d"}
String[] a2 = s2.split(" "); 

部分文字列

文字列中の一部を抜き出します。
javaの場合はString.subString()。開始と終了のインデックスを引数で渡しますが、第2引数で指定した終了インデックスの文字は含まれないことに注意。

// 3文字目（インデックス2）から5文字目（インデックス4）までの計3文字を抜き出す。
// 6文字目（インデックス5）は含まれない。
// "abcdef"⇒"cde"
String sub = str.substring(2, 5)

連結

配列やリストを連結して１つの文字列にします。
javaの場合はString.join()。第1引数にデリミタ、第2引数に繰り返し要素を指定します。

// 配列連結 {"a", "b", "c", "d"}⇒"abcd"
String s1 = String.join("", a);
// List連結 ["a", "b", "c", "d"]⇒"a,b,c,d"
String s2 = String.join(",", l);

四捨五入、切り捨て、切り上げ

数学ライブラリを使用します。javaの場合はMath。

// 小数点1位の四捨五入 4.5⇒5
double d12 =Math.round(d11)
// 切り上げ 4.1⇒5
double d22 =Math.ceil(d21)
// 切り捨て 4.9⇒4
double d32 =Math.floor(d31)

javaの場合、Mathクラスが小数点1位以外の四捨五入をできないしょんぼり仕様なので、それ以外の四捨五入をしたければBigDecimalを使用します。

// 小数点2位の四捨五入 3.14⇒3.1
BigDecimal b2 = b1.setScale(1, BigDecimal.ROUND_HALF_UP);

累乗

累乗はxのy乗（2の3乗⇒2×2×2）、みたいな計算のことです。
javaの場合、専用の演算子がないので、数学ライブラリを使用します。

// 累乗演算。引数も返却値もdouble。2.0,3.0⇒8.0
int i = (int) Math.pow(d1, d2);

絶対値

負の値の場合、符号を反転する。正の値はそのまま。
javaの場合、数学ライブラリを使用します。

// 絶対値。-2⇒2
int i2 = Math.abs(i1);

最大値、最小値

引数の中で最大値、最小値を抽出する。
javaの場合、数学ライブラリを使用しますが、2つの引数同氏の大小しか対応していないポンコツ。

// 最大値。1,2⇒2
int i3 = Math.max(i1, i2);
// 最小値。1,2⇒1
int i4 = Math.min(i1, i2);

TOPSICでありがちな、パターンの中で最大（小）値を求めよみたいな問題で、ループ中で最大（小）値を発見したら更新、みたいな処理はif文を使うのではなく最大値、最小値で片付ける。

int max = 0;
for(int i = 0; i < 10; i++) {
    // if (max < i) {
    //     max = i;
    // }
    // ↑ではなく↓
    max = Math.max(max, i);
}

重複の検知

集合にインプットを全部ぶち込んで、ぶち込み前とサイズが変わらなければ重複はないってことです。
javaならSetを使用します。

Set<Integer> set = new HashSet<>(list);
set.size() == list.size() ? "重複ないよ" : "あるよ";

ついでにリストから重複を排除したい場合。Setをリスト化すると順序が崩れてしまうので順序保持したい場合は以下のようなコードにします。但し、IntegerとかStringとかのリストならこれで良いですが、独自クラスのリストの場合、独自クラスでequals()とhashCode()をオーバーライドしておく必要があります。

List destList = srcList.stream().distinct().collect(Collectors.toList());

ソート

並べ替え。自然順序のソートなら話は単純です。
javaならList.sort()が便利です。配列ならArrays.sort()。
独自クラスのソートとか複合条件ソートとかになると話がメンドウになってくる。

// 自然順序での昇順ソート
srcList.sort();
// 自然順序での降順ソート
srcList.sort(Collections.reverseOrder());

// 独自クラスのソート（イメージ）
Comparator<User> comparator
    = Comparator.comparing(
        User::getName).thenComparing( // 第一ソート条件
        User::getAge, Comparator.reverseOrder()); // 第二ソート条件（逆順）
srcList.sort(comparator);

検索

リストや配列中にある要素があるかどうか。
集合か辞書を使います。javaならSetかMapです。
自分で検索処理実装しようとか考えない。

Set<Integer> set = new HashSet<>(list);
System.out.println(set.contains(i) ? "あるよ" : "ないよ");

ところがリストの要素がプリミティブ値ではなかったり、閾値を探りたいような場合には役に立ちません。しかし独自二分探索を即興でプログラミングしようとすると火傷するので、カスタマイズしやすい二分探索コードの一例をご紹介します。但し、昇順ソート済みであることが前提です。

めぐる式二分探索のテンプレート（参考URL）

// まずisOkを定義すべし。
private static boolean isOk(int i) {
    // 何をもってOKとするかは都度定義する。
    return 引数がOKかどうか判断するコード;
}

// ng < okの場合
// 初期値のng,okを受け取り,is_okを満たす最小のokを返す。
// ngはとり得る最小の値-1
// okはとり得る最大の値+1。
// ng > okの場合
// 初期値のng,okを受け取り,is_okを満たす最大のokを返す。
// ngはとり得る最大の値+1
// okはとり得る最小の値-1。
private static int meguruBisect(int ng, int ok) {
    while (Math.abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;
        if (isOk(mid)) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    return ok;
}

以下は使用法の一例です。
とある配列の中で値が5以上の要素の境界のインデックスを取得したいとします。この目的に合わせてisOK関数を定義します。
配列の要素数は8で、取り得る最小のインデックスは0、最大のインデックスは7なので、それぞれ-1、+1して-1、8を引数に渡します。
返却値は4となり、これは配列中のインデックス4以上の要素は値が5以上であることを示しています。

// 昇順ソート済み配列
static int[] a = {1, 1, 2, 3, 5 ,8, 13, 21};
// 問題に合わせたisOK関数定義
private static boolean isOk(int i) {
    // 配列aのインデックスiの値が5以上ならtrueを返す。
    return a[i] >= 5;
}

public static void main(String[] args) {
    System.out.println(meguruBisect(-1 , 8)); // ⇒4
}

フィルタリング

リストや配列中から条件を満たす要素のみを抽出します。
javaならStream.filter()が便利です。

// filter()内に独自フィルタリング処理を実装。以下は偶数フィルタの例。
srcList.stream().filter(i -> i % 2 == 0 /* 独自のフィルタ処理 */).collect(Collectors.toList())

■実施に際して

数値型の最大/最小値、及び精度について

使用言語によって特性が違うので注意してください。
javaのint型は32bitで、最大値は約21億（2の16乗-1）です。TOPSICで扱う数字は問題によっては、この2の16乗を超えてくるケースがあります。long、BigDecimal等の使用を検討してください。
浮動小数点数の精度もjavaのfloatの精度では不足するケースがあります。

尚、BigDecimalは通常の演算はできないのでBigDecimal自身の演算メソッドを使います。特に除算は精度と、無限小数をどう扱うかを指定する必要があるなど、ちょっと癖があるのでご注意ください。

// 商が無限小数となる場合は小数点第21を四捨五入する除算。
BigDecimal b3 = b1.divide(b2, 20, RoundingMode.HALF_UP);

ループは慣れているスタイルで。

レガシーな言語はスタイリッシュなループな方法が取れなかったりするのですが、殊、javaにおいてはStreamやIterable等for each系のループや拡張for文は自信がなければやめておきましょう。for each系を使用したループはbreak、continueの扱いが難しいし、javaの拡張for文はインデックスが取得できないので、そんだったら最初からレガシーforループでいいやって感じです。但し、取り扱うリストは配列やArrayList等のランダムアクセスが速いものが良いでしょう。
インデックスについてはjavascriptなら配列のforEachの第2引数、pythonならenumerate()が使いやすいでしょう。

最終手段：力技で解く。

取り得る選択肢がx個あるものが全部でy個ある。ある選択肢を取った時のポイント（コスト）は〇〇〇で、最大ポイント（or最小コスト）を求めよ～みたいな問題が出ることがあります。
本来〇〇〇の内容に応じてロジックに工夫を凝らし最小限の演算で解答を導くのが美しいのですが、どーにもわかんないっていう時の最終手段。
全パターンのポイント（コスト）を算出しちゃう。TOPSICの目的に照らしてどうなのよっていうのは知らん。
そのパターン数はxのy乗。
選択肢がon/offの2パターンのものが10個並んでます、みたいな問題の場合、2の10乗パターン。このパターンを順番に処理しないきゃいけないとなると、以下のようなパターンの羅列が必要になってきます。
0000000000
0000000001
0000000010
0000000011
0000000100
0000000101
…

x=2固定の場合に使用できるコード。

int y = 10;
int p = (int) Math.pow(2, y);
for (int i = 0; i < p; i++) {
    for (int j = 0; j < y; j++) {
        if (((i >> j) & 1) == 1) {
            // onの時何かする。
            System.out.print("1");
        } else {
            // offの時何かする。
            System.out.print("0");
        }
    }
    // これは要らない。
    System.out.println("");
}

このサンプルの場合、
0000000000
1000000000
0100000000
1100000000
0010000000
1010000000
…
みたいな出力になります（下位ビットから処理しているので上下反転しています）。

x=2以外の時はどうするか。
3の4乗の場合はこんな感じになります。

int x = 3;
int y = 4;
int p = (int) Math.pow(x, y);
for (int i = 0; i < p; i++) {
    String nBitString = Integer.toString(i, x);
    String fullFilledNBitString = String.format("%" + y + "s", nBitString).replace(" ", "0");
    System.out.println(fullFilledNBitString);
}

このサンプルの場合、3進数になるので、
0000
0001
0002
0010
0011
0012
0020
0021
…
みたいな出力になります。あとはこの文字列を分解して、0の場合、1の場合、2の場合…に応じて何かしましょう。
（ちなみに今適当に考えたコードなのでバグっているやも…）

計算量爆発

前項の力技を含めて、殆どの場合、ロジック内にループ処理が登場すると思いますが、パターン数が多すぎる場合、計算しきれません。
1ループ内の処理にも寄りますが、頑張っても（ループ内の処理が軽くても）10の8乗、9乗あたりのループ数からダメになってくるかもしれません。大体億になってくるとだめというイメージ。
制限実行時間内に計算が完了しない。
ネスト（多段）ループの場合はループ回数の乗算です。10回のループの3段の場合は10の3乗で1000ループ。ループ内の処理に要素数に依存する処理が含まれる場合は処理時間が線形時間O(n)となるのでネストループが存在するのと同じと思ってください。
ある要素のリストが与えられて、単純に組み合わせを試していくと計算量は二乗時間O(n²)となります。要素数が10の4乗なら10の4乗の2乗で10の8乗。もうダメっぽいスメルがします。
問題を読み解き、存在しないパターンの法則を見つけ出すとか中間値を計算してO(n²)⇒O(n)に変換するとか分割統治によりパターン数の組み合わせを低減するとか、このあたりは問題によって対応が異なると思われるので必勝法はないような気がしています。まぁこれを考える能力を計るのがTOPSICの本来の目的なのでしょうが…。

おまけ

遠慮なくデバッグ用のprint文を書いていい。

ローカル開発環境でデバッガを使っている分には問題ないですが、オンライン実行環境ではprint文がデバッグの主力になります。
ロジックが複雑な場合は最終的な回答のprint文だけ出力しても、途中がどううまくいっているのかいっていないのか、良く分からないことが多いでしょう。
コードの前後でbefore＆afterを出力した方が結果的に早くロジックの誤りを発見できるかもしれません。
デバッグ用の文を消すのは提出用コードの時だけで十分。
但し、うっかりデバッグ用の文を残したまま提出しないようにご注意。。

被除数が負数の場合の商と剰余について、言語により結果が異なる。

負の値を除算した場合、例えば-5を2で割った場合、商と剰余は何になると思いますか？
処理系によって答えは異なります。自分の使用する言語の特性を知っておきましょう。

Java　-5 / 2　⇒ -2 剰余 -1 （-2 × 2 - 1 = -5ということ）
Python -5 / 2 ⇒ -3 剰余 1 （-3 × 2 + 1 = -5ということ）

■おわりに

内容に不備、誤り、不明点ありましたらどうかご指摘くださいm(_ _)m