ABC1完erのためのAHC入門【解法と考察過程と実装付き】 by ABC2完er

Last updated at 2024-05-30Posted at 2023-09-14

※AtCoderのサービスを使用していること前提の記事です。

■伝えたいこと

・AHCは楽しい。
・AHCはアルゴリズムのレーティング灰色帯でも、考察やひらめきで得点がみるみる上がっていく。

■導入

アルゴリズムのコンテストは出てるけど、ヒューリスティックのコンテストは出てない人のうち、「AHCって、焼きなましとかビームサーチとか、難しいアルゴリズムを使ったりできないと提出さえできないんでしょ？」と思っている人はいませんか？

そんなことありません！
私は上記の技術は扱えませんが、毎回たのしくて仕方がありません。
また、AHC023で初めて「幅優先探索（BFS）」を実装しました！
AHCでもABCでも使える武器が増えて、興奮しています！

■この記事に書いてあること

2023-09-03(日) 10:00 ~ 2023-09-10(日) 20:00に開催された
「第10回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 023）」

の解法を思い付いていく流れ（実装付き）の例。

問題は事前に読んでおいてください。（むずかしいことをいう）

■私のAtCoderのレベル感

直近3回のAHCのレーティングは「1188●、1152●、1333●」でした。
直近3回のABCのレーティングは「249●（2完）、783●（3完）、294●（2完）」でした。
　　※2023/09/12当時の状況

■解法の目次

一番かんたんにACを取る解法：
　　①　何もしない。ただし0点。
　　　【難易度：０】0点
1個植える解法：
　　②　最初の作物だけ植える。
　　　【難易度：１】15,425点
　　③　最高得点になるように作物を1個植える。
　　　【難易度：２】99,775点
2個植える解法（考察あり）：
　　④　最初の2個、作物を植える。
　　　【難易度：３】32,050点
　　⑤　最高得点になるように、2個作物を植える。
　　　【難易度：６】183,000点（バグあり）
　　⑥　「⑤　最高得点になるように、2個作物を植える。」のバグを取る。
　　　【難易度：－】188,925点
一気にたくさん植える解法（考察なし：ひらめき）：
　　⑦　最初の作物を基準に、一気にたくさん植える。
　　　【難易度：３】824,025点
　　⑧　貪欲に、一気にたくさん植える。
　　　【難易度：４】1,217,300点
　　⑨　最高得点になるように、一気にたくさん植える。
　　　【難易度：５】977,275点（バグあり）
　　⑩　「⑨　最高得点になるように、一気にたくさん植える。」のバグを取る。
　　　【難易度：－】1,288,700点

~~２つの解法のいいとこ取りをするテクニック：~~
　　思ったよりも記事作成に時間が掛かるため、このテクニック記載は中止。

※解法別に難易度を推測しました。
「レーティング÷４０＝難易度」くらいかな？　ものすごく雑な推測です。
※各解法の章には、提出した際のレーティングを記載しました。
※一部の解法の章には、実装が似てるかも知れないABCの問題も記載しました。

疑問：
もしかして、Qiitaに目次の項目はいらない？

■解法

①　何もしない。ただし0点。

得点　　　　：－
レーティング：328　●

AHCは、　0　を出力するだけでACできることがある。

これだけで得点が1点以上（用語「正の得点」）になることもあります。
AHC023では、得点なしでした。残念。

しーげんご.c

#include<stdio.h>
int main(void)
{
  puts("0");      //植える作物の総数
  return 0;
}

しーぷらぷら.cpp

#include<iostream>
int main(void)
{
  std::cout << "0" << std::endl;//植える作物の総数
  return 0;
}

ぱいそん.py

print(0);        #植える作物の総数

Visualizer　Seed0のスコア　：　0点

次は→？
　　とりあえず1個植えてみよう！　＝　②へ

②　最初の作物だけ植える。

得点　　　　：15,425点（暫定50ケース）
レーティング：663　●

いきなり最終形態を目指すのではなく、少しずつ進めることが大切。

考察：
問題文をざっくりまとめてみると、きっとこうだと思う。
１．土地は、迷路みたいになっている。
２．土地の区画を上下左右にだけ動ける。
３．作物を植えたら、収穫するまでその区画は通れない。
４．作物は、早めに植えてもよい。
５．作物の収穫時期は、絶対守らなければならない。

ということは、作物を2個以上植える場合は、入り口からみた「手前」と「奥」のことを考える必要がありそう。

じゃあ、作物1個だけならどこに植えてもよさそう！

作物1個植えるのに必要な入力を見てみる。

入力	要/不要	理由
T	不要	初月に植えるため
H	不要	最北端に植えるため
W	不要	最西端に植えるため
i0	不要	手前と奥のことは考えないため
h	不要	手前と奥のことは考えないため
v	不要	手前と奥のことは考えないため
K	不要	1個しか植えないため
S	不要	初月しか植えないため
D	不要	選んだ作物の情報に任せるため

よって、入力は受け取らない！つよきのしせい！

出力は？

出力	固定/任意	出力の内容
M	固定	1個
k	固定	最初の作物
i	固定	最北端
j	固定	最西端
s	固定	初月

何もかもを固定！わがみちをゆく。

実装：

しーげんご.c

#include<stdio.h>
int main(void)
{
  puts("1");      //植える作物の総数
  puts("1 0 0 1");//入力で与えられる(はずの)1個目の作物を、座標(0,0)に植える（1ヵ月目）
  return 0;
}

しーぷらぷら.cpp

#include<iostream>
int main(void)
{
  std::cout << "1" << std::endl;      //植える作物の総数
  std::cout << "1 0 0 1" << std::endl;//入力で与えられる(はずの)1個目の作物を、座標(0,0)に植える（1ヵ月目）
  return 0;
}

ぱいそん.py

print(1);         #植える作物の総数
print(1, 0, 0, 1);#入力で与えられる(はずの)1個目の作物を、座標(0,0)に植える（1ヵ月目）

Visualizer　Seed0のスコア　：　325点

次は→？
　　今の作物の数で、最高得点を目指したい　＝　③へ
　　植える作物の数を増やしたい　＝　いくつ増やす→？
　　　　　　コツコツ派だから１個増やしたい　＝　④へ
　　　　　　よくばり派だからたくさん増やしたい　＝　⑦へ

③　最高得点になるように作物を1個植える。

得点　　　　：99,775点（暫定50ケース）
レーティング：696　●

各作物の得点　：　d - s + 1

これが解ければ理解可能
ABC275　A問題：

これが解ければ楽勝
ABC313　A問題：

得点の計算式：
d - s - 1
収穫月 − 植えなきゃいけない期限の月(※) ＋１

※早めに植えても、得点は上がらない

すべての作物の中から、最高得点となる作物を見つける方法：
勝ち抜き戦のような方式を取ってみる。
2個の作物の得点を比較して、小さい方は脱落。
勝ち残った作物と、次の作物で比較して、小さい方は脱落。
それをすべての作物を比較し終わるまで続ける。
よさそう。

作物1個の最大得点を求めるのに必要な入力を見てみる。

入力	要/不要	理由
T	不要	初月に植えるため
H	不要	最北端に植えるため
W	不要	最西端に植えるため
i0	不要	手前と奥のことは考えないため
h	不要	手前と奥のことは考えないため
v	不要	手前と奥のことは考えないため
K	必要★	1個しか植えないが、すべての作物の得点計算をするため
S	必要★	得点計算のため
D	必要★	得点計算のため

不要な入力は読み飛ばしちゃう。
すべての作物の得点計算をするために、for文の登場です。

出力は？

出力	固定/任意	出力の内容
M	固定	1個
k	任意	最高得点の作物の番号
i	固定	最北端
j	固定	最西端
s	固定	初月

少しだけにゅうわになりました。

実装：

しーげんご.c

#include<stdio.h>
int main(void)
{
  //最初の1行は読み飛ばす
  int t, h, w, i0;
  scanf("%d %d %d %d\n", &t, &h, &w, &i0);
  //39行分は読み飛ばす
  char dust[20+1];
  for(int i=0; i<39; i++)
  {
    scanf("%s\n", dust);
  }
  int k;
  scanf("%d\n", &k);//作物の総数
  
  //全作物の情報を受け取りながら、最高得点となる作物を探す
  int s, d, point;
  int point_max=0/*最高得点*/, point_max_i/*最高得点である作物の番号*/;
  for(int i=0; i<k; i++)
  {
    scanf("%d %d\n", &s, &d);
    point = d-s+1;
    if(point_max <= point)
    {
      //最高得点である
      point_max   = point;
      point_max_i = i+1;
    }
  }
  
  //出力
  puts("1");
  printf("%d 0 0 1\n", point_max_i);//最高得点の作物を座標(0,0)に植える（1ヵ月目）
  return 0;
}

しーぷらぷら.cpp

#include<iostream>
#include<string>
int main(void)
{
  //最初の1行は読み飛ばす
  int t, h, w, i0;
  std::cin >> t >> h >> w >> i0;
  //39行分は読み飛ばす
  std::string dust;
  for(int i=0; i<39; i++)
  {
    std::cin >> dust;
  }
  int k;
  std::cin >> k;//作物の総数
  
  //全作物の情報を受け取りながら、最高得点となる作物を探す
  int s, d, point;
  int point_max=0/*最高得点*/, point_max_i/*最高得点である作物の番号*/;
  for(int i=0; i<k; i++)
  {
    std::cin >> s >> d;
    point = d-s+1;
    if(point_max <= point)
    {
      //最高得点である
      point_max   = point;
      point_max_i = i+1;
    }
  }
  
  //出力
  std::cout << 1 << std::endl;
  std::cout << point_max_i << " 0 0 1" << std::endl;//最高得点の作物を座標(0,0)に植える（1ヵ月目）
  return 0;
}

ぱいそん.py

#注意：私はPythonに詳しくないため、Pythonが初のプログラミング言語である人の書き方がわかりません。
#      Cっぽい書き方になりますが、考え方は一緒なのでご了承ください。

#最初の1行(4要素)は読み飛ばす
t,h,w,i0=map(int, input().split())

#39行分は読み飛ばす
for _ in range(0, 39):
  input()

k = int(input())
point_max = 0
#全作物の情報を受け取りながら、最高得点となる作物を探す
for i in range(0, k):
  s,d=map(int, input().split())
  point = d - s + 1
  if point_max <= point:
    #最高得点である
    point_max = point
    point_max_i = i+1

#出力
print(1);
print(point_max_i, 0, 0, 1);#最高得点の作物を座標(0,0)に植える（1ヵ月目）

Visualizer　Seed0のスコア　：　1900点

次は→？
　　考察の解法に進みたい　＝　④へ
　　ひらめきの解法に進みたい　＝　⑦へ

④　最初の2個、作物を植える。

得点　　　　：32,050点（暫定50ケース）
レーティング：600後半　●

考察：どんな条件でも、入り口からの手前と奥が決まる座標は存在するか？

考察：
どんな条件でも「作物1が、入り口からみて手前の座標に植えられている」と「作物2が、入り口からみて奥の座標に植えられている」となる植え方が存在するなら、その座標を固定で出力すれば解ける。
最強の座標がないかを、探そうとしています。

20×20の土地を考えるのは、さすがに人間にはむずかしい。
なので、3×2の土地で考えてみます。

あ～ぬ：水路のありえそうな27パターン
Ⅰ～Ⅲ：入り口の全3パターン
ア～ホ：植える座標（手前（①）と奥（②））の全30パターン

やろうとしていること：
作物をア～ホの座標で、手前（①）と奥（②）に固定した場合、どんな水路パターン（あ～ぬ）でも、どんな入り口パターン（Ⅰ～Ⅲ）でも、成り立つ組合せがあるか？
そうです。全探索です。

やろうとしていることのパターン数：
27×3×30＝2430パターン
手動だと多い！

確認するパターンを減らす案１：
ⅠとⅢは、線対称なので、どちらか一方を確認すればもう一方は確認を省略できる！採用。
27×2×30＝1620パターン
まだ多い！

確認するパターンを減らす案２：
Ⅱも線対称だけど、確認したパターンかどうかを考えるのも大変なので省略しないことにする。不採用。

確認するパターンを減らす案３：
ア～ホの視点で、Ⅰ～Ⅲとあ～ぬの組合せのうち1個でもNGがあったら、もうOKにはならないので打ち切ってよい。採用。
ここまで減らせばいけそう！

目的：
どんな条件でも「作物1が、入り口からみて手前の座標に植えられている」と「作物2が、入り口からみて奥の座標に植えられている」となる植え方が存在するか確認したい。

全探索の方針：
ア～ホの視点で、Ⅰ～Ⅲとあ～ぬの組合せのうち1個でもNGがあったら、もうOKにはならないので打ち切る。

えっさ、ほいさ。

結果：
アの視点で、全パターンを確認する。
もしもすべてOKだったら、アの植え方が最強の植え方！

残念、29パターン目がNGでした。

懲りずに続けましょう。
NGになったパターンだけ表示します。

なかった！

本当にないのか、もっと考察：
入り口の座標は分かっているので、入り口の目の前に①を植えれば、②はどこに植えても奥である。
当たり前だったかも？

奥(②)の作物をどこに植えるか？：
Ⅰのパターンで②を入り口の北に植えることはできない。
Ⅲのパターンで②を入り口の南に植えることはできない。
②を入り口の東に植えれば、ⅠⅡⅢどのパターンでも植えることができる。

やったー！

以上のことを踏まえて、入力/出力の要/不要を考えてみる。
長かったっ！

作物2個の手前と奥を求めるのに必要な入力を見てみる。

入力	要/不要	理由
T	不要	初月に植えるため
H	不要	入り口と同じ南北の座標に植えるため
W	不要	最西端と最西端の東隣りに植えるため
i0	必要★	考察の結果、入り口の南北の座標が欲しいため
h	不要	考えなくていいことは考察済みなので不要
v	不要	考えなくていいことは考察済みなので不要
K	不要	必要な情報は2個だけのため
S	不要	初月しか植えないため
D	必要★	手前/奥の情報が欲しいため

i0を必要とするのは初！うきうきしますね。

出力は？

出力	固定/任意	出力の内容
M	固定	2個
k	任意	1→2、または、2→1の順番のどちらか
i	任意	入り口と同じ南北の座標
j	任意	最西端→最西端の東隣り
s	固定	初月

なんだか難しそうな言い回し、、、
実装で確認してね！

実装：

しーげんご.c

#include<stdio.h>
int main(void)
{
  //入り口の座標だけ使用する。他は使用しない。
  int t, h, w, i0/*入り口の座標(南北の座標)*/;
  scanf("%d %d %d %d\n", &t, &h, &w, &i0);
  //39行分は読み飛ばす
  char dust[20+1];
  for(int i=0; i<39; i++)
  {
    scanf("%s\n", dust);
  }
  int k;
  scanf("%d\n", &k);//作物の総数
  
  //作物1の情報を受け取る
  int s1, d1;
  scanf("%d %d\n", &s1, &d1);
  //作物2の情報を受け取る
  int s2, d2;
  scanf("%d %d\n", &s2, &d2);
  
  //収穫時期が早い方を入り口から見て手前、遅い方を入り口から見て奥に植える
  puts("2");
  if(d1 < d2)
  {
    //作物1が手前、作物2が奥
    printf("1 %d 0 1\n", i0);//手前
    printf("2 %d 1 1\n", i0);//奥
  }
  else
  {
    //作物2が手前、作物1が奥
    printf("2 %d 0 1\n", i0);//手前
    printf("1 %d 1 1\n", i0);//奥
  }
  return 0;
}

しーぷらぷら.cpp

#include<iostream>
#include<string>
int main(void)
{
  //最初の1行は読み飛ばす
  int t, h, w, i0;
  std::cin >> t >> h >> w >> i0;
  //39行分は読み飛ばす
  std::string dust;
  for(int i=0; i<39; i++)
  {
    std::cin >> dust;
  }
  int k;
  std::cin >> k;//作物の総数
  
  //作物1の情報を受け取る
  int s1, d1;
  std::cin >> s1 >> d1;
  //作物2の情報を受け取る
  int s2, d2;
  std::cin >> s2 >> d2;
  
  //収穫時期が早い方を入り口から見て手前、遅い方を入り口から見て奥に植える
  std::cout << 2 << std::endl;
  if(d1 < d2)
  {
    //作物1が手前、作物2が奥
    std::cout << "1 " << i0 << " 0 1" << std::endl;//手前
    std::cout << "2 " << i0 << " 1 1" << std::endl;//奥
  }
  else
  {
    //作物2が手前、作物1が奥
    std::cout << "2 " << i0 << " 0 1" << std::endl;//手前
    std::cout << "1 " << i0 << " 1 1" << std::endl;//奥
  }
  return 0;
}

ぱいそん.py

#注意：私はPythonに詳しくないため、Pythonが初のプログラミング言語である人の書き方がわかりません。
#      Cっぽい書き方になりますが、考え方は一緒なのでご了承ください。

#入り口の座標(南北の座標)だけ使用する。他は使用しない。
t,h,w,i0=map(int, input().split())

#39行分は読み飛ばす
for _ in range(0, 39):
  input()

k = int(input())#作物の総数

#作物1の情報を受け取る
s1,d1=map(int, input().split())
#作物2の情報を受け取る
s2,d2=map(int, input().split())

#収穫時期が早い方を入り口から見て手前、遅い方を入り口から見て奥に植える
print(2)
if d1 < d2:
  #作物1が手前、作物2が奥
  print(1, i0, 0, 1)#手前
  print(2, i0, 1, 1)#奥
else:
  #作物2が手前、作物1が奥
  print(2, i0, 0, 1)#手前
  print(1, i0, 1, 1)#奥

Visualizer　Seed0のスコア　：　525点

次は→？
　　今の作物の数で、最高得点を目指したい　＝　⑤へ
　　なるべく楽な実装で、植える作物の数をもっともっと増やしたい　＝　⑦へ

⑤　最高得点になるように、2個作物を植える。

得点　　　　：183,000点（暫定50ケース）
レーティング：800前半　●

得点の合計が最大となる作物を2個選ぶ。

これが解ければ理解可能
ABC213　B問題：

これが解ければ楽勝
ABC252　B問題：

「③　最高得点になるように作物を1個植える。」を振り返る：
2個の作物の得点を比較して、低得点な作物は読み飛ばした。
最後まで残っていた作物が、最高得点な作物である。
そんなデスゲームを主催しました。

2番目に得点の高い作物とは：
デスゲームで負けた作物が、その時点の2番目に得点の高い作物なのではないだろうか？
１度負けても生き残れるけど、次はないものと知る。

作物2個の最大得点を求めるのに必要な入力を見てみる。

入力	要/不要	理由
T	不要	初月に植えるため
H	不要	入り口と同じ南北の座標に植えるため
W	不要	最西端と最西端の東隣りに植えるため
i0	必要★	④の考察の結果、入り口の南北の座標が欲しいため
h	不要	考えなくていいことは、④で考察済みなので不要
v	不要	考えなくていいことは、④で考察済みなので不要
K	必要★	2個しか植えないが、すべての作物の得点計算をするため
S	必要★	得点計算のため
D	必要★	得点計算のため。手前/奥の情報が欲しいため

解法③と解法④の合わせ技です。

出力は？

出力	固定/任意	出力の内容
M	固定	2個
k	任意	最高得点の作物の番号→2番目得点の作物の番号、または、最高得点の作物の番号→2番目得点の作物の番号、の順番のどちらか
i	任意	入り口と同じ南北の座標
j	任意	最西端→最西端の東隣り
s	固定	初月

そして、実装へ。

実装例：
後述しますが、この実装にはバグがあります。
※考えたとおりではあるが、最高得点という目的に対して中途半端な結果となっている。

しーげんご.c

#include<stdio.h>
int main(void)
{
  //入り口の座標だけ使用する。他は使用しない。
  int t, h, w, i0/*入り口の座標(南北の座標)*/;
  scanf("%d %d %d %d\n", &t, &h, &w, &i0);
  //39行分は読み飛ばす
  char dust[20+1];
  for(int i=0; i<39; i++)
  {
    scanf("%s\n", dust);
  }
  int k;
  scanf("%d\n", &k);//作物の総数
  
  //全作物の情報を受け取りながら、最高得点と2番目得点となる作物を探す
  int s, d, point;
  int point_max1=0/*作物の最高得点*/, point_max1_i=0/*最高得点である作物の番号(0=未設定)*/,  point_max1_d=0/*最高得点である作物の収穫時期(0=未設定)*/;
  int point_max2  /*作物の2番目得点*/, point_max2_i=0/*2番目得点である作物の番号(0=未設定)*/, point_max2_d=0/*2番目得点である作物の収穫時期(0=未設定)*/;
  for(int i=0; i<k; i++)
  {
    scanf("%d %d\n", &s, &d);
    point = d-s+1;
    if(point_max1 <= point)
    {
      //最高得点である
      //最高得点だったものは2番目に降格
      point_max2   = point_max1;
      point_max2_i = point_max1_i;
      point_max2_d = point_max1_d;
      //最高得点を更新
      point_max1   = point;
      point_max1_i = i+1;
      point_max1_d = d;
    }
  }
  
  //収穫時期が早い方を入り口から見て手前、遅い方を入り口から見て奥に植える
  puts("2");
  if(point_max1_d < point_max2_d)
  {
    //作物1が手前、作物2が奥
    printf("%d %d 0 1\n", point_max1_i, i0);//手前
    printf("%d %d 1 1\n", point_max2_i, i0);//奥
  }
  else
  {
    //作物2が手前、作物1が奥
    printf("%d %d 0 1\n", point_max2_i, i0);//手前
    printf("%d %d 1 1\n", point_max1_i, i0);//奥
  }
  return 0;
}

しーぷらぷら.cpp

#include<iostream>
#include<string>
int main(void)
{
  //入り口の座標だけ使用する。他は使用しない。
  int t, h, w, i0/*入り口の座標(南北の座標)*/;
  std::cin >> t >> h >> w >> i0;
  //39行分は読み飛ばす
  std::string dust;
  for(int i=0; i<39; i++)
  {
    std::cin >> dust;
  }
  int k;
  std::cin >> k;//作物の総数
  
  //全作物の情報を受け取りながら、最高得点となる作物を探す
  int s, d, point;
  int point_max1=0/*作物の最高得点*/, point_max1_i=0/*最高得点である作物の番号(0=未設定)*/,  point_max1_d=0/*最高得点である作物の収穫時期(0=未設定)*/;
  int point_max2=0/*作物の2番目得点*/, point_max2_i=0/*2番目得点である作物の番号(0=未設定)*/, point_max2_d=0/*2番目得点である作物の収穫時期(0=未設定)*/;
  for(int i=0; i<k; i++)
  {
    std::cin >> s >> d;
    point = d-s+1;
    if(point_max1 <= point)
    {
      //最高得点である
      //最高得点だったものは2番目に降格
      point_max2   = point_max1;
      point_max2_i = point_max1_i;
      point_max2_d = point_max1_d;
      //最高得点を更新
      point_max1   = point;
      point_max1_i = i+1;
      point_max1_d = d;
    }
  }
  
  //出力
  std::cout << 2 << std::endl;
  if(point_max1_d < point_max2_d)
  {
    //作物1が手前、作物2が奥
    std::cout << point_max1_i << " " << i0 << " 0 1" << std::endl;//手前
    std::cout << point_max2_i << " " << i0 << " 1 1" << std::endl;//奥
  }
  else
  {
    //作物2が手前、作物1が奥
    std::cout << point_max2_i << " " << i0 << " 0 1" << std::endl;//手前
    std::cout << point_max1_i << " " << i0 << " 1 1" << std::endl;//奥
  }
  return 0;
}

ぱいそん.py

#注意：私はPythonに詳しくないため、Pythonが初のプログラミング言語である人の書き方がわかりません。
#      Cっぽい書き方になりますが、考え方は一緒なのでご了承ください。

#入り口の座標(南北の座標)だけ使用する。他は使用しない。
t,h,w,i0=map(int, input().split())

#39行分は読み飛ばす
for _ in range(0, 39):
  input()

k = int(input())#作物の総数

#全作物の情報を受け取りながら、最高得点と2番目得点となる作物を探す
point_max1 = 0   #作物の最高得点
point_max1_i = 0 #最高得点である作物の番号(0=未設定)
point_max1_d = 0 #最高得点である作物の収穫時期(0=未設定)
for i in range(0, k):
  s,d=map(int, input().split())
  point = d-s+1
  if point_max1 <= point:
    #最高得点である
    #最高得点だったものは2番目に降格
    point_max2   = point_max1
    point_max2_i = point_max1_i
    point_max2_d = point_max1_d
    #最高得点を更新
    point_max1   = point
    point_max1_i = i+1
    point_max1_d = d

#収穫時期が早い方を入り口から見て手前、遅い方を入り口から見て奥に植える
print(2)
if point_max1_d < point_max2_d:
  #作物1が手前、作物2が奥
  print(point_max1_i, i0, 0, 1)#手前
  print(point_max2_i, i0, 1, 1)#奥
else:
  #作物2が手前、作物1が奥
  print(point_max2_i, i0, 0, 1)#手前
  print(point_max1_i, i0, 1, 1)#奥

Visualizer　Seed0のスコア　：　3700点

次は→？
　　バグを取り除きたい　＝　⑥へ
　　ひらめきの解法に進みたい　＝　⑦へ

⑥　「⑤　最高得点になるように、2個作物を植える。」のバグを取る。

得点　　　　：188,925点（暫定50ケース）
レーティング：800前半　●

バグは出るもの。
最低でも、問題に取り組んでいる時間の3割はデバッグに消えるものだと思おう。

バグの概要：
最高得点を更新しないと、2番目得点が更新されない。

バグを再現する入力：
100 20 20 10
※2行目からの39行分は省略
3
1 2
1 100
1 99

期待する動作：
[作物1]と[作物2]を比較　→　[作物2]の方が得点が高い
●結果:最高得点=作物2(100点)、2番目得点=作物1(2点)
次の作物と比較
[最高得点の作物2]と[作物3]を比較　→　[最高得点の作物2]の方が得点が高い
[2番目得点の作物1]と[作物3]を比較　→　[作物3]の方が得点が高い
●結果:最高得点=作物2(100点)、2番目得点=作物3(99点)
比較完了！

最終結果	作物の番号	得点
1st	2	100点
2nd	3	99点
3rd	1	2点

期待する出力：
2
3 10 0 1
2 10 1 1
※最終結果のテーブルと順番が異なるのは、収穫時期による手前/奥の違いのため。

実際の動作：
[作物1]と[作物2]を比較　→　[作物2]の方が得点が高い
●結果:最高得点=作物2(100点)、2番目得点=作物1(2点)
次の作物と比較
[最高得点の作物2]と[作物3]を比較　→　[最高得点の作物2]の方が得点が高い
●結果:最高得点=作物2(100点)、2番目得点=作物1(2点)
比較完了！

最終結果	作物の番号	得点
1st	2	100点
2nd	1	2点
3nd	3	99点

実際の出力：
2
1 10 0 1
2 10 1 1
※最終結果のテーブルと順番が異なるのは、収穫時期による手前/奥の違いのため。

期待と実際の結果は、なにが異なっているか：
2番目の作物の得点が、期待は99点なのに、実際は2点。

期待と実際の動作は、なにが異なっているか：
[2番目得点の作物]と[次の作物]を比較する、いわゆる敗者復活戦をしていない。

足りないコードを書こう。

修正例：

ついかしたこーど.c

    else if(point_max2 <= point)
    {
      //最高得点未満だけど、2番目得点以上である
      //2番目得点を更新
      point_max2   = point;
      point_max2_i = i+1;
      point_max2_d = d;
    }
    else
    {
      //2番目得点未満なので得点の更新なし
    }

実装例：

しーげんご.c

#include<stdio.h>
int main(void)
{
  //入り口の座標だけ使用する。他は使用しない。
  int t, h, w, i0/*入り口の座標(南北の座標)*/;
  scanf("%d %d %d %d\n", &t, &h, &w, &i0);
  //39行分は読み飛ばす
  char dust[20+1];
  for(int i=0; i<39; i++)
  {
    scanf("%s\n", dust);
  }
  int k;
  scanf("%d\n", &k);//作物の総数
  
  //全作物の情報を受け取りながら、最高得点となる作物を探す
  int s, d, point;
  int point_max1=0/*作物の最高得点*/, point_max1_i=0/*最高得点である作物の番号(0=未設定)*/,  point_max1_d=0/*最高得点である作物の収穫時期(0=未設定)*/;
  int point_max2  /*作物の2番目得点*/, point_max2_i=0/*2番目得点である作物の番号(0=未設定)*/, point_max2_d=0/*最高得点である作物の収穫時期(0=未設定)*/;
  for(int i=0; i<k; i++)
  {
    scanf("%d %d\n", &s, &d);
    point = d-s+1;
    if(point_max1 <= point)
    {
      //最高得点である
      //最高得点だったものは2番目に降格
      point_max2   = point_max1;
      point_max2_i = point_max1_i;
      point_max2_d = point_max1_d;
      //最高得点を更新
      point_max1   = point;
      point_max1_i = i+1;
      point_max1_d = d;
    }
    else if(point_max2 <= point)
    {
      //最高得点未満だけど、2番目得点以上である
      //2番目得点を更新
      point_max2   = point;
      point_max2_i = i+1;
      point_max2_d = d;
    }
    else
    {
      //2番目得点未満なので得点の更新なし
    }
  }
  
  //収穫時期が早い方を入り口から見て手前、遅い方を入り口から見て奥に植える
  puts("2");
  if(point_max1_d < point_max2_d)
  {
    //作物1が手前、作物2が奥
    printf("%d %d 0 1\n", point_max1_i, i0);//手前
    printf("%d %d 1 1\n", point_max2_i, i0);//奥
  }
  else
  {
    //作物2が手前、作物1が奥
    printf("%d %d 0 1\n", point_max2_i, i0);//手前
    printf("%d %d 1 1\n", point_max1_i, i0);//奥
  }
  return 0;
}

しーぷらぷら.cpp

#include<iostream>
#include<string>
int main(void)
{
  //最初の1行は読み飛ばす
  int t, h, w, i0/*入り口の座標(南北の座標)*/;
  std::cin >> t >> h >> w >> i0;
  //39行分は読み飛ばす
  std::string dust;
  for(int i=0; i<39; i++)
  {
    std::cin >> dust;
  }
  int k;
  std::cin >> k;//作物の総数
  
  //全作物の情報を受け取りながら、最高得点となる作物を探す
  int s, d, point;
  int point_max1=0/*作物の最高得点*/, point_max1_i=0/*最高得点である作物の番号(0=未設定)*/,  point_max1_d=0/*最高得点である作物の収穫時期(0=未設定)*/;
  int point_max2=0/*作物の2番目得点*/, point_max2_i=0/*2番目得点である作物の番号(0=未設定)*/, point_max2_d=0/*2番目得点である作物の収穫時期(0=未設定)*/;
  for(int i=0; i<k; i++)
  {
    std::cin >> s >> d;
    point = d-s+1;
    if(point_max1 <= point)
    {
      //最高得点である
      //最高得点だったものは2番目に降格
      point_max2   = point_max1;
      point_max2_i = point_max1_i;
      point_max2_d = point_max1_d;
      //最高得点を更新
      point_max1   = point;
      point_max1_i = i+1;
      point_max1_d = d;
    }
    else if(point_max2 <= point)
    {
      //最高得点未満だけど、2番目得点以上である
      //2番目得点を更新
      point_max2   = point;
      point_max2_i = i+1;
      point_max2_d = d;
    }
    else
    {
      //2番目得点未満なので得点の更新なし
    }
  }
  
  //出力
  std::cout << 2 << std::endl;
  if(point_max1_d < point_max2_d)
  {
    //作物1が手前、作物2が奥
    std::cout << point_max1_i << " " << i0 << " 0 1" << std::endl;//手前
    std::cout << point_max2_i << " " << i0 << " 1 1" << std::endl;//奥
  }
  else
  {
    //作物2が手前、作物1が奥
    std::cout << point_max2_i << " " << i0 << " 0 1" << std::endl;//手前
    std::cout << point_max1_i << " " << i0 << " 1 1" << std::endl;//奥
  }
  return 0;
}

ぱいそん.py

#注意：私はPythonに詳しくないため、Pythonが初のプログラミング言語である人の書き方がわかりません。
#      Cっぽい書き方になりますが、考え方は一緒なのでご了承ください。

#入り口の座標(南北の座標)だけ使用する。他は使用しない。
t,h,w,i0=map(int, input().split())

#39行分は読み飛ばす
for _ in range(0, 39):
  input()

k = int(input())#作物の総数

#全作物の情報を受け取りながら、最高得点と2番目得点となる作物を探す
point_max1 = 0   #作物の最高得点
point_max1_i = 0 #最高得点である作物の番号(0=未設定)
point_max1_d = 0 #最高得点である作物の収穫時期(0=未設定)
for i in range(0, k):
  s,d=map(int, input().split())
  point = d-s+1
  if point_max1 <= point:
    #最高得点である
    #最高得点だったものは2番目に降格
    point_max2   = point_max1
    point_max2_i = point_max1_i
    point_max2_d = point_max1_d
    #最高得点を更新
    point_max1   = point
    point_max1_i = i+1
    point_max1_d = d
  elif point_max2 <= point:
    #最高得点未満だけど、2番目得点以上である
    #2番目得点を更新
    point_max2   = point
    point_max2_i = i+1
    point_max2_d = d

#収穫時期が早い方を入り口から見て手前、遅い方を入り口から見て奥に植える
print(2)
if point_max1_d < point_max2_d:
  #作物1が手前、作物2が奥
  print(point_max1_i, i0, 0, 1)#手前
  print(point_max2_i, i0, 1, 1)#奥
else:
  #作物2が手前、作物1が奥
  print(point_max2_i, i0, 0, 1)#手前
  print(point_max1_i, i0, 1, 1)#奥

Visualizer　Seed0のスコア　：　3700点

次は→？
　　記事の都合上　＝　⑦へ

⑦　最初の作物を基準に、一気にたくさん植える。

得点　　　　：824,025点（暫定50ケース）
レーティング：800台　●

ひらめき：手前と奥の概念は、本当に必要か？

すべての入力を完了してから出力するような解法を実装できるのであれば理解可能
ABC294　A問題：

観察：
問題文ページの最下部に記載されている「入力例 1／出力例 1」をVisualizerに貼り付けて、1ターンずつ進めて観察してみると、作物を一気に収穫しているときがある。
今までの考察では、収穫時期によって手前と奥に分けていた。なのに、この「入力例 1／出力例 1」の結果では、まるで手前と奥なんかないみたいに振る舞っている。ずるい！

※赤い×は、その月に収穫した作物。

入り口から見た奥の作物が、青い線を辿って入り口に辿り着けないのではないか？という疑問を持った。

なぜこんなことができるのか、引き続きVisualizerを観察してみることにする。
そのターン中に植えてある作物にマウスカーソルを重ねると、その作物の全情報が表示される。

D（収穫月）が、同じになっていることがわかる。
収穫月が同じなら、入り口から見た手前の作物から収穫してくれるということ？
こういうときは、おとなしく問題文をよく読んでみる。読んでみたら、確かにそう書いてありました。
通れなくならないように順番に気を付けてね？という問題なので、手前と奥に分けなければならない。どこかで自分ルールに当てはめてしまうことが度々ある。誤読！思い込みに注意！

「収穫月が同じなら、手前と奥は不問になる」とは？：
収穫月が同じ作物を収穫する順番を考えるのは私ではなく、頭のいい部下が手前から順番になるように収穫してくれる。
たすかる。

頭のいい部下がすべてよしなにやってくれるのなら、収穫月が同じ作物は、何も考えずにすべてどこかに植えまくっておこう！きづかいぜろ！

どの収穫月を基準にする？：
最初の作物を基準とする。これが一番かんたんそう。

どこかに植えるって、どこに植える？：
北から順に植えていくことにする。北の西から東に１区画ずつ。埋まったら１区画南に。

最初の作物と同じ収穫月の作物を、北から順に植えていくのに必要な入力を見てみる。

入力	要/不要	理由
T	不要	初月に植えるため
H	不要	20固定なので、受け取るまでもないため
W	不要	20固定なので、受け取るまでもないため
i0	不要	最北端・最西端から順に受け取るため
h	不要	考えなくていいことは考察済みなので不要
v	不要	考えなくていいことは考察済みなので不要
K	必要★	作物1と同じ収穫月か、すべての作物を確認するため
S	不要	初月しか植えないため
D	必要★	作物1と同じ収穫月か確認するため

出力は？

出力	固定/任意	出力の内容
M	任意	作物1と同じ収穫月である作物の総数
k	任意	1→作物1と同じ収穫月である作物の番号→作物1と同じ収穫月である作物の番号→・・・
i	任意	最北端から順番に植える（20回0→20回1→20回2→・・・）
j	任意	最西端から順番に植える（0→1→2→・・・18→19→0→1→2→・・・）
s	固定	初月

実装：

しーげんご.c

#include<stdio.h>
int main(void)
{
  //最初の1行は読み飛ばす
  int t, h, w, i0;
  scanf("%d %d %d %d\n", &t, &h, &w, &i0);
  //39行分は読み飛ばす
  char dust[20+1];
  for(int i=0; i<39; i++)
  {
    scanf("%s\n", dust);
  }
  int k;
  scanf("%d\n", &k);//作物の総数
  
  //全作物の情報を受け取りながら、作物1と同じ収穫時期である作物の数を数える
  int s_one, d_one; //scanf用
  int d_all[k];     //収穫時期は後でまた使うので、全部格納するための配列を用意しておく
  int target_d;     //植えたい作物の収穫時期(基準)
  int plant_count=0;//植える作物の総数
  for(int i=0; i<k; i++)
  {
    scanf("%d %d\n", &s_one, &d_one);
    d_all[i] = d_one;
    if(0 == i)
    {
      //作物1の収穫時期を基準にする
      target_d = d_one;
    }
    if(target_d == d_one)
    {
      //作物1と同じ収穫時期なので、植える作物としてインクリメント
      plant_count++;
    }
  }
  
  printf("%d\n", plant_count);
  int news=0;//植える座標(0,0)が初期位置
  for(int i=0; i<k; i++)
  {
    if(target_d == d_all[i])
    {
      //作物iを座標の北西から順番に植えていく
      printf("%d %d %d 1\n", i+1, news/20, news%20);
      news++;//次の座標へ
    }
  }
  
  return 0;
}

しーぷらぷら.cpp

#include<iostream>
#include<string>
int main(void)
{
  //最初の1行は読み飛ばす
  int t, h, w, i0;
  std::cin >> t >> h >> w >> i0;
  //39行分は読み飛ばす
  std::string dust;
  for(int i=0; i<39; i++)
  {
    std::cin >> dust;
  }
  int k;
  std::cin >> k;//作物の総数
  
  //全作物の情報を受け取りながら、作物1と同じ収穫時期である作物の数を数える
  int s_one, d_one; //scanf用
  int d_all[k];     //収穫時期は後でまた使うので、全部格納するための配列を用意しておく
  int target_d;     //植えたい作物の収穫時期(基準)
  int plant_count=0;//植える作物の総数
  for(int i=0; i<k; i++)
  {
    std::cin >> s_one >> d_one;
    d_all[i] = d_one;
    if(0 == i)
    {
      //作物1の収穫時期を基準にする
      target_d = d_one;
    }
    if(target_d == d_one)
    {
      //作物1と同じ収穫時期なので、植える作物としてインクリメント
      plant_count++;
    }
  }
  
  //出力
  std::cout << plant_count << std::endl;
  int news=0;//植える座標(0,0)が初期位置
  for(int i=0; i<k; i++)
  {
    if(target_d == d_all[i])
    {
      //作物iを座標の北西から順番に植えていく
      std::cout << i+1 << " " << news/20 << " " << news%20 << " 1" << std::endl;
      news++;//次の座標へ
    }
  }
  return 0;
}

ぱいそん.py

#注意：私はPythonに詳しくないため、Pythonが初のプログラミング言語である人の書き方がわかりません。
#      Cっぽい書き方になりますが、考え方は一緒なのでご了承ください。

#最初の1行は読み飛ばす
t,h,w,i0=map(int, input().split())

#39行分は読み飛ばす
for _ in range(0, 39):
  input()

k = int(input())#作物の総数

#全作物の情報を受け取りながら、作物1と同じ収穫時期である作物の数を数える
d_all=[]      #収穫時期は後でまた使うので、全部格納するための配列を用意しておく
plant_count=0 #植える作物の総数
for i in range(0, k):
  s_one,d_one=map(int, input().split())
  d_all.append(d_one)
  if 0 == i:
    #作物1の収穫時期を基準にする
    target_d = d_one
  if target_d == d_one:
    #作物1と同じ収穫時期なので、植える作物としてインクリメント
    plant_count += 1

print(plant_count);
news=0 #植える座標(0,0)が初期位置
for i in range(len(d_all)):
  if target_d == d_all[i]:
    #作物iを座標の北西から順番に植えていく
    print(i+1, news//20, news%20, 1);
    news += 1 #次の座標へ

Visualizer　Seed0のスコア　：　17825点

次は→？
　　オセロで次の一手をたくさんひっくり返す手を選択するあなた　＝　⑧へ
　　そうではないあなた　＝　⑨へ

⑧　貪欲に、一気にたくさん植える。

得点　　　　：1,217,300点（暫定50ケース）
レーティング：800台　●

得点計算が難しいときは、得点計算をしないという決断。

これが解ければ理解可能
ABC240　B問題：

ABC245　B問題：

考察の前に：
AHCは、基本的に得点計算がややこしい。
今回の得点計算はかなりシンプルなので、解法⑧は飛ばしてしまってもいいくらい。
でも、次回以降や過去問に挑戦するときは覚えておいて欲しい。
「最高得点を目指す計算式が複雑で実装方法がわからないなら、得点に比例しそうな数値を目指すという手もある」ということを。

考察：
「⑦　最初の作物を基準に、一気にたくさん植える。」で判明したとおり、ひと月で収穫する作物は複数ある。
各月で収穫する作物の数の内、収穫できる作物の数が最高になる月を選べば、比較的高得点が取れるのではないだろうか？

各月で収穫する作物の数の内、最高数の月を選ぶのに必要な入力を見てみる。

入力	要/不要	理由
T	不要	初月に植えるため
H	不要	20固定なので、受け取るまでもないため
W	不要	20固定なので、受け取るまでもないため
i0	不要	最北端・最西端から順に受け取るため
h	不要	考えなくていいことは考察済みなので不要
v	不要	考えなくていいことは考察済みなので不要
K	必要★	各月の収穫数を確認するため
S	不要	初月しか植えないため
D	必要★	すべての作物に対して、収穫月を確認するため

出力は？

出力	固定/任意	出力の内容
M	任意	収穫数が一番多い月の、その収穫数
k	任意	収穫数が一番多い月ｎ作物の番号
i	任意	最北端から順番に植える（20回0→20回1→20回2→・・・）
j	任意	最西端から順番に植える（0→1→2→・・・18→19→0→1→2→・・・）
s	固定	初月

実装：

しーげんご.c

#include<stdio.h>
int main(void)
{
  //最初の1行は読み飛ばす
  int t, h, w, i0;
  scanf("%d %d %d %d\n", &t, &h, &w, &i0);
  //39行分は読み飛ばす
  char dust[20+1];
  for(int i=0; i<39; i++)
  {
    scanf("%s\n", dust);
  }
  int k;
  scanf("%d\n", &k);//作物の総数
  
  //全作物の情報を受け取る
  int s_one, d_one; //scanf用
  int d_all[k];     //収穫時期は後でまた使うので、全部格納するための配列を用意しておく
  //全作物の情報を配列に詰め込んでおく
  for(int i=0; i<k; i++)
  {
    scanf("%d %d\n", &s_one, &d_one);
    d_all[i] = d_one;
  }
  
  int plant_count=0;//植える作物の総数(最大数)
  int target_d;     //植えたい作物の収穫時期(基準)
  for(int d=0; d<=100; d++)
  {
    //初月から順に作物数を確認する
    int count_d=0;  //今月植えることができる作物数
    for(int i=0; i<k; i++)
    {
      if(d_all[i] == d)
      {
        //この時期に植えたい作物である
        count_d++;
      }
    }
    
    //今月植えることができる作物数は、前月までと比べて最大か確認
    if(plant_count <= count_d)
    {
      //最大である
      plant_count = count_d;//最大数を覚えておく
      target_d    = d;      //最大数な収穫時期を覚えておく
    }
  }
  
  printf("%d\n", plant_count);
  int news=0;//植える座標(0,0)が初期位置
  for(int i=0; i<k; i++)
  {
    if(target_d == d_all[i])
    {
      //作物iを座標の北西から順番に植えていく
      printf("%d %d %d 1\n", i+1, news/20, news%20);
      news++;//次の座標へ
    }
  }
  
  return 0;
}

しーぷらぷら.cpp

#include<iostream>
#include<string>
int main(void)
{
  //最初の1行は読み飛ばす
  int t, h, w, i0;
  std::cin >> t >> h >> w >> i0;
  //39行分は読み飛ばす
  std::string dust;
  for(int i=0; i<39; i++)
  {
    std::cin >> dust;
  }
  int k;
  std::cin >> k;//作物の総数
  
  //全作物の情報を受け取る
  int s_one, d_one; //cin用
  int d_all[k];     //収穫時期は後でまた使うので、全部格納するための配列を用意しておく
  //全作物の情報を配列に詰め込んでおく
  for(int i=0; i<k; i++)
  {
    std::cin >> s_one >> d_one;
    d_all[i] = d_one;
  }
  
  int plant_count=0;//植える作物の総数(最大数)
  int target_d;     //植えたい作物の収穫時期(基準)
  for(int d=0; d<=100; d++)
  {
    //初月から順に作物数を確認する
    int count_d=0;  //今月植えることができる作物数
    for(int i=0; i<k; i++)
    {
      if(d_all[i] == d)
      {
        //この時期に植えたい作物である
        count_d++;
      }
    }
    
    //今月植えることができる作物数は、前月までと比べて最大か確認
    if(plant_count <= count_d)
    {
      //最大である
      plant_count = count_d;//最大数を覚えておく
      target_d    = d;      //最大数な収穫時期を覚えておく
    }
  }
  
  std::cout << plant_count << std::endl;
  int news=0;//植える座標(0,0)が初期位置
  for(int i=0; i<k; i++)
  {
    if(target_d == d_all[i])
    {
      //作物iを座標の北西から順番に植えていく
      std::cout << i+1 << " " << news/20 << " " << news%20 << " 1" << std::endl;
      news++;//次の座標へ
    }
  }
  
  return 0;
}

ぱいそん.py

#注意：私はPythonに詳しくないため、Pythonが初のプログラミング言語である人の書き方がわかりません。
#      Cっぽい書き方になりますが、考え方は一緒なのでご了承ください。

#最初の1行は読み飛ばす
t,h,w,i0=map(int, input().split())

#39行分は読み飛ばす
for _ in range(0, 39):
  input()

k = int(input())#作物の総数

#全作物の情報を受け取る
d_all=[]      #収穫時期は後でまた使うので、全部格納するための配列を用意しておく
for i in range(0, k):
  s_one,d_one=map(int, input().split())
  d_all.append(d_one)

plant_count=0 #植える作物の総数(最大数)
target_d=0    #植えたい作物の収穫時期(基準)
for d in range(0, 100+1):
  #初月から順に作物数を確認する
  count_d=0   #今月植えることができる作物数
  for i in range(0, k):
    if d_all[i] == d:
      #この時期に植えたい作物である
      count_d += 1
  
  #今月植えることができる作物数は、前月までと比べて最大か確認
  if plant_count <= count_d:
    #最大である
    plant_count = count_d #最大数を覚えておく
    target_d    = d       #最大数な収穫時期を覚えておく

print(plant_count);
news=0 #植える座標(0,0)が初期位置
for i in range(len(d_all)):
  if target_d == d_all[i]:
    #作物iを座標の北西から順番に植えていく
    print(i+1, news//20, news%20, 1);
    news += 1 #次の座標へ

Visualizer　Seed0のスコア　：　26250点

次は→？
　　記事の都合上　＝　⑧へ

⑨　最高得点になるように、一気にたくさん植える。

得点　　　　：977,275点（暫定50ケース）
レーティング：800台　●

「最高得点を目指す」にも、いろいろある。

これらを応用できるのであれば理解可能
ABC290　A問題：

ABC307　A問題：

最高得点の振り返り：
・③　最高得点になるように作物を1個植える。
　　すべての作物の得点を計算し、一番得点の高い作物を植える。
・⑤　最高得点になるように、2個作物を植える。
　　すべての作物の得点を計算し、一番得点の高い作物と二番目に高い作物を植える。

一気にたくさん植える振り返り：
・⑦　最初の作物を基準に、一気にたくさん植える。
　　すべての作物の収穫月を確認し、1つ目の作物と同じ収穫月の作物をすべて植える。
・⑧　貪欲に、一気にたくさん植える。
　　すべての作物を収穫月別にカウントし、一番カウントが多い収穫月の作物をすべて植える。

この勢いで、今回の解法を記載しましょう。
　　すべての作物を収穫月別に得点計算し、一番得点の高い収穫月の作物をすべて植える。

上記に必要な入力を見てみる。

入力	要/不要	理由
T	不要	初月に植えるため
H	不要	20固定なので、受け取るまでもないため
W	不要	20固定なので、受け取るまでもないため
i0	不要	最北端・最西端から順に受け取るため
h	不要	考えなくていいことは考察済みなので不要
v	不要	考えなくていいことは考察済みなので不要
K	必要★	各月の合計得点を確認するため
S	不要	初月しか植えないため
D	必要★	すべての作物に対して、得点を確認するため

出力は？

出力	固定/任意	出力の内容
M	任意	合計得点が一番多い月の収穫数
k	任意	合計得点が一番多い月の作物の番号
i	任意	最北端から順番に植える（20回0→20回1→20回2→・・・）
j	任意	最西端から順番に植える（0→1→2→・・・18→19→0→1→2→・・・）
s	固定	初月

実装：
後述しますが、この実装にはバグがあります（ここまで来たあなたなら、、、わかりますか？）。

しーげんご.c

#include<stdio.h>
int main(void)
{
  //最初の1行は読み飛ばす
  int t, h, w, i0;
  scanf("%d %d %d %d\n", &t, &h, &w, &i0);
  //39行分は読み飛ばす
  char dust[20+1];
  for(int i=0; i<39; i++)
  {
    scanf("%s\n", dust);
  }
  int k;
  scanf("%d\n", &k);//作物の総数
  
  //全作物の情報を受け取りながら、作物1と同じ収穫時期である作物の数を数える
  int s_all[k], d_all[k];//後でまた使うので、全部格納するための配列を用意しておく
  //全作物の情報を配列に詰め込んでいく
  for(int i=0; i<k; i++)
  {
    scanf("%d %d\n", &s_all[i], &d_all[i]);
  }
  
  int plant_count=0;  //植える作物の総数
  int max_sum_point=0;//最大合計得点
  int target_d;       //植えたい作物の収穫時期(基準)
  for(int d=0; d<=100; d++)
  {
    //初月から順に作物数を確認する
    int count=0;      //植える作物の総数
    int sum_point=0;  //今月植えることができる作物の合計得点
    for(int i=0; i<k; i++)
    {
      if(d_all[i] == d)
      {
        //この時期に植えたい作物である
        sum_point = d_all[i] - s_all[i] + 1;
        count++;
      }
    }
    
    //今月植えることができる作物の合計得点は、前月までと比べて最大か確認
    if(max_sum_point <= sum_point)
    {
      //合計得点が最大である
      max_sum_point = sum_point;
      plant_count   = count;
      target_d      = d;      //最大数な収穫時期を覚えておく
    }
  }
  
  printf("%d\n", plant_count);
  int news=0;//植える座標(0,0)が初期位置
  for(int i=0; i<k; i++)
  {
    if(target_d == d_all[i])
    {
      //作物iを座標の北西から順番に植えていく
      printf("%d %d %d 1\n", i+1, news/20, news%20);
      news++;//次の座標へ
    }
  }
  
  return 0;
}

しーぷらぷら.cpp

#include<iostream>
#include<string>
int main(void)
{
  //最初の1行は読み飛ばす
  int t, h, w, i0;
  std::cin >> t >> h >> w >> i0;
  //39行分は読み飛ばす
  std::string dust;
  for(int i=0; i<39; i++)
  {
    std::cin >> dust;
  }
  int k;
  std::cin >> k;//作物の総数
  
  //全作物の情報を受け取りながら、作物1と同じ収穫時期である作物の数を数える
  int s_one, d_one;       //cin用
  int s_all[k], d_all[k]; //後でまた使うので、全部格納するための配列を用意しておく
  //全作物の情報を配列に詰め込んでいく
  for(int i=0; i<k; i++)
  {
    std::cin >> s_one >> d_one;
    s_all[i] = s_one;
    d_all[i] = d_one;
  }
  
  int plant_count=0;  //植える作物の総数
  int max_sum_point=0;//最大合計得点
  int target_d;       //植えたい作物の収穫時期(基準)
  for(int d=0; d<=100; d++)
  {
    //初月から順に作物数を確認する
    int count=0;      //植える作物の総数
    int sum_point=0;  //今月植えることができる作物の合計得点
    for(int i=0; i<k; i++)
    {
      if(d_all[i] == d)
      {
        //この時期に植えたい作物である
        sum_point = d_all[i] - s_all[i] + 1;
        count++;
      }
    }
    
    //今月植えることができる作物の合計得点は、前月までと比べて最大か確認
    if(max_sum_point <= sum_point)
    {
      //合計得点が最大である
      max_sum_point = sum_point;
      plant_count   = count;
      target_d      = d;      //最大数な収穫時期を覚えておく
    }
  }
  
  std::cout << plant_count << std::endl;
  int news=0;//植える座標(0,0)が初期位置
  for(int i=0; i<k; i++)
  {
    if(target_d == d_all[i])
    {
      //作物iを座標の北西から順番に植えていく
      std::cout << i+1 << " " << news/20 << " " << news%20 << " 1" << std::endl;
      news++;//次の座標へ
    }
  }
  
  return 0;
}

ぱいそん.py

#注意：私はPythonに詳しくないため、Pythonが初のプログラミング言語である人の書き方がわかりません。
#      Cっぽい書き方になりますが、考え方は一緒なのでご了承ください。

#最初の1行は読み飛ばす
t,h,w,i0=map(int, input().split())

#39行分は読み飛ばす
for _ in range(0, 39):
  input()

k = int(input())#作物の総数

#全作物の情報を受け取る
#後でまた使うので、全部格納するための配列を用意しておく
s_all=[]
d_all=[]
for i in range(0, k):
  s_one,d_one=map(int, input().split())
  s_all.append(s_one)
  d_all.append(d_one)

plant_count=0   #植える作物の総数(最大数)
max_sum_point=0 #最大合計得点
target_d=0      #植えたい作物の収穫時期(基準)
for d in range(0, 100+1):
  #初月から順に作物数を確認する
  count=0       #今月植えることができる作物数
  sum_point=0   #今月植えることができる作物の合計得点
  for i in range(0, k):
    if d_all[i] == d:
      #この時期に植えたい作物である
      sum_point = d_all[i] - s_all[i] + 1
      count += 1
  
  #今月植えることができる作物の合計得点は、前月までと比べて最大か確認
  if max_sum_point <= sum_point:
    #合計得点が最大である
    max_sum_point = sum_point
    plant_count   = count     #最大数を覚えておく
    target_d      = d         #最大数な収穫時期を覚えておく

print(plant_count);
news=0 #植える座標(0,0)が初期位置
for i in range(len(d_all)):
  if target_d == d_all[i]:
    #作物iを座標の北西から順番に植えていく
    print(i+1, news//20, news%20, 1);
    news += 1 #次の座標へ

Visualizer　Seed0のスコア　：　29025点

次は⑨→？
　　バグを取り除きたい　＝　⑩へ

⑩　「⑨　最高得点になるように、一気にたくさん植える。」のバグを取る。

得点　　　　：1,288,700点（暫定50ケース）
レーティング：800台　●

バグに気付くにもスキルが必要。

バグには、気付けるバグと簡単には気付けないバグがある。
今回の解法⑨は、最高得点を目指したのに得点が低くなっていて気付けるバグ。
解法⑤は、簡単には気付けないバグだった。
気付けないバグに気付いたら、自分をほめよう！

バグの概要：
得点を合計したいのに、合計していない。

バグの説明：
コードを見れば一目瞭然。
加算していなかった。

修正例：

えぬじー.c

sum_point = d_all[i] - s_all[i] + 1;

おーけー.c

sum_point += d_all[i] - s_all[i] + 1;

その他　改善箇所の概要：
初月を0ヵ月目としているが、初月は1か月目である。

バグの説明：
0ヵ月目の処理を入れていても問題ないが、0ヵ月目に植える作物は存在しないため、処理があっても意味がない。

修正例：

えぬじー.c

for(int d=0; d<=100; d++)

おーけー.c

for(int d=1; d<=100; d++)

実装：

しーげんご.c

#include<stdio.h>
int main(void)
{
  //最初の1行は読み飛ばす
  int t, h, w, i0;
  scanf("%d %d %d %d\n", &t, &h, &w, &i0);
  //39行分は読み飛ばす
  char dust[20+1];
  for(int i=0; i<39; i++)
  {
    scanf("%s\n", dust);
  }
  int k;
  scanf("%d\n", &k);//作物の総数
  
  //全作物の情報を受け取りながら、作物1と同じ収穫時期である作物の数を数える
  int s_all[k], d_all[k];//後でまた使うので、全部格納するための配列を用意しておく
  //全作物の情報を配列に詰め込んでいく
  for(int i=0; i<k; i++)
  {
    scanf("%d %d\n", &s_all[i], &d_all[i]);
  }
  
  int plant_count=0;  //植える作物の総数
  int max_sum_point=0;//最大合計得点
  int target_d;       //植えたい作物の収穫時期(基準)
  for(int d=0; d<=100; d++)
  {
    //初月から順に作物数を確認する
    int count=0;      //植える作物の総数
    int sum_point=0;  //今月植えることができる作物の合計得点
    for(int i=0; i<k; i++)
    {
      if(d_all[i] == d)
      {
        //この時期に植えたい作物である
        sum_point += d_all[i] - s_all[i] + 1;
        count++;
      }
    }
    
    //今月植えることができる作物の合計得点は、前月までと比べて最大か確認
    if(max_sum_point <= sum_point)
    {
      //合計得点が最大である
      max_sum_point = sum_point;
      plant_count   = count;
      target_d      = d;      //合計得点が最大な収穫時期を覚えておく
    }
  }
  
  printf("%d\n", plant_count);
  int news=0;//植える座標(0,0)が初期位置
  for(int i=0; i<k; i++)
  {
    if(target_d == d_all[i])
    {
      //作物iを座標の北西から順番に植えていく
      printf("%d %d %d 1\n", i+1, news/20, news%20);
      news++;//次の座標へ
    }
  }
  
  return 0;
}

しーぷらぷら.cpp

#include<iostream>
#include<string>
int main(void)
{
  //最初の1行は読み飛ばす
  int t, h, w, i0;
  std::cin >> t >> h >> w >> i0;
  //39行分は読み飛ばす
  std::string dust;
  for(int i=0; i<39; i++)
  {
    std::cin >> dust;
  }
  int k;
  std::cin >> k;//作物の総数
  
  //全作物の情報を受け取りながら、作物1と同じ収穫時期である作物の数を数える
  int s_one, d_one;       //cin用
  int s_all[k], d_all[k]; //後でまた使うので、全部格納するための配列を用意しておく
  //全作物の情報を配列に詰め込んでいく
  for(int i=0; i<k; i++)
  {
    std::cin >> s_one >> d_one;
    s_all[i] = s_one;
    d_all[i] = d_one;
  }
  
  int plant_count=0;  //植える作物の総数
  int max_sum_point=0;//最大合計得点
  int target_d;       //植えたい作物の収穫時期(基準)
  for(int d=0; d<=100; d++)
  {
    //初月から順に作物数を確認する
    int count=0;      //植える作物の総数
    int sum_point=0;  //今月植えることができる作物の合計得点
    for(int i=0; i<k; i++)
    {
      if(d_all[i] == d)
      {
        //この時期に植えたい作物である
        sum_point += d_all[i] - s_all[i] + 1;
        count++;
      }
    }
    
    //今月植えることができる作物の合計得点は、前月までと比べて最大か確認
    if(max_sum_point <= sum_point)
    {
      //合計得点が最大である
      max_sum_point = sum_point;
      plant_count   = count;
      target_d      = d;      //最大数な収穫時期を覚えておく
    }
  }
  
  std::cout << plant_count << std::endl;
  int news=0;//植える座標(0,0)が初期位置
  for(int i=0; i<k; i++)
  {
    if(target_d == d_all[i])
    {
      //作物iを座標の北西から順番に植えていく
      std::cout << i+1 << " " << news/20 << " " << news%20 << " 1" << std::endl;
      news++;//次の座標へ
    }
  }
  
  return 0;
}

ぱいそん.py

#注意：私はPythonに詳しくないため、Pythonが初のプログラミング言語である人の書き方がわかりません。
#      Cっぽい書き方になりますが、考え方は一緒なのでご了承ください。

#最初の1行は読み飛ばす
t,h,w,i0=map(int, input().split())

#39行分は読み飛ばす
for _ in range(0, 39):
  input()

k = int(input())#作物の総数

#全作物の情報を受け取る
#後でまた使うので、全部格納するための配列を用意しておく
s_all=[]
d_all=[]
for i in range(0, k):
  s_one,d_one=map(int, input().split())
  s_all.append(s_one)
  d_all.append(d_one)

plant_count=0   #植える作物の総数(最大数)
max_sum_point=0 #最大合計得点
target_d=0      #植えたい作物の収穫時期(基準)
for d in range(0, 100+1):
  #初月から順に作物数を確認する
  count=0       #今月植えることができる作物数
  sum_point=0   #今月植えることができる作物の合計得点
  for i in range(0, k):
    if d_all[i] == d:
      #この時期に植えたい作物である
      sum_point += d_all[i] - s_all[i] + 1
      count += 1
  
  #今月植えることができる作物の合計得点は、前月までと比べて最大か確認
  if max_sum_point <= sum_point:
    #合計得点が最大である
    max_sum_point = sum_point
    plant_count   = count     #最大数を覚えておく
    target_d      = d         #最大数な収穫時期を覚えておく

print(plant_count);
news=0 #植える座標(0,0)が初期位置
for i in range(len(d_all)):
  if target_d == d_all[i]:
    #作物iを座標の北西から順番に植えていく
    print(i+1, news//20, news%20, 1);
    news += 1 #次の座標へ

Visualizer　Seed0のスコア　：　29025点

次は→？
　　ないっ！

■まとめ

・できることから1つずつ取り組む。（解法①〜⑩）
・満点に気を取られすぎない。（解法②④⑦⑧）
・無駄からわかることもある。（解法④）
・気付きを大切に進む。（解法⑦）
・複雑さを捨てる決断を。（解法⑧）
・言われたことを守る必要はない。
・すべて【楽しい】に繋がる。

■募集

・AHCに興味を持ってくれる人。
・AtCoderともだち。

■リンク

オススメの記事（AHC033参加記）です。
私は、このmasuTomo様の記事を読んで、AHCの楽しさを再確認しました♪

ここまで読んでくださり、ありがとうございます。

次回のAHCで会いましょう♪

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

ABC1完erのためのAHC入門【解法と考察過程と実装付き】 by ABC2完er

■伝えたいこと

■導入

■この記事に書いてあること

■私のAtCoderのレベル感

■解法の目次

■解法

① 何もしない。ただし0点。

② 最初の作物だけ植える。

③ 最高得点になるように作物を1個植える。

④ 最初の2個、作物を植える。

⑤ 最高得点になるように、2個作物を植える。

⑥ 「⑤ 最高得点になるように、2個作物を植える。」のバグを取る。

⑦ 最初の作物を基準に、一気にたくさん植える。

⑧ 貪欲に、一気にたくさん植える。

⑨ 最高得点になるように、一気にたくさん植える。

⑩ 「⑨ 最高得点になるように、一気にたくさん植える。」のバグを取る。

■まとめ

■募集

■リンク

ここまで読んでくださり、ありがとうございます。

①　何もしない。ただし0点。

②　最初の作物だけ植える。

③　最高得点になるように作物を1個植える。

④　最初の2個、作物を植える。

⑤　最高得点になるように、2個作物を植える。

⑥　「⑤　最高得点になるように、2個作物を植える。」のバグを取る。

⑦　最初の作物を基準に、一気にたくさん植える。

⑧　貪欲に、一気にたくさん植える。

⑨　最高得点になるように、一気にたくさん植える。

⑩　「⑨　最高得点になるように、一気にたくさん植える。」のバグを取る。