paiza開発日誌

IT/Webエンジニア向け総合求人・学習サービス「paiza」の開発者が、プログラミングやITエンジニアの転職などについて書いています。

20200204140738

ITエンジニア向け総合求人・学習サービス「paiza」の開発者が、プログラミングやITエンジニアの転職などについて書いています。

VC投資先スタートアップ企業特集

Pythonで難しい問題を解きたい人向け・段階別&解答例付き問題集

f:id:paiza:20210122194937j:plain
f:id:paiza:20180910132940p:plainこんにちは。倉内です。

プログラミング学習で大切なのは、インプットと同時に自分でコードを書いてアウトプットをすることです。

paizaラーニングの学習講座は動画を見るだけでなく、自分でコードを書いて解く課題が設定されています。また、さまざまなプログラミング問題を解く場として、スキルチェックや問題集も公開しています。

四則演算や条件文・ループ文、配列や関数などを使う基本的な問題が解けるようになったら、ぜひそれらを組み合わせたり、実行速度を考慮したりして解く難易度が高い問題にも挑戦してみてください。

とはいえ、どのように取り組めばよいか、また分からないときに参考にできるコードや解説がなく諦めてしまってはあまり勉強になりません。

そこで今回は、先日全問題のPython3の解答コード例・解説を公開した、レベルアップ問題集の「Aランクレベルアップメニュー」を使って一緒にスキルアップを目指しましょう!

レベルアップ問題集」で着実にスキルを伸ばす

レベルアップ問題集では、計算問題や文字列、図形を扱う問題、法則を見つけたりアルゴリズムを使って解く問題など多様な練習問題をご用意しています。

問題はS・A・B・C・Dと難易度分けがされていて、Sランクが最高難易度となります。この難易度はpaizaが提供しているプログラミングスキルを測るサービス「スキルチェック」のランクと対応しています。詳細はこちら

レベルアップ問題集では、テストケースの入力値や一部問題の解答コード例を見ることができ*1、また問題についてSNS上で友人と相談したりコードを公開したりすることも可能です。

f:id:paiza:20210125192219j:plain

よって「とにかくプログラミング問題をたくさん解いて勉強したい」「難易度の低い問題が解けたら段階的に難しい問題に取り組んでみたい」という方には特におすすめです。

「Aランクレベルアップメニュー」で目指すこと

「レベルアップメニュー」シリーズは、ゴールとなるランクの問題を解けるようになるために、それよりやさしい問題を複数解くことで考える力・書く力をつけ、段階的にゴールを目指すことを目的としています。

今回扱う「Aランクレベルアップメニュー」は、Cランク相当・Bランク相当の問題に取り組んで、最終的にAランク相当の問題を解くことを目指します。

20210122201446

問題のセットはいくつかありますが、ここでは「陣取りゲーム」を例に実際のC、B、Aランク相当の問題を見てみましょう。

なお、プログラミングを始めたばかり、または基本的な文法は分かるけどあまりプログラミング問題を解いたことがないという方は、「Cランクレベルアップメニュー」「Bランクレベルアップメニュー」に先に取り組んでみていただくとよいかもしれません。

Aランク相当の問題「陣取りゲーム」を解くステップ

陣取りゲームは、Cランク相当の問題2つ、Bランク相当の問題3つ、最後にAランク相当の問題という構成になっています。

20210122215157

Aランク相当の問題を解くために必要な考え方やコードの書き方をC、Bランク相当の問題で段階的に理解することが可能です。

以降でC、B、Aそれぞれのランクに相当する問題を実際に解いてみましょう。コードを自由に書いて実行できるオンライン環境「paiza.IO」も適宜活用してください。

1マスの陣取り(Cランク相当)

問題文:

盤面の情報が与えられます。
現在プレイヤーのいるマスは '*' になっており、そのマスはプレイヤーの陣地です。
プレイヤーは現在の陣地から上下左右に 1 マス移動することで到達できるマスをプレイヤーの陣地にします。
プレイヤーの陣地を '*' にした盤面を出力してください。

入力される値:

H W
S_0
...
S_(H-1)

・ 1 行目では、盤面の行数 H , 列数 W が与えられます。
・ 続く H 行のうち i 行目 (0 ≦ i < H) には、盤面の i 行目の文字をまとめた文字列 S_i が与えられ、 S_i の j 文字目は、盤面の i 行目の j 列目に書かれている文字を表します。(0 ≦ j < W)

期待する出力:

操作後の盤面を H 行で出力してください。

条件:

すべてのテストケースにおいて、以下の条件をみたします。

・ 1 ≦ H, W ≦ 20
・ S は W 文字の文字列
・ S の各文字は '.' または '*'
・ '*' のマスは 1 つ

問題理解:
STEP1は、与えられた現在地の上下左右の1マスを陣地にするというシンプルな問題です。

この問題で標準入力で与えられる盤面の行数 H , 列数 W の値の取り方を覚えましょう。(標準入力について学べる講座はこちら

続いて、どこが現在地かを取得するために「*」の位置を特定します。

「*」を見つけたらその上下左右を「*」に置き換えます。ただし、盤面の外に出てしまう場合は何もしません。この処理を忘れると現在地が端の場合に範囲外エラーになってしまいます。

最後に置き換え後の盤面を出力できればOKです。

解法のポイント:
おそらくつまずきやすい、「*」に置き換える処理を少し見ておきましょう。(問題集では、コード提出後画面にて解答コード例全体を参照可能です。)

# Hが盤面の行数、Wが盤面の列数を示す
# x, yが現在地を示す

・・・
if s[y][x] == "*":
    if y > 0:
        s[y - 1][x] = "*"
    if y < H - 1:
        s[y + 1][x] = "*"
    if x > 0:
        s[y][x - 1] = "*"
    if x < W - 1:
        s[y][x + 1] = "*"

・・・

盤面上に「*」があったとき条件により4つの処理に分岐させています。たとえば、以下の部分では

    if y < H - 1:
        s[y + 1][x] = "*"

盤面の一番最後の行でなければ、現在地のひとつ下の行(列数は変わらず)を「*」に変えると処理しています。問題集のほうで公開している解法のポイントも参照し復習してみてください。

つづいてSTEP2もCランク相当の問題です。ほとんどSTEP1と同じですがひとつだけ条件が追加されました。「障害物(#)」のあるマスは陣地にできないというものです。

さきほどのコードを改良して解けるのでぜひチャレンジしてみてください。

陣取りの結末(Bランク相当)

STEP3のBランク相当の問題を解いてみます。STEP1、2の応用です。

問題文:

盤面の情報が与えられます。
現在プレイヤーのいるマスは '*' になっており、そのマスはプレイヤーの陣地です。
プレイヤーは次の操作をできなくなるまで続けます。

・ プレイヤーは現在の陣地から上下左右に 1 マス移動することで到達できるマスをプレイヤーの陣地にする。ただし障害物( '#' )のマスは陣地にできない。

操作を終えた後のプレイヤーの陣地を '*' にした盤面を出力してください。

入力される値:

H W
S_0
...
S_(H-1)

・ 1行目では、盤面の行数 H , 列数 W が与えられます。
・ 続く H 行のうち i 行目 (0 ≦ i < H) には、盤面の i 行目の文字をまとめた文字列 S_i が与えられ、 S_i の j 文字目は、盤面の i 行目の j 列目に書かれている文字を表します。(0 ≦ j < W)

期待する出力:

操作後の盤面を H 行で出力してください。

条件:

すべてのテストケースにおいて、以下の条件をみたします。

・ 1 ≦ H, W ≦ 20
・ S は W 文字の文字列
・ S の各文字は '.' または '*' または '#'
・ '*' のマスは 1 つ

問題理解:
さきほどは与えられた現在地の上下左右を陣地にする(ただし、障害物があるところは陣地にできない)という内容でした。

今度は与えられた現在地の上下左右を陣地にすることを繰り返して、陣地にできるところがなくなったら終了となります。

入出力例2の右下のマスのように障害物に囲まれて陣地にできないエリアもあります。

#入力例2
3 3
*.#
..#
##.

---

#出力例2
**#
**#
##.

盤面の端ではないかという判定に加え、「#(障害物)」ではないかつまり「.」であるかを同時に判定する必要があります。

解法のポイント:
「プレイヤーは現在の陣地から 1 マス移動することで到達できるマスをプレイヤーの陣地にする。」というヒントをもとに、この操作を繰り返すことで陣地の拡大を実装します。具体的には

プレイヤーのいるマスから1マス拡大 → 1 回目の拡大で新たに陣地になったマス 1 → 1 回目の拡大で新たに陣地になったマス 2 ....

という処理になります。このアルゴリズムを幅優先探索といい、FIFO(First In First Out)のデータ構造を使うとうまくいきます。「探索ってなに…?」という方は以下の記事で基本的な内容を説明していますので、よければごらんください。

paiza.hatenablog.com

問題集では図を使って解法のポイントを具体的に解説していますので、Bランク相当の問題が難しいなと感じた方はぜひ参考にしてみてください。

連結の判定(Aランク相当)

STEP4、5もBランク相当の問題です。それらをクリアし、準備がしっかりできたら最後にFINAL問題であるAランク相当の問題にチャレンジしてみましょう。

これまでと異なるのは、今回はプレイヤーがふたり交互に陣取りをし、最後の出力は勝者とその人が陣地としたマス数という点です。ただし、ここまでの考え方や書いたコードは使えそうです。

問題文:

A さんと B さんは次の操作を交互に繰り返すことで陣取りゲームをしようと考えました。 2 人の操作によって盤面が変化しなくなったらゲームを終了します。

・ 現在の陣地から上下左右に 1 マス移動することで到達できる、まだ誰の陣地でもない全てのマスを新たに陣地にする。ただし、障害物( # )のマスは陣地にできない。新たに陣地にできるマスが無い場合、何もしない。

盤面の情報と、先攻のプレイヤーの名前が与えられます。
盤面では、はじめに A さんのいるマスを 'A' , B さんのいるマスを 'B' で表します。
ゲーム終了時に A さん、 B さん、それぞれの陣地のマス数と勝った人の名前を出力してください。
なお、引き分けにはならないことが保証されています。

入力される値:

H W
N
S_0
...
S_(H-1)

・ 1 行目では、マップの行数 H , 列数 W が与えられます。
・ 2 行目では、先攻のプレイヤーの名前 N が与えられます。
・ 続く H 行のうち i 行目 (0 ≦ i < H) には、盤面の i 行目の文字をまとめた文字列 S_i が与えられ、 S_i の j 文字目は、盤面の i 行目の j 列目に書かれている文字を表します。(0 ≦ j < W)

期待する出力:

2 行の出力
二人のマス数の間には半角スペースを 1 つ出力してください。

A さんの陣地のマス数 B さんの陣地のマス数
勝者の名前

条件:

条件
すべてのテストケースにおいて、以下の条件をみたします。

・ 1 ≦ H, W ≦ 1000
・ N は 'A' か 'B'
・ S は W 文字の文字列
・ S の各文字は '.', '#', 'A', 'B'のいずれか
・ 'A' , 'B' のマスは1つ
・ 必ずゲームの勝者が決定する

解法のポイント:
操作自体はこれまで解いてきた問題とほとんど同じです。盤面の外にいかないようにする、障害物を避けるといった条件もそのままです。

ただし今回は、AさんとBさんふたりのスタート位置からの陣地拡大を考慮する必要があります。

キューを2つ用意して管理するか、1つのキューに先攻のスタート地点、後攻のスタート地点を順に入れて、STEP3でも出てきた幅優先探索を使って解くこともできます。

どのようにプレイヤーふたりの盤面での状態を管理しているのか、もしくは自分が解いてみた方法と違っている点はあるのかなど、ぜひ解答コード例も参照してみてください。

Aランクレベルアップメニューの問題集

この問題セットには、さきほど紹介した「陣取りゲーム」を含め8つの問題集を用意しています。現在はPython3とC++の解答コード例の参照が可能です。(下図は対応言語の一部です)

20210122205152

Aランク相当の問題に初めてチャレンジする場合、問題文も長く難しいと感じる方も多いので、まずはC~Bランク相当を自分で解けるようになるための問題集もあります。

問題セット一覧はこちらから

マップの判定・縦横

f:id:paiza:20210123014530j:plain

STEP: 1 盤面の情報取得(C)
STEP: 2 盤面の情報変更(C)
STEP: 3 マップの判定・横(C)
STEP: 4 マップの判定・縦(C)
FINAL問題: マップの判定・縦横(B)

座標系での向きの変わる移動

f:id:paiza:20210123014543j:plain

STEP: 1 マップからの座標取得(C)
STEP: 2 座標系での移動・方角(C)
STEP: 3 座標系での移動・向き(B)
STEP: 4 座標系での規則的な移動(B)
FINAL問題: 座標系での向きの変わる移動(B)

へび

f:id:paiza:20210123014551j:plain

STEP: 1 移動が可能かの判定・方角(B)
STEP: 2 移動が可能かの判定・方向(B)
STEP: 3 移動が可能かの判定・複数回の移動(B)
STEP: 4 移動が可能かの判定・幅のある移動(B)
STEP: 5 幅のある移動(B)
STEP: 6 時刻に伴う移動(A)
FINAL問題: へび(A)

陣取りゲーム

f:id:paiza:20210123014707j:plain

STEP: 1 1 マスの陣取り(C)
STEP: 2 1マスの陣取り2(C)
STEP: 3 陣取りの結末(B)
STEP: 4 陣取りの手間(B)
STEP: 5 陣取りのターン数(B)
FINAL問題: 陣取りゲーム(A)

いびつなリバーシ対戦

f:id:paiza:20210123112107j:plain

STEP: 1 裏返せる可能性(縦横)(C)
STEP: 2 リバーシの操作(縦横)(C)
STEP: 3 裏返せる可能性(斜め)(C)
STEP: 4 リバーシの操作(斜め)(C)
STEP: 5 リバーシの操作(C)
STEP: 6 いびつなひとりリバーシ(1ターン)(B)
STEP: 7 いびつなひとりリバーシ(B)
STEP: 8 いびつなリバーシ対戦(2人)(A)
FINAL問題: いびつなリバーシ対戦(A)

区間の積

f:id:paiza:20210123112113j:plain

STEP: 1 累積和の計算(C)
STEP: 2 区間和の計算(B)
STEP: 3 最短の区間(B)
STEP: 4 最長の区間(B)
STEP: 5 区間への足し算(A)
FINAL問題: 区間の積(A)

最大公約数

f:id:paiza:20210123112122j:plain

STEP: 1 規則的な数列の和(C)
STEP: 2 べき乗の計算(C)
STEP: 3 素数判定(C)
FINAL問題: 最大公約数(C)

連結の判定

f:id:paiza:20210123112129j:plain

STEP: 1 隣接行列(B)
STEP: 2 隣接リスト(B)
STEP: 3 有向グラフの隣接行列と隣接リスト(B)
STEP: 4 重みあり有向グラフの隣接行列と隣接リスト(B)
STEP: 5 一方通行(グラフ上の移動)(B)
STEP: 6 りんご拾い(情報を持ちながらの移動)(B)
FINAL問題: 連結の判定(A)

プログラミングの実力を測る「スキルチェック

レベルアップ問題集で難易度の高い問題の解答に自信がついてきたら、ぜひスキルチェックに挑戦してみてください!

スキルチェックの問題は、レベルアップ問題集と違って解答に時間制限があり、実行速度や解答時間も加味してスコアを出します。その点数によって上位のランクへアップするか、とどまるかの判定がされます。(ランクが下がることはありません)

詳しくはこちら
paizaのスキルチェック

まとめ

レベルアップ問題集で公開中の「Aランクレベルアップメニュー」についてご紹介しました。

Aランクの問題は問題文の理解はもちろん、複雑な条件をどのように整理して処理に落としこむかを考える力が必要になります。また、効率のよい計算方法やアルゴリズムを使って処理回数を減らす工夫が必要になることもあります。

はじめは難しく感じるかもしれませんが、数をこなしていくうちにだんだん力がついていきます。解答コード例や解説を見てつまづいた箇所はしっかり復習できるとよいですね。

なお、冒頭にも書いたとおりレベルアップ問題集の問題を解いたご自分のコードはSNSで開示したり、分からないところを相談したり教え合ったりしていただいて構いません。合わせて授業や研修で使用することも問題ありませんので、ぜひご活用ください。




これからプログラミング学習を始めたいという方には、paizaラーニングがおすすめです。Python、Java、C言語、C#、PHP、Ruby、SQL、JavaScript、HTML/CSSなど、プログラミング未経験者や初心者でも動画で学べる入門レッスンを公開しています。

Python入門編」「C#入門編」「ITエンジニアの就活準備編」といった人気講座も完全無料となっておりますので、プログラミングを学びたい方・ITエンジニアを目指したい方はぜひごらんください。

詳しくはこちら
paizaラーニング

*1:ただし、それらを閲覧するためには学習チケットが必要となります。チケットは毎日初回ログイン時に1枚付与され6枚まで所持できます。(有料会員の場合はチケットの消費なしで閲覧可能です)

paizaのおすすめコンテンツ

Webセキュリティ入門 ハッカー入門 Webセキュリティ講座がスタート!CVは内田真礼さん! Python✕AI 機械学習入門講座 CVに上坂すみれさんを起用!人気の機械学習講座を公開中!
paiza転職 paiza新卒 EN:TRY paizaラーニング Copyright Paiza, Inc, All rights reserved.