LoginSignup
1
0

More than 3 years have passed since last update.

@naaga0610

JOI 2020/21 一次予選 1回目 解説

Last updated at Posted at 2020-09-19

はじめに

以下の点にご留意ください。

  • これは麻布学園のパーソナルコンピュータ同好会(Twitter)での解説用に作成したものです。
  • 予選時間中に作成して、また部内で解説をスムーズにする為に作成した資料なので、誤字脱字や説明が雑な部分があります。
    • 【追記 9/20】 体裁を整えました。(読みやすくなってるといいな…)
  • コードは、C言語またはC++を使用しています。講座でC言語を教えているためです。全コードに対してCかC++かを明記しました。
  • まだプログラミングの勉強を始めたばかり(1ヶ月少し)の新入部員向けに作成した解説です。
  • ここに上げてるコードは全て実際に提出してACが出たコード(から余分な部分を省いたもの)です。参考にしていただけると幸いです。

A - 2 番目に大きい整数 (The Second Largest Integer)

問題文(そのまま)

$3$ つの整数 $A,B,C$ が与えられる．これらのうち $2$ 番目に大きい数を出力せよ．

解法

1. 場合分けで考えてみる

8通り? if文で分けるのは結構難しそうだけど考えてみる…

(表は大小関係のみを考え、大きい順に3,2,1としています)

A B C 答え
1 2 3 B
1 3 2 C
2 1 3 A
2 3 1 A
3 1 2 C
3 2 1 B

だけじゃない

・入力例2

1 3 3

同じ場合もある。全部可能性を列挙してあげると…

A B C 答え
1 2 3 B
1 3 2 C
2 1 3 A
2 3 1 A
3 1 2 C
3 2 1 B
1 1 1 A,B,C
1 1 2 A,B
1 2 1 A,C
2 1 1 B,C
1 2 2 B,C
2 1 2 A,C
2 2 1 A,B

流石に14通りの場合分けは辛いし、A,Bは同じだけどCはそれより小さいのなら…とかやってられない。

解説のために書きました。

回答 C

#include <stdio.h>

int main(){
    int a,b,c;
    scanf("%d %d %d", &a, &b, &c);
  if(a < b && b < c)  printf("%d", b);
  if(a < c && c < b)  printf("%d", c);
  if(b < a && a < c)  printf("%d", a);
  if(c < a && a < b)  printf("%d", a);
  if(b < c && c < a)  printf("%d", c);
  if(c < b && b < a)  printf("%d", b);

  if(a == b && b == c){
    printf("%d", a);
  }else{ //＊
    if(a == b) printf("%d", a);
    if(a == c) printf("%d", a);
    if(b == c) printf("%d", b);
  }
}
  • 上の表を読むと、AとBが一緒だったらCの大小は関係なくA,Bのどっちでも答えになるので、そこは少し省きましょう。
  • ＊部：else文を使いましょう。$A=B=C$の時に4回出力されて落ちます

自分も表をきちんと整理した上で1回WAを出してるし、場合分けも面倒…あと間違ってた時に気づけない。 そこで次の解法です。

2. 最大値を考える

現実的な解法です。最大値を計算し、最大値だった変数の値を0にして、改めて3つでもう1回比較する方法です。これなら、コードをコンパクトに書く事ができるはず…！

回答C

#include <stdio.h>

int main(){
    int a,b,c;
    scanf("%d %d %d", &a, &b, &c);


  // ＊1
  int max = a;
  if(max < b)   max = b;
  if(max < c)   max = c;
  // ＊1 ここまで

  // ＊2
  if(a == max)      a = 0;
  else if(b == max) b = 0;
  else if(c == max) c = 0;
  // ＊2 ここまで


  int sec = 0;
  if(sec < a)   sec = a;
  if(sec < b)   sec = b;
  if(sec < c)   sec = c;

  printf("%d\n", sec);
}
  • ＊1：ここでは最大値を探しています
  • ＊2：2番目の値を考えたいので、一番大きい値を消したい。ただ、a=b=cみたいな時や、a=b=2, c=1みたいな時に問題が起きるので、「もしまだ最大値が見つけられてないならー」みたいな気分でelseを使ってあげます。

3. 最大値最小値を求めて引く(自分のコード) C++

実際に自分が提出したコード(から余分な行を消したやつ)です。

回答 C++

#include <iostream>
#include <algorithm>
using namespace std;

signed main(){
    int a,b,c;
    cin >> a >> b >> c;
    int ma = max({a,b,c}); //＊
    int mi = min({a,b,c});
    cout << a + b + c - ma - mi << endl;
}
  • ＊：max()で最大値、min()で最小値を求める関数を実行してくれます。
    • 中1向けだとこの部分は以下みたいな実装をすればOKです。あとはa+b+cから最大値、最小値を引けば答えがでるね、という感じです。
 int max = a;
  if(max < b)   max = b;
  if(max < c)   max = c;

B - JOI ソート (JOI Sort)

問題概要

文字列 JIOIJO みたいなのを JJOOII みたいにJ, O, Iの順番に並べ替えてくださいという問題。

方針

正直解けた人の実装方針は全員同じだったんじゃないかな…?

  1. 文字列1文字1文字に着目して、J,O,Iの個数を全部カウントする。
  2. その後、Jの個数分J、その後O,Iの個数分O,I を出力。

【9/20 追記】
部内で解いた人はみんな結構ソートして書いてたらしいですね…ソートは中1にはまだ教えてないので、これから話していこうかなと思ってます。
この記事を読んでる外部の方々向けに、回答2として解説を載せていますのでそちらご覧ください。

回答 C

#include <stdio.h>

signed main(){
  int n;
  char s[101]; // ＊
  scanf("%d", &n);
  scanf("%s", s);

  int j,o,i;
  j = o = i = 0;

  for(int k=0; k<n; k++){
    if(s[k]=='J') j++;
    if(s[k]=='O') o++;
    if(s[k]=='I') i++;
  }

  for(int k=0; k<j; k++){
    printf("J");
  }

  for(int k=0; k<o; k++){
    printf("O");
  }

  for(int k=0; k<i; k++){
    printf("I");
  }
}
  • ＊：文字列を扱う時は必ず配列を文字数+1つ用意するのでした。今回は文字数が最大100文字なので、101個用意しましょう。配列の数より文字数が少ない分には問題ありません。

自分が提出したコード C++

#include <iostream>
#include <string>
using namespace std;
#define LOOP(i,N) for(int i=0;i<N;i++)

signed main(){
    int n;
    string s;
    cin >> n;
    cin >> s;
    int j,o,i;
    j = o = i = 0;
    LOOP(k,n){ //＊
      if(s[k]=='J')j++;
      if(s[k]=='O')o++;
      if(s[k]=='I')i++;
    }
    LOOP(k,j){ //＊
      cout << "J";
    }
    LOOP(k,o){ //＊
      cout << "O";
    }
    LOOP(k,i){ //＊
      cout << "I";
    }
}
  • ＊：for文で0からn-1まで回すという意味に自動的に置き換わる、みたいなやつです。4行目を参照。中1向け講座には後々登場します。

回答2 C++

#include <bits/stdc++.h>

using namespace std;

bool joi_sort(const char& a, const char& b) {
    if (a == 'J' && b == 'O' || a == 'J' && b == 'I')
        return true;
    if (a == 'O' && b == 'I')
      return true;
    return false;
}

int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;

  sort(s.begin(), s.end(), joi_sort);
  cout << s;
  return 0;
}

sort関数を用いてソートしちゃいます。sort関数は一つめに要素の先頭、２つめに要素の末尾を入れるとソートしてくれます。また、3つめに関数を指定してあげると関数に記述されたルールに従ってソートしてくれます。
ソートに関してのあれこれ(マージソート等)はまだ中1には教えていない範囲なので、今回はメインの解法として扱っていません。(あと自分がノータイムで思いついたのは方針に書いた方の解法だったのもあります…)

C - 共通要素 (Common Elements)

問題文がなんか難しい！
どうやら両方の要素を見つけるぽい…?というのを頑張って理解して、入出力例を見て問題概要を把握していきましょう。

概要

数列${A},{B}$があって、$A$ にも $B$ にも出現する数字を全部出力してね。

方針

なかなか難しい。1次予選は2問解ければいいから分からなくても全然問題はないです。

1~100番について、「値が存在するか」どうかの情報を持った配列を2つ用意します。

1つめの配列は、$a_i$番をtrueにします。
2つめの配列は、1つめの配列で$b_i$番がtrueならば2つめの$b_i$番をtrueにします。

あとは1番から100番までを全部調べて、2つめでtrueだったのを全部出力してあげればOK。
配列のこんな使い方は講座でやってなかったし、これを思いつくのは難しかったと思います。

回答 C

#include <stdio.h>

signed main(){
  int n,m;
  bool k[101]={}; //＊1
  scanf("%d %d", &n, &m);
  for(int i=0; i<n; i++){
    int a;
    scanf("%d", &a);
    k[a] = true; //*2
  }

  bool ans[101]={};
  for(int i=0; i<m; i++){
    int b;
    scanf("%d", &b);
    if(k[b] == true){
      ans[b] = true;
    }
  }
  for(int i=1; i<=100; i++){
    if(ans[i] == true){
      printf("%d\n", i);
    }
  }
}
  • ＊1：この1行に講座では解説していなかった事項が2つあったので説明します。
    • 1. bool型。0と1のみを扱う事ができる型です。覚えてなかったらint型で全部代用できます。
    • 2. {}での初期化。配列は宣言する段階でだけ、{}を使う事で全部の値を0にする事ができます。
  • ＊2：true, false について説明してなかったです。1,0と同じです。
  • 中2以上は、$a_i, b_i \leq 10^9$ でも大丈夫なコードを書けるようにしてください。
    • もしかしたらAPCCOJにあるかも。あとで探してみます。

あと問題文はちゃんと読みましょう。僕は最初、かぶってる数だけ出力すると思って実装して提出したのでWAしました……

1
0
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0