第3号~PG BATTLE

ERP・AI事業部の荻野・白鳥・高槻です。

今回の「SI News」の内容は、9/28(土)に開催された【PG BATTLE】についてです。

私達3人も、チームを組んで参加しました。

 

10/5(土)には、YouTubeLiveにて結果発表会が行われました。

皆さん、ご覧頂けましたでしょうか。

また、当社のYouTubeチャンネルでは、PG BATTLE全12問の解説動画が投稿されています。

AtCoder株式会社 高橋直大様が分かりやすく解説してくださっています。

今回【PG BATTLE】に参加していない方も、ロジックの考え方を知る良い機会になるので見る価値ありです。

 

今回で2回目の開催となった【PG BATTLE】。

第1回の参加数は  全260チーム 780名

第2回の参加数は… 全444チーム 1332名!

なんと参加者は、184チーム 552名の増加になりました。

これからますます盛り上がっていくこと間違いなしです。

 

白鳥
高校生以下の部から、48チームの参加があったことは驚きました。

私がプログラミングを勉強し始めたのは、高校卒業してからでしたからね。

 

荻野
かつおぶし問題の正答率を見て、驚愕しました。
正答率10%未満の問題もあり、本当に難しい問題が多いことが分かりました。

 

【PG BATTLE】では、ソースの提出や正答判定に、当社製品「TOPSIC」を利用しています。

普段は法人向けサービスとして、エンジニアの採用や教育に利用されているものです。

「TOPSIC」サイトのブログでは、

第1回大会「学生の部」優勝チームの皆様へのインタビュー記事。

PG BATTLE 2018 「学生の部」初代優勝者インタビュー

 

プログラミング教育の必修化についての記事。

なぜ「プログラミング教育」が必修化されるの?

 

など興味深い記事がありますので、新人ブログと合わせて読んでみてください。

 

私達3人は、今回の結果を受けて「PG BATTLE復習会」を実施しました。

ここからは、私達なりの【PG BATTLE】の解説をソースコードと共に紹介します。

言語はC#になります。

※ソースコードが見にくくなる可能性がある為、PCやタブレットを推奨します。

 

 

PGBattle2019「ましゅまろ」第2問:AtCoder

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace PGBATTLE2019_マシュマロ_Q2_AtCoder
{
  #region 問題文
  /*アルファベット大文字小文字のみを含む長さ7の文字列Sが与えられます。
  Sが AtCoder と等しい場合 Yes、そうではなく、かつ、大文字小文字の違いを除いて AtCoder と等しい場合 Maybe、
  どちらでもない場合 No と出力してください。
  制約:|S|=7でSはアルファベット大文字小文字のみを含む。*/
  #endregion
  
  class Program
  {
    static void Main(string[] args)
    {
      //入力値取得
      string input = Console.ReadLine();
      //模範解答設定
      string ans = "AtCoder";

      //出力パターンをif文で場合分け

      //完全一致の場合
      if (input.Equals(ans))
      {
        Console.WriteLine("Yes");
      }
      //大文字小文字の区別しないで一致の場合 *小文字に揃えて比較
      else if (input.ToLower() == ans.ToLower())
      {
        Console.WriteLine("Maybe");
      }
      //その他一致しない場合
      else
      {
        Console.WriteLine("No");
      }
    }
  }
}

 

 

PGBattle2019「せんべい」第3問:バレー・ボール

using System;
using System.Collections.Generic;
namespace cs {
  class Program {
    static void Main(string[] args) {
      var NM = Console.ReadLine().Split(' ');
      int N = int.Parse(NM[0]);
      int M = int.Parse(NM[1]);

      var g = new Queue<int>[M + 1];
      var dist = new int[N + 1];
      var Qr = new Queue<int>();
      var Qd = new Queue<int>();

      for (int i = 0; i <= N; i++)
        dist[i] = 4; 
for (int i = 0; i <= M; i++) g[i] = new Queue<int>(); for (int i = 0; i < M; i++) { var AB = Console.ReadLine().Split(' '); int A = int.Parse(AB[0]); int B = int.Parse(AB[1]); g[B].Enqueue(A); } int r = 0; int d = 0; Qr.Enqueue(r); Qd.Enqueue(d); while (Qr.Count != 0) { r = Qr.Dequeue(); d = Qd.Dequeue(); if(dist[r] < d) continue; dist[r] = d; foreach (int no in g[r]) { Qr.Enqueue(no); Qd.Enqueue(d + 1); } } for(int i = 1; i <= N; i++) { if(dist[i] <= 3) Console.WriteLine("Yes"); else Console.WriteLine("No"); } Console.ReadLine(); } } }

 

 

PGBattle2019「かつおぶし」第2問:着席

問題文

AtCorder鉄道の車両には、左右の扉に挟まれて 個の座席が連続して並んでいます。 これらの座席には左から順に1から の番号が振られています。

はじめ、座席には誰も座っていません。これから、この車両に 人の乗客が1人ずつ乗車します。 各乗客がどちらの扉から乗車するかは文字列 によって表され、 文字目がLなら番目の乗客は左の扉から乗車し、 番目が Rなら番目の乗客は右の扉から乗車します。

乗車した乗客は、次のように座る席を判断して座ります。

  • 人の座っている席と隣接しない空間が存在する場合、それらの席のうち乗車した扉から最も近い席に座る。
  • そうでない場合、乗車した扉から最も近い空席に座る。

それぞれの乗客が座る座席を求めてください。

制約

  • 1≤N≤10^5
  • |S|=N
  • の各文字はLまたはRである。

入力

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

N
S

出力

桁出力せよ。行目に、番目の乗客が座る座席の番号を出力すること。

入力例1

5
LRLLL

出力例1

1
5
3
2
4
  • 1番目の乗客は左の扉から乗車し、人の座っている席と臨席しない空席のうち最も左の扉に近い席である座席1に座ります。
  • 2番目の乗客は右の扉から乗車し、人の座っている席と臨席しない空席のうち最も右の扉に近い席である座席5に座ります。
  • 3番目の乗客は左の扉から乗車し、人の座っている席と臨席しない空席のうち最も左の扉に近い席である座席3に座ります。
  • 4番目の乗客は左の扉から乗車し、空席の家最も左の扉に近い席である座席2に座ります。
  • 5番目の乗客は左の扉から乗車し、空席の家最も左の扉に近い席である座席4に座ります。

入力例2

3
RRR

出力例2

3
1
2

解答コード

using System;
using System.IO;
using System.Collections.Generic;

namespace PGBattle02
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var s = Console.ReadLine();

            var l = 0;
            var r = n - 1;

            var hasUsed = new bool[n];
            var isPhase1 = true;

            var outputs = new List();

            Action sit = i =>
            {
                outputs.Add(i + 1);
                hasUsed[i] = true;
            };

            foreach (var passenger in s)
            {
                // Phase1: 人の座っている席と臨席しない空席が存在する
                if (isPhase1)
                {
                    // 左の扉から乗車
                    if (passenger == 'L')
                    {
                        sit(l);

                        l += 2;
                    }
                    // 右の扉から乗車
                    else
                    {
                        sit(r);

                        r -= 2;
                    }

                    // Phase1終了判定
                    if (l > r)
                    {
                        // l, rを初期化してPhase2へ
                        isPhase1 = false;
                        l = 0;
                        r = n - 1;
                    }
                }
                // Phase2: 人の座っている席と臨席しない空席が存在しない
                else
                {
                    // 左の扉から乗車
                    if (passenger == 'L')
                    {
                        // 左から空席までlを進める
                        while (hasUsed[l])
                        {
                            l++;
                        }

                        sit(l);
                    }
                    // 右の扉から乗車
                    else
                    {
                        // 右から空席までrを進める
                        while (hasUsed[r])
                        {
                            r--;
                        }

                        sit(r);
                    }
                }
            }

            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            outputs.ForEach(Console.WriteLine);
            Console.Out.Flush();
        }
    }
}

解説

この問題は入力から与えられた乗客ついてループを回し、一人ずつ着席させる問題です。 問題を簡単にするために、以下のようにPhase1とPhase2に分けて処理を記述しています。

  • Phase1: 人の座っている席と臨席しない空席が存在する
  • Phase2: 人の座っている席と臨席しない空席が存在しない

Phase1では、人の座っている席と臨席しない空席が存在するため、 左の扉から乗車した場合には最後に左の扉から乗車して着席した乗客の2つ隣の席に着席し、 右の扉から乗車した場合には最後に右の扉から乗車して着席した乗客の2つ隣の席に着席します。

ここでの最後に左の扉から乗車して着席した乗客の2つ隣の席最後に右の扉から乗車して着席した乗客の2つ隣の席l, rを利用することで実現しています。 l, rの初期値はそれぞれ0, n-1(nは座席数) で、一番左の席と右の席を表します。 左の扉から乗車した場合には座席lに着席し、次回の着席(2つ隣の席)のためにlを2増加させます。 右の扉から乗車した場合には座席rに着席し、次回の着席(2つ隣の席)のためにrを2増加させます。

Phase1の終了条件は(l > r)trueとなったときです。 l, rを再度初期化し、以降の着席処理はPhase2に移ります。

Phase2では、人の座っている席と臨席しない空席が存在しないため、単純に乗車した扉の側から一番近い位置に着席していきます。 左の扉から乗車した場合には座席lから最も近い空席に着席し、 左の扉から乗車した場合には座席rから最も近い空席に着席します。

最も近い空席は、l,rそれぞれを1ずつ増大ないし減少させて、1席ずつ空席かどうかを確認しています。 空席かどうかの情報はhasUsedに格納しており、これを利用します。

 

以上。

ABOUTこの記事をかいた人

白鳥 来希

よろしくお願いします。
学ぶこと、食べること、遊ぶこと。
この3つのことを続けていきたいと思っています。
好きな食べ物は紅生姜、趣味はカラオケ・ダーツ・ボウリング。