こんにちは、トア・ルドクターです。
みなさんはバイトリーダーに憧れたことありますでしょうか。世界中のアルバイト達に尊敬される対象であるとともに、遍くアルバイト達のシフトを司りし存在です。僕はエンジニア・ラウンジ・パーティ運営・塾講師など様々なバイトをしましたが、実際、バイトリーダー的な存在がいたのか記憶にございません。

前置きはさておき、今回もAtCoderの問題解説になります。暫くは競技プログラミング周辺の記事が多くなるかと思うのですが「AtCoderとか競技プログラミングって何？」という人は【第４話】を御参照ください。個人的には競技プログラミングの面白さを多くの人に知って欲しいという思いがありますが、あくまでエンジニアスキルの一類型にすぎないので、興味ある人は是非！程度に留めておきます。そのうち、ディープラーニング・セキュリティ系・アプリ作成などのテーマも扱う予定です。

早速ですが、問題に入りましょう。
前回なんとなく書いたプログラミングの心技体という解説方式が個人的に気に入ったので、今回もそういう流れで参ります。

【問題】ABC080のD問題

（１）プログラミングの体（知識）

この問題を解くには imos法というアルゴリズムが有力です。簡便化した次の問題を考えてください。

【例題】バイトリーダー
あなたはN人のアルバイトを束ねるバイトリーダーです。勤務帯によってはバイトの人数が多すぎることが発覚しました。そこで、タイムカードの履歴から最もバイト人数の多い時間帯を求めてください。
i番目のバイトの出勤時間は "a[i] 時〜 b[i] 時" で与えられ、0時〜24時の範囲とします（日を跨ぐことはないとする）。

シンプルに実装しようとすると、0-24の数字を格納した時間リストを作成して、各時間ごとに a[i] - b[i] の範囲に含まれるか見ていく。例えば、0時を含む人は●人、1時を含む人は●人・・・と回していく。このときの計算量は、25*N であり O(M*N)オーダーです。M=25 程度ならいいものの、計算量削減の工夫をしたいところです。この方法のピットフォールは、みる必要のない時間まで計算してしまう点です。例えば、1-4時と3-5時の重複を考えるとき、重複時間は1,4,3,5のいずれかの数字で示されるはずなので（この場合3-4時）、2時が含まれるかどうか各々確認するのは無駄です。

そこで imos法の出番です。これは各時間のバイト人数の絶対数を見るのではなく、各時間の人数変化を追っていく方法です。まず全要素を0で初期化した imosリストを作成し、人数変化をこのリストに格納します。たとえば、バイトAが 1-4時勤務であれば、imos[1] += 1 とし、imos[5] -= 1 とします（4時ではなく1時間後の5時に消える点に注意）。同様に、バイトBが3-5時勤務であれば、imos[3] += 1 とし、imos[6] -= 1 とします。これを全てのバイトに対して処理すれば、全ての時間における人数変化が分かり、このときの計算量は O(N) となります。実際に知りたいのは、各時間におけるアルバイト人数の絶対数ですから、この人数変化の累積和を取ればいいわけです（速度を積分すると距離になるのと同じ発想）。累積和の計算は、各時間i（i>=1）に対して imos[i] += imos[i-1] という漸化式を繰り返せばいいので計算量は O(M) に過ぎません。したがって、全体の計算量は O(N+M) であり十分に高速です。以下が例題の解答です。

import numpy as np

# 標準入力
n = int(input())
a,b = [],[]
for _ in range(n):
   aa,bb = map(int,input().split())
   a.append(aa)
   b.append(bb)

# imosリストを埋めていく作業
imos = np.zeros(24+2, dtype=np.int64)
for i in range(n):
   imos[a[i]] += 1
   imos[b[i]+1] -= 1

# 累積和のリストを得るnumpyメソッド
cumsum = imos.cumsum()
# enumerateで配列のインデックス/要素を得る
for i,ele in enumerate(cumsum):
   if ele == cumsum.max() : print(i)

imosリストの初期化は numpy の np.zeros を用いると簡単で、更に numpy のリストでは累積和を求める cumsumメソッドを使うことができます（因みにnumpy配列の計算速度はint64が最速）。
またpythonの小技ですが、enumerate関数を使うと、配列のインデックスと要素（element）を同時に取り出すことができます。特定の値の要素についてインデックスを知りたい場合など有用です。

（２）プログラミングの技（発想）

この問題が imos法の問題だということは知識さえあれば着想しやすいでしょう。ただ、今回の問題は直球ではなく変化球的な問題です。同じチャンネル内では連続予約可能だが、異なるチャンネル同士では連続予約不可能（たとえ連続番組でも他の録画機じゃないと無理）という条件をどう処理するかがポイントでした。結論を言えば、同じチャンネル内での連続番組は１つの録画機でカバーする（連続番組を統合して１つの番組として扱う）ことで、録画のコスパを最大化できます。この方法論の着想こそ、エンジニアとしての技巧が問われる部分です。仮に方法論が分かったとしても、如何にして実装するかというところに創意工夫の余地は沢山あります。１つの実装法として、配列 [s, t] たちをsに関してソートして、t[i-1] = s[i] であれば [s[i-1], t[i]] という配列へ統合する方法が考えられます。

（３）プログラミングの心（忍耐）

知識が十分にあり解法が着想できたら、最後は粘り強さ・忍耐力で勝負が決まります。個人的に苦戦したポイントを２つ挙げておきます。

①imosの配列サイズのミス
　→「時間の最大値+1」を格納できる配列を作らないといけない
②連続番組の統合において、事前にソートし忘れた
　→凡ミスだが、多くのケースで偶然ACしちゃった所為で、原因になかなか気づけなかった

提出したコードのどこに誤謬があるのか、それが方法論レベルのものなのか、記法レベルのものなのか探り出す姿勢が重要です。所謂「デバッグ力」のことですが、最終的には忍耐力ではないでしょうか。

【解答】

import numpy as np

# 標準入力
n,c = map(int,input().split())
chs = [[] for _ in range(c+1)]
for _ in range(n):
   s,t,c = map(int,input().split())
   chs[c].append([s,t])

# 同チャンネル内の連続番組を統合
# timesリストに全部まとめて格納
times = []
for ch in chs:
   if not ch: continue
   ch.sort()
   for i in range(len(ch)):
       if i == 0: continue
       if ch[i-1][1] == ch[i][0]:
           ch[i] = [ch[i-1][0], ch[i][1]]
           ch[i-1] = []
   for arr in ch:
       if arr: times.append(arr)

# いもす法
# numpyのメソッドで累積和
imos = np.zeros(10**5+2, dtype=np.int64)
for arr in times:
   imos[arr[0]] += 1
   imos[arr[1]+1] -= 1
ans = imos.cumsum().max()
print(ans)

コードについて、改善点・アドバイス等ありましたら御教授いただけると幸いに存じます。最後に imos法の復習問題を載せておきます。

【問題】ABC035のC問題

それではまたいつか！

【著者プロフィール】
都内で医師として研鑽する傍ら、独学でプログラミングを学ぶ26歳。趣味は『ギター / バイオリン / 美術鑑賞 / youtube鑑賞 / 創作料理 / 囲碁 / チェス / 折り紙 / スノボ / サーフィン / ドライブ』など枚挙にいとまがない。CIAの格闘武術クラブマガを始める。得意料理はバナナシチュー。ビールと牡蠣は生派だが生セックスは断固せず、経験人数の常用対数は２未満と清純を極める。略歴としては高２で数学全国１位（駿台）、文系で官僚をめざすも、ドラマ『コードブルー』の影響から気づいたら医師に。ディープラーニングG検定、統計検定２級、知的財産検定３級など取得。TOEICは次回900目指す予定（仮）。

【記事アーカイブ】
【第１話】医者なのにプログラミングを勉強してみた話
【第２話】pythonプログラミングの小技（１）ラムダ
【第３話】プログラミング初心者が学ぶべき３つのポイント
【第４話】競技プログラミングのススメ
【第５話】競技プログラミング物語（１）バイトリーダーの苦悩
【第６話】プログラミングで自作する実用アプリ（１）NEVER-NOTE
【第７話】プログラミングで解析したDNA鑑定の精度
【第８話】統計学は最強の学問であるのか？
【第９話】プログラミングすれば人類最高IQに対抗できる説