突然ですが、みなさんはTechFULのチャレンジ問題やTCBの問題に挑戦するときにどのような練習方法を行っているでしょうか？
様々な書籍、サイトを参考にして自らのスキルを向上させて挑んでいる方も多いとは思いますが、今回はTechFUL内で自分がおすすめするプラクティス問題を解き、解説を読むことでスキルを向上させる方法を紹介したいと思います。
チャレンジ問題の意義はみなさんのスキルを可視化することにあるためノーヒントで問題を解く必要がありますが、プラクティス問題の意義は考える力をアップデートすることにあり、コード提出後にテストケースを見ながらデバッグすることができます。また、過去のコンテストの問題などから成っているため、おおよその問題で解説も公開されております。
そこで、カテゴリおよび難易度別にピックアップしたおすすめの問題を紹介していきたいと思います。今回は、プログラミング基礎, アルゴリズム, 数学のカテゴリから初級, 中級の問題をピックアップしました。
各問題リンクの下にある、解説と書かれた折りたたみタブの中にはその問題のざっくりとした解説を載せてあります。
プログラミング基礎
プログラミング基礎のカテゴリに入っている問題は全て初級問題です。全ての問題を解いて欲しい所ではありますが、ここではおすすめの問題を5問紹介します。
初級
for文によるループを用いて問題文に書かれた通りに実装すると計算量
でこの問題を解くことができます。
しかし、式変形を行うことで
で解くことができます。
挑戦する問題の難易度が上がってくると、こういった式変形による計算量の改善が度々登場するようになるため、
で解かなかった人も式変形の流れを一度追っておくとよいでしょう。
この問題は1の位から3桁毎にカンマを入れていく問題です。
8桁の
自然数と指定されているため、整数を文字列とみて決められた位置にカンマを挿入することで解くことができます。
桁数が一般の場合は1桁目(文字列として見たときの末尾)から順に見ていき、3の倍数個整数を読み、かつ次の桁の数字が存在する場合にカンマを挿入することで解くことができます。
今回は必要無い解法ですが、こちらの「逆順から見る」操作も頻出のテーマなので頭の片隅に入れておくとよいでしょう。
この問題はX座標が指定された3点が一直線上に並ぶかどうか判定する問題です。
指定されるX座標が1,2,3と等間隔で1になっているため、後はY座標の増加度がAB間、BC間で等しいか判定すればよいです。
幾何の問題は度々登場しますが、この問題はそれらの入門といった立ち位置の問題となっています。
前問と同様に、X座標や点の個数などの設定を一般化したときの問題も解くことが可能なので考えてみましょう。
この問題は2種類の操作から選ぶことを繰り返し、最終的に全ての要素を0にできるか？という問題です。
こういった、行う操作と順番が任意で選べるときに条件を満たすことができるか？というような問題は頻出の形です。
今回の場合、行う操作が決まるとその順番を入れ替えても最終的な要素は同じになること、1個目の操作は各要素に対し高々1回しか行えないこと、2個目の操作では異なる要素を等しくできないこと等の考察によって行うべき操作を単
純化し解くことができます。
いずれの問題においても、操作の内容やその順番を適切に言い換えて単
純化できないかどうかを考えることはとても大切です。
この問題は、K進数における2つの整数の足し算において繰り上がりが発生するか？という問題をQ個解く問題です。
問題文中に繰り上がりに関する重要なヒントが書いてあるため、各桁について見ていき繰り上がりが発生するような桁が1つでも存在すればYes、存在しないならNoを出力することで解くことができます。
全探索が可能であればすること、問題文内のヒントは余さず活かすようにすることが大切です。
今回の問題はクエリ毎独立に解くことができますが、クエリを適切に並び替えたり、クエリを読む前に前計算しておくことで高速に解答する必要がある問題も存在するため、注意しておきましょう。
アルゴリズムのカテゴリではその名の通り、解くために様々なアルゴリズムを実装する必要がある問題が並べられています。
初級
N×Nの配列を回転させた状態を出力する問題です。
2次元配列の添え字に関する理解を深めることができます。
制約の小ささに注目して利用する問題です。
初期状態の何かに対して何回か操作を施してできるものを答えさせる問題では、最終的に生じるものから逆算して初期状態にできるか？という問題を考えると解きやすくなることが度々あります。
愚直な全探索
アルゴリズムを素直な発想で高速化する問題です。
ある値を決め打ちすると別の値も決めることができることを利用した計算量の改善は典型的です。
少ない操作回数でf(N)が一定の値になることに気づけば、後は
再帰的に処理することで解ける問題です。
再帰関数を用いずとも解くことはできますが、練習で実装してみてもよいでしょう。
電車の移動と乗客の乗り降りをシュミレーションする問題です。
で問題なく解けますが、
でも解けるのでこちらの解法にも挑戦してみましょう。
少し変則的な貪欲法で解ける問題です。
と
の大きい方を選び続ける解法は正当ですが、実装面において罠があるため気をつける必要があります。
グラフに対する操作が必要な問題です。
グラフ理論における木の性質に対する理解を深めることができます。
操作の内容を単
純化した上で貪欲にシュミレーションする問題です。
基本的なデータ構造の使い方を学ぶことができます。
ゲーム理論と実装問題の中間といった問題です。
未知の値を全探索することで解くことができます。
条件を全て満たすように、2つの
区間を狭めていくことで解くことができます。
あるマスが宝の埋まっているマスかどうかを考えて全探索しようとすると実行時間制限内に間に合わないことに注意しましょう。
中級
偶奇と一点賭けができるルーレットについて賭け金と返却枚数の情報が与えられるので、当選した整数としてあり得るものの種類数を答える問題です。
数字を全探索していては実行時間制限内に収めるのは厳しいですが、与えられた情報に存在する整数とそれ以外の整数に分けて考えることで解くことができます。
また、0の存在の有無がコーナーケースとなっているため注意しましょう。
文字列Sから文字列Tを、何回部分文字列として取り出せるかという問題です。
取り出す位置の組み合わせを全探索しようとすると計算量が爆発してしまいますが、制約のTの条件から考えて最適な取り出し方を1種類に固定することで解くことができます。
制約にその問題を解くための重要な情報が載っていることが多々あるため、問題文と同様にしっかりチェックすることが大切です。
クエリ形式で問題が与えられますが、クエリの個数の最大値があり得る盤面数と同じため結局全ての盤面に対する解を求めることが要求されています。
多始点からの探索において終点が1点であるときは、終点から逆算することで計算量を抑えることができます。
問題タイトルにあるようにセグメント木と呼ばれるデータ構造をテーマとした問題です。
一般にセグメント木の実装では
区間を2分割することを繰り返すようにした実装がなされますが、それを参考にして
区間を3分割することを繰り返して実装することで最適な解が得られます。
セグメント木自体も頻出のデータ構造なので、実装したことがない方はこの機会に実装してみましょう。
の全探索を、文字種の種類数の少なさを用いて改善する問題です。
このように、登場する値(整数や文字など)の種類数の小ささを利用する場合があることを覚えておきましょう。
各回においてそのとき一番楽しさが大きいものを選び続けるという貪欲法は見えやすいと思います。
今回の問題はその貪欲法を
アルゴリズムを用いて高速化することが求められています。
T回の行動における最小値がx以上か？という判定問題に単調性があることを利用して二分探索を用いることで解けます。
ある判定問題に単調性があると気づいたときは二分探索の利用を考えましょう。
一つ目の移動方法のみ利用できる場合の解は
ダイクストラ法と呼ばれるグラフ
アルゴリズムを使って解くことができます。
この問題も各街に対して年代や年代の移動回数などの情報を持たせた頂点を用意する(各街について複数個頂点を作る)ことで
ダイクストラ法で解けます。
このように、既存の
アルゴリズムが適用できるようにお膳立てをする問題は典型的です。
union-findと呼ばれるデータ構造を利用する問題です。union-findでは集合の併合操作は可能ですが、分割操作は難しいため逆順から考えるテクニックを利用して解くことになります。
また、連結成分数を高速に求めるためグラフが常に森であることも利用する必要があります。
ちなみに、集合の分割操作が可能な高度なデータ構造も存在します。
多角形上での鬼
ごっこをテーマにした少し難しいゲーム問題です。
偶奇問わずはじめの行動だけを全探索することでその後の行動を単
純化できますが、証明が少し大変です。
こういった問題では小さいサイズのケースを手計算して実験してみたり、証明が大変な予想をコンピュータ上である程度成り立つことを確認することが役立つ場合があります。
愚直な全探索が間に合わない問題です。
切り分ける位置を1つずらしたときの左部分と右部分それぞれの差分を考えると、両端から位置に依存した累積和を取ることで高速に求めることができると分かります。
両端から考える発想は少し難しいですが、覚えておくとよいでしょう。
数学
数学のカテゴリでは整数論アルゴリズムや式変形を用いて愚直な全探索を高速化させる問題などが多く登場します。
初級
この問題はfor文などのループに加え、基本的な算術演算と条件分岐によって解くことができます。(解説の方針1に相当)
しかし、解説の方針2のように適切な場合分けと式変形を施すことで
でも解くことができます。
中級以上になってくると、方針1では実行時間制限内に収まらないような制約となることがほとんどであるため、練習がてら方針2で解いてみましょう。
XORに関する理解度と、
アルゴリズムの高速化を要求する問題です。
XORが登場する問題ではビット毎に考えることで解ける問題もあるため、理解を深めておくとよいでしょう。
また、
アルゴリズムの高速化パートでは主客転倒と呼ばれる典型的な知識が必要となるためこちらも覚えておきましょう。
一見すると確率dp等で順に求めていく問題にも見えますが、この問題は数学的手法で高速に解けます。
コインの枚数が0枚となるときに注目すると、2のべき乗を用いて求めることができます。
2のべき乗に関して、想定解では繰り返し二乗法と呼ばれる
アルゴリズムで高速に計算しています。応用が利く
アルゴリズムなので知らなかった方は学んでおくとよいでしょう。
問題タイトル通りシンプルな式を展開する問題です。
多項式を扱う問題は実は高難易度の問題で頻出のテーマであるため、慣れておくとよいでしょう。
数学の初級問題の中ではトップクラスに難しい問題です。
毎回愚直に計算していては実行制限時間内に間に合わないので、考える必要がある対象を絞り込む必要があります。
また、絞り込んだ上で二分探索によって○以上の最小の値などを見つける必要があります。
中級
の約数の個数を答えよというシンプルな数学問です。
整数
の
素因数分解といえば
の
アルゴリズムが有名ですが、今回はその
アルゴリズムでは間に合わないため
の
素因数分解の結果を観察する必要があります。
逆に、
が
の各素因数の個数を
倍しただけに過ぎないことに気づけば、愚直な
の
素因数分解アルゴリズムで解くことができます。
余談ですが、大きな桁数の
素因数分解は高速に計算することが一般的に難しいとされており、暗号の基盤としても利用されています。確率的
アルゴリズムであればある程度高速な
素因数分解法も存在します。
内容はとてもシンプルですが、愚直な計算が間に合わずとっかかりも少ないため初手を考えるのが難しい問題です。
難しい式変形と、
の種類数が
で抑えられることに気づくこと(
が
以上かどうかで場合分けすると分かります)が肝となります。
与えられた数字を並び替えてできる全ての整数を足し合わせた数を求める問題です。
先行ゼロを含む数を求めないために、最上位の数を全探索する工夫が必要になります。
問題の言い換えと式変形を繰り返して高速化することを要求される難問です。
が大きいテストケースがたくさん与えられる可能性があるため、前計算した上で各クエリ毎に
で答えることが求められています。
終わりに
練習用におすすめなプラクティス問題を初級,中級に絞っていくつか紹介してきましたが、いかがだったでしょうか。
この記事で紹介したプラクティス問題を全て解けるようになればチャレンジ問題やTCB等の中級レベルの問題にも十分太刀打ちできると思います。
今回は紹介しませんでしたが、上級レベルの問題はどれも個性的で時に高度な知識が得られる問題も数多く存在するため、実力が付いたと感じたらどんどん挑戦していって欲しいです。
それではよいTechFULライフを！
