AtCoder Beginner Contest 182 D問題

AtCoder Python

前書き

atcoder.jp

D問題

難易度：茶色
時間：タイムオーバー

O(n**2)の処理はできないので計算量を意識しながらコードを書かないといけません。

1回目の提出

はい数個のWA。
累積和を使えば解ける問題と言うのは察していました。
実は動作i終了後でのロボットの位置の最大値だと勘違いしてしまい「簡単やん」と思ったのが運のつき。
動作iの途中位置も含めてのロボットの位置の最大値でした。

最後の処理がまずい事は気付きながら時間がないのでとりあえず提出しました。

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
Alis, Sumlis = np.zeros(len(A)), np.zeros(len(A))
 
for i in range(len(A)):
    Alis[i] += Alis[i-1]+A[i]
    Sumlis[i] += Sumlis[i-1]+Alis[i]

np.append(Sumlis,0)
np.append(Alis,0)
print(int(max(np.max(Alis[:np.argmax(Sumlis)+1])+np.max(Sumlis),0)))

2回目

アルゴリズムは以下の通りです。

  1. 動作i(1,2..,n)が増すごとにA[i]の移動変位は累積されていく
  2. 動作nにおいてロボットの移動変位を配列化（Alis）
  3. 動作iではi回の移動をします。i回の中で最も正の方向に移動した移動変位の配列化（Amax）
  4. 動作i終了時点でのロボットの位置を配列化（Sumlis）
  5. 動作i-1での位置（Sumlis）+次の動作iでの最大移動変位（Amax）の和を取得（Ans）
  6. スタート位置が最大の場合・ゴール位置が最大の場合・最大位置（Ans）で最も最大となる地点を出力

私は3の発想がなかったですね。精進しなきゃ。

import numpy as np
import sys
 
N = int(input())
A = np.array(list(map(int, input().split())))
Alis, Amax, Sumlis = np.zeros(len(A)), np.zeros(len(A)), np.zeros(len(A)+1)
 
if N==1:
  print(max(max(A),0))
  sys.exit()
        
# N=1の場合、Alis[i-1]でA[0]を参照してしまうので注意
for i in range(N):
  Alis[i] = Alis[i-1]+A[i]
  Amax[i] = max(Alis[i],Amax[i-1])
  Sumlis[i+1] += Sumlis[i]+Alis[i-1]+A[i]
 
Ans = Sumlis[:N]+Amax
print(int(max(max(np.max(Ans),0),Sumlis[-1])))

結果

WA（数個WA）→WA（1個WA）→AC

AtCoder Beginner Contest 183 D問題

AtCoder Python

前書き

atcoder.jp

D問題

難易度：茶色
時間：60分超

超苦戦して、時間を浪費しましたが、何とか自力で解きました。
キーワードは「累積和」です。

qiita.com

与えられている条件設定は以下の通り。

1≤N≤2*10**5
0≤Si≤Ti≤2*10**5
1≤W,Pi≤10**9

こちらをざっと見てO(N**2)の計算はできないなと察したのですが、二重ループを必要とするアルゴリズムしか最初思い浮かびませんでした。
Ni氏が湯を使用し始めた時間をSi、使用を終えた時間をTi、使用量をPiとします。

  • 配列の区間（Si〜Ti）に使用量Piの値を代入処理（O(N)） * N人分の処理（O(N)）

でO(N**2)になるなとずっと悩んでいました。

回答

import numpy as np
N,M = map(int, input().split())
Tmax, STPlis = 0, []
 
for p in range(N):
  STP = list(map(int, input().split()))
  STPlis.append(STP)
  Tmax = max(STP[1], Tmax)
 
Timelis = np.zeros(Tmax+1)
Sumlis = np.zeros(Tmax+2)
 
for stp in STPlis:
  Timelis[stp[0]] += stp[2]
  Timelis[stp[1]] -= stp[2]
 
for j in range(1,Tmax+1):
  Sumlis[j] = Timelis[j-1]+Sumlis[j-1]
 
if int(max(Sumlis))<=M: print('Yes')
else: print('No')

解説

考えを変えて「累積和」を意識します。

「使用開始時間SI」・「使用終了時間Ti」にのみ使用量Piを配列に当てはめます。
Timelisは「新たに時間tから変化する使用湯量」の配列です。
力学で例えるとこれは「加速度」の配列です。

for stp in STPlis:
  Timelis[stp[0]] += stp[2]
  Timelis[stp[1]] -= stp[2]

Si < t < Tiの継続使用期間では等速直線運動をしているイメージです。
なので 「v = v0 + at」の式で習ったように、「現在tの使用湯量 = (t-1)での使用湯量 + 新たに時間tから変化する使用湯量」になります。
Sumlisは「現在tの使用湯量」の配列で、力学で例えると「速度」の配列です。

for j in range(1,Tmax+1):
  Sumlis[j] = Timelis[j-1]+Sumlis[j-1]

Sumlisの配列から最大値がMを超えていないか確認するだけです。

結果

ACでした。

AtCoder Beginner Contest 185 D問題

AtCoder Python

前書き

atcoder.jp

D問題

難易度：茶色
時間：45分

おおよそのアルゴリズムは10分ほどで浮かび、実装していましたが、
場合分けを忘れておりWAを出してしまい、時間ロス。

「白色タイルを無くすためにスタンプを押そう！でも青色タイルには押さないでね」という問題。
スタンプのサイズは最初の一回のみ決定できます。
白色タイルは1≤N≤10**9、青色タイルは1≤M≤2*10**5です。

1. まず最初にすべき場合分け処理

  • 青色のタイルが全く存在しない場合はサイズNのスタンプで1度押すだけ
  • 青色のタイルがNの場合は白色タイルが存在しないので0度

2. 連続する白色タイルの最小値(>0)を求めます

  • 次に青色タイルが0個目、N+1個目に存在すると仮定→両端処理
  • 白色タイルの連続値を取得、同時に連続値の最小値（→スタンプのサイズ）も取得

3. 白色タイルにスタンプを押す最小回数を求めます

import math
import sys
N, M = map(int, input().split())
Delta,count,size = [],0,N
A = [aa for aa in map(int, input().split())]
A.sort()

if M==0: 
  print(1)
  sys.exit()
if len(A)==N:
  print(0)
  sys.exit()

A.insert(0,0)
A.append(N+1)
for i in range(0,M+1):
  c=A[i+1]-A[i]
  Delta.append(abs(c-1)) 
  if c-1>0: size = min(size, c-1)

for j in Delta:
  count += math.ceil(j/size)
print(count)

ACでした。

地頭が悪いので「地頭力を鍛える」を要約してみた

雑記 読書

前書き

前回、以下の記事を書きました。「思考停止で情報に溺れてはいけないよ」という話です。
melheaven.hatenadiary.jp

「地頭力を鍛える」
問題解決に生かす「フェルミ推定」/ 細谷功

www.amazon.co.jp


フェルミ推定には３つの能力が養われます。

  • 仮説を立てて考える力
  • 全体から考える力
  • 単純に考える力

それぞれに足りてないと感じる経験があります。
ではどうすれば養えるのかを考えていきます。

仮説を立てて考える力

例えば私は「アプリ作りたいけど、いきなりプログラミング言語の学習から入っていた」経験があります。

(⌒,_ゝ⌒)ワイ「結局、続かずやめる、何があかんねん」

結論から考える事です。

「あらかじめ結論を予測して、仮説を用意する」必要があります。アプリ開発の例では「一から百を勉強するよりも、ゴールを見据えて必要な知識だけを学べば良い」という考え方です。

(⌒,_ゝ⌒)ワイ「プログラミングについて何も知らんと、そんなん仮説すら立てられへんやん」

個人で前提条件を立てて、仮説を想定してください。

「アプリで何を成し遂げたいのか」→「アプリのコンセプト」→「アプリの機能」→「使用技術・言語」→「必要モジュール・環境」→・・・といった感じで逆算しながら考えていく必要があります。野球選手も「メジャーでプレーする」→「まず日本球界で活躍」→「一軍レギュラー」→「プロ入団」→「高校で活躍」→・・・とゴールを明確にしている選手ほど活躍されている印象です。

とりあえず「少ない情報から仮説を立てる」必要があります。ここに正確な精度は不必要で「おおよそ合っていたら」でいいのです。狂い出したら新しくプランBを構築します。そうする事で自然に情報感度も向上して、さらに正確な仮説を構築できるみたいです。

練習として競技プログラミングを勉強します。問題から結論へ至るまでの論理仮説を構築して、実装する習慣がつきます。瞬時に「ああこれだと実行時間オーバーするな」と計算量を計算できる能力も身につきます。

全体から考える力

「結局、何が言いたい？」って言われたりする事ありません？よく言われるんですよね。面接とかで。

ホストが好きでホスト系Youtuberの動画をよく見てるんですけど、やっぱり話術の達人ですよね。話の全体像が分かりやすいです。

「結論」→「大まかな話の流れ（ストーリー）」→「ストーリーを分解、具体的な話」

こんな感じで話されているので、復習を2度しながら話を聞いている感じになります。
「結論」と「大まかなストーリー」が最初にくることにより、話の中で「いつ終わるか分からない」恐怖がかなり薄れます。

(⌒,_ゝ⌒)ワイ「そんなんいきなり出来へんわ」

自分の中の相対座標より絶対座標で考えます。

(⌒,_ゝ⌒)ワイ「は？何言うてんねん、コイツ」

個人的には達観した感じで神になったつもりでいるのがいいかもしれません。「前でゴミを捨てた人」がした時、安易に「その人が悪い」と決めつけてもいいのでしょうか。

「ゴミを捨てた人」に着目するのでは無く、社会全体について考えます。

「ゴミを捨てる場所がない」「ゴミを捨ててはいけないと言う事が周知されていない」「ゴミで手が汚れやすく捨てたい気持ちでいっぱい」といった様々な切り口で考えると、背景がいくらでも考えられますね。

普段から取り組む仕事でも全体を把握しながら活動を進めると良いそうです。

単純に考える力

「自分が伝えたい事を全部伝えようとしてしまい、結局何も印象にない」と言うことがありませんか？
自分も研究活動報告でそんな感じでしたね・・・

情報量が多い場合、話の本質が見えにくくなります。話が上手い人って難しい話でも分かりやすいですよね。イメージするなら塾講師とかです。

塾講師の人って「難しい内容を身の回りの何かに例えがち」な気がします。情報の枝葉を削ぎ落として、身の回りの何かに抽象化しているんです。抽象化するには「難しい情報」と「身の回りの何か」との間の共通点（これが本質）を導き出しています。本質以外の情報は一旦削ぎ落としていますよね。

(⌒,_ゝ⌒)ワイ「どうすればそんなん出来ねん」

本のレビューとかします。本って情報量多いですし、本質を見つけて要約する事が必要です。そこから自分に落とし込んで考える事に抽象化スキルを適用できますよね。

まとめ

以下の事をすると良いそうです。

  • 仮説を立てて考える力 → 競技プログラミングで手を動かす前に仮説を立てて実装
  • 全体から考える力 → 「結論➡︎全体を大まかに➡︎具体的」を意識して話す
  • 単純に考える力 → 難しめの本のレビュー