AtCoder茶色解く5

今回解くのはこちら
D - Replacing

問題が複雑なので、実際の例をみて考えます。

まず、以下が入力で与えられます。

4
1 2 3 4
3
1 2
3 4
2 4

この時、配列1 2 3 4に対して、3回の操作を行います。
1を2に、3を4に、2を4にすると、それぞれ

2 2 3 4 = 11
2 2 4 4 = 12
4 4 4 4 = 16 

となります。

また、
配列の数、配列の取りうる数、取り替える数、変更値のすべてが10^5の範囲となります。
よって、2重ループでは時間が足りないので、何か工夫を考えます。

ここで、元の配列にそれぞれの数が何こずつ存在するかをハッシュで記憶しておくと、
そのハッシュ値を元に変更しながら計算できるのではと考えました。

流れとしては以下です。
・配列を取得
・配列の各値がいくつあるか値:個数でハッシュに格納、さらに合計値を計算しておく
・for文で、置換する値を受け取り、ハッシュの値を書き換える 書き換えた結果を元に再計算

これを繰り返していけばいいはず。
実装は以下です。

N=int(input())
A=list(map(int, input().split()))
l={}

# Aの数をまとめておく
for i in A:
  if i not in l:
    l[i]=1
  else:
    l[i]+=1
sum=sum(A)
#print(l, sum)

M=int(input())
for i in range(M):
  B, C = map(int, input().split())
  if B in l:
    bef=l[B]*B
    aft=l[B]*C
    if C in l:
      l[C]+=l[B]
    else:
      l[C]=l[B] 
    l[B]=0
    #print(l,sum, bef, aft)
    sum=sum-bef+aft
  print(sum)

サンプルでちょっとNGがあったので、処理を増やしています。
前回覚えた差分更新が早速役に立ちました。

AtCoder茶色解く4

今回解くのはこちら
D - Floor Function

floor(t)は、実数t以下の最大の整数とのこと。
問題のイメージがつきづらいので、実際にいくつか例をもって計算してみます。
A=5, B=7, N=4のとき
Ax/B, x/Bの値は

x=1, l=floor(5/7)=0, m=floor(1/7)=0  l-5*m=0
x=2, l=floor(10/7)=1, m=floor(2/7)=0 l-5*m=1
x=3, l=floor(15/7)=2, m=floor(3/7)=0 l-5*m=2
x=4, l=floor(20/7)=2, m=floor(4/7)=0 l-5*m=2

Nが10**12なので、通常のfor文では実行時間が間に合わないと判断、
nの数を減らせる工夫を考えます。

ここで、xが7の倍数になるとき、mの値が増加します。
それに合わせて、計算式も単調増加から一時的に減少に転じます。
よって、最大値を求めるとしたらxが7の倍数-1, 7の倍数のとき、およびNに一致したときと考えます。

例えばN=15だとすると、
x=6, 7, 13, 14, 15について計算ができればいいと思われます。

この場合は、

i = N//7 # 2になる
for x in range(i):
  x1 = x*7-1
  x2 = x*7
xn = N

となるはず。

...
と思ったのですが、ちょっとうまくいかなかったので参考資料をたよりに再確認
AtCoder ABC 165 D - Floor Function (400 点) - けんちょんの競プロ精進記録

周期性を見るためにもう一度手計算してみると。。。。

x=1, l=floor(5/7)=0, m=floor(1/7)=0  l-5*m=0
x=2, l=floor(10/7)=1, m=floor(2/7)=0 l-5*m=1
x=6, l=floor(30/7)=2, m=floor(6/7)=0 l-5*m=2
x=7, l=floor(35/7)=2, m=floor(7/7)=0 l-5*m=0
x=13, l=floor(65/7)=2, m=floor(13/7)=0 l-5*m=2
x=14, l=floor(70/7)=2, m=floor(14/7)=0 l-5*m=0

たしかに周期性があるため、この例でいえばx=1~6 (B-1)までで試せばよい。
また、その数は増えていくのだから、
NがB-1を超えた場合はB-1の値、NがB-1以下であればxの最大値で計算すればよい。

A, B, N = map(int, input().split())

min = N
if N > B-1:
  min = B-1
print(A*min//B - A*(min//B))

ということで、完成。
一見不思議な形の数式については、具体的な値を入れて法則を見出すことにする。
今回も、きちんと出力値を出していれば答えの周期自体に気づけたはず・・・精進します。

AtCoder茶色解く3

今回解くのはこちら
C - Skill Up

本を購入するしないの2通りを全本の組み合わせに対して行うbit全探索であると推測、
進めていきます。

12冊の本を買ったか買っていないかでフラグ管理するとすると、
2^12=4^4=16^2=256通りで試せばいいことになります。

例えば以下のサンプルがある場合

3 3 10
60 2 2 4
70 8 7 9
50 2 3 9

n=5の場合、2進数で表すと101となります。
60 2 2 4と50 2 3 9が1となり採用され、残りの1行は採用されません。
それぞれの値は配列(aとする)に足しこまれます。

a=[60 2 2 4]+[50 2 3 9]=[110 4 5 13]となります。
その後、これらを比較し、a[1]~a[3]に対して必要スキルレベル以上かどうかを判定します。
今回は10に届かないので、この値は破棄します。

n, m, x = map(int, input().split())
inp=[]

# 入力をすべて受け取る
for i in range(n):
  tmp = list(map(int, input().split()))
  inp.append(tmp)

# bit全探索を行うための箱づくり
sum = 0
min = 10**10
for i in range(2**n):
  tmp = [0]*m
  flg = 0
  
  # ある買う買わないのケースに対して、フラグが立ってたらスキルポイントを増やす
  for j in range(n):
    if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
      sum += inp[j][0]
      for k in range(1,m+1):
        #print(n,j, k, tmp, inp)
        tmp[k-1] += inp[j][k]
  for ii, k in enumerate(tmp):
    if k < x: # x未満ならflgをたててNGとする
      flg = 1
      break
  #print(tmp, flg)
  if sum < min and flg == 0: min = sum
  sum = 0
  
if min == 10**10: min = -1
print(min)

bit全探索自体を作るのに時間がかかってしまったので、ほかの問題も解いてコツをつかみたい

AtCoder茶色解く2

今回解くのはこちら
D - Banned K

Nの数は2*10^5が上限
Aの数は1~Nまで

まずは簡単にするために、すべてのAを数え上げて記録する

N = int(input())
A = list(map(int, input().split()))
di = {}

for a in A:
  if a not in di.keys(): # diに何もなかった場合
    #print("add")
    di[a] = 1
  else:
    #print("sum")
    di[a] += 1
#print(di)


さらに、得られたまとめデータをもとに各Aに対してfor文を回す

# 組み合わせ計算
sum = 0
for k in A:
  for a, b in di.items():
    if a == k: b -= 1
    #print(a,b)
    sum += int((b*(b-1))/2*1)
  print(sum)
  sum = 0

一部がTLE出ている
よって、最適化を行っていく

まずは、計算結果をメモするように変更した

# 組み合わせ計算
sum = 0
ll = {}
for k in A:
  if k not in ll.keys():
    for a, b in di.items():
      if a == k: b -= 1
      #print(a,b)
      sum += int((b*(b-1))/2*1)
    print(sum)
    ll[k] = sum
  else:
    print(ll[k])
  sum = 0

これで一部高速化でき、ACの数は増えたが、以前TLEが存在する状況であった。

ここで、以下記事を参考に考え方を変えた
AtCoder ABC 159 D - Banned K (400 点) - けんちょんの競プロ精進記録

愚直に毎回の数列について計算したのでは O(N2) の計算量を要してしまう。今回のような、各 k について、それを除いたものについて考えるタイプの問題では

まず全体の数列についての答えを求めておいて
各要素を取り除くことによる「影響」を計算し、
その影響分を引く

先に組み合わせ数の計算値を求めておき、そこから各パターンを追加で計算する。
差分更新というやり方らしい

これで書き換えたものが以下

N = int(input())
A = list(map(int, input().split()))
di = {}

for a in A:
  if a not in di.keys(): # diに何もなかった場合
    #print("add")
    di[a] = 1
  else:
    #print("sum")
    di[a] += 1

# 全体量計算
sum = 0
for a, b in di.items():
  #print(a,b)
  sum += int((b*(b-1))/2*1)
  
# 組み合わせ計算
for k in A:
  n = di[k]
  bef = n*(n-1)/2
  aft = (n-1)*(n-2)/2
  print(int(sum-bef+aft))

無事ACが取れました。

AtCoder茶色解く1

今回解くのはこちら
D - String Formation

特定のフラグがきたら特定の操作を行う
特定の操作は以下
1.手元のキューの順番を反転
2.手元のキューに要素を追加

ここで、1については実質やらなくてよい
なぜなら、1の操作で前後が入れ替わっても2回で元に戻るし、
1回入れ替えたあとに2の操作を行う場合はキューに入れ込む動作が前後逆になるだけだから

なので、方針は以下
・全体をデキューで実装、前と後ろどちらからでも入れられるようにする
・1が来たらフラグを立てる
・2が来たらそのあとの向きに応じてキューに入れる、フラグが立っていれば逆にする

from collections import deque
d = deque()
d.append("a")  # 右から入れる
d.appendleft("b") # 左から入れる

作ったサンプルが以下

from collections import deque
d = deque(input())
n = int(input())
p=[]
flg = 0
for i in range(n):
  p = list(input().split())
  #print(p)
  if p[0] == "1":
    flg ^= 1 # flg == 1 の場合は左右反転
    #print(flg)
  else:    
    if p[1] == "1": # 1の場合は先頭
      if flg == 1: # 1の場合は反転
        d.append(p[2])
      else:
        d.appendleft(p[2]) # 左から入れる
    else:
      if flg == 1:
        d.appendleft(p[2]) # 左から入れる
      else:
        d.append(p[2])
  
if flg == 1:
  d.reverse()
a =""
for i in d:
  a += i
print(a)

無事通りました、やったね

改善ポイントは・・・
・dequeの使い方が不慣れ
・bit演算(フラグ部分)不慣れ
・最後の出力部分が不慣れ

精進します

隙間活動し始めました2

とりあえず進めている数日
ここ何日かはまとまって勉強できる時間があまりなかった・・・
そして、隙間らしい隙間ではちゃんとした勉強なぞできないことを悟った(当たり前)

それから、いろいろな本の要約を見れるアプリを見つけた
試しに色々読んでみているが、効果はあるのだろうか・・・
とりあえず実践するいくつかのことは見つけた

その本によると、自分に足りないのはアウトプットだそう。
インとアウトが3:7でちょうどよい、らしい
俺の場合は確かにほとんど詰め込み系だから、なんとかしてアウトプットせねば

というわけで、それぞれの目標に対してアウトプットを考えてみた

HTB攻略...チートコード記載、WriteUp作成
 →上記をするため、アウトプットをきちんとメモする習慣をつけるべき
  →ログ機能を有効にしてすぐ追えるようにするor1挙動したらメモする癖をつける

バグバウンティ...ログ、やったことメモ、勉強した中身や思考の流れをメモ
 →これ自体はほとんど実践な気がするのですべてアウトプットでは。
 
徳丸本勉強...メモ、VMでの動作確認、不明点の深堀り
 →教科書なのでインプットに重きを置きがち
  →せっかく色々試せるようになっているので演習をきちんと理解しながら進めること

外国株式勉強...メモ、周囲に話して理解を深める
 →周りに話すことで記憶の定着を図る
  →まわりも巻き込めるくらい魅力やメリデメを認識しておくこと!

AtCoder勉強...解いた問題の復習!!!
 →解いて終わりが多すぎる、解けた問題自体も考え方を解説見て学ぶべし
  →さらに言えば、公式以外の有名な人らの解説も見て真似てみる

機械学習勉強...メモ、環境構築等手順化
 →当面は環境作成するあたりだと思うので、再現性のある手順構築をする
  →手順書作るの苦手なので意識して作るようにする

統計学勉強...メモ、何かの問題集とか解く
 →これもインプットばっかりなので、きちんと理解したことを解いて示したい
  →ぶっちゃけ学生向けの問題集とかでもいいかも、ネットで探して解いてみる

ほとんどメモですかねぇ
メモが本当にただのメモになりがちなので、何等かの形できちんと残したい

続、やりたいこと2

前回の続き

syachineko.hatenablog.com

 

思ったけど、

自由時間としてとってる3時間って、全体的に部屋が暗いんですよね・・・

なので書籍を読むのがちょっと大変

それを加味してタイムスケジュール考えなければならないな 

 

HTB攻略

U...3 D...3 T...5

O...チートシート、資格(OSCP)、称号

10時間ほど 

PCさえあればいつでもできる、隙間時間にも大いに取り組むべき

 

・バグバウンティ

U...4 D...5 T...5

O...見つかれば報奨金、知識メモ

20時間 

PCさえあれば大丈夫だが、まとまった時間があったほうがいいかも

 

・徳丸本勉強

U...4 D...2 T...3

O...資格(徳丸試験)

24時間 

紙の本なので、明かりが必要、できれば朝のタイミングで進めたい、あとちょこちょこまとめる必要があるのでそのときはPC必要

 

 

・外国株式投資勉強

U...5 D...3 T...4

O...ポートフォリオ、お金

15時間 

必要に応じて紙の資料とか見ないといけないし、場合によっては話を聞くような必要もあるかも

これはもはや日中の3時間以外のところにもってくるしかない?

 

AtCoder(アルゴリズム)勉強

U...4 D...3 T...3

O...レート

10時間

教材で学ぶならいらないが、オンラインとなると時間を合わせないといけないので現実的でない・・・

 

機械学習勉強

U...3 D...4 T...4

O...資格、業務知識(可能性、kaggle

10時間

某友人の助けを借りるなどしてとりあえず環境構築だけする

PCがあれば大丈夫だが、これもタイミングあわせないとならぬ

もしくは教材だけでいけるのか・・・?

まず相談したいな 

 

統計学勉強

U...5 D...2 T...3

O...資格、業務知識(可能性

20時間

媒体によるが、本なら朝方に回りそう、でも今から買うならKindleにすれば夜中でも読める

あとは社内のコンテンツを覗いてみる(一応業務にかかわるかもしれないので)

 

 

以上をまとめると

朝やる

・徳丸本

・外国株式勉強(保険、お金の話含む)

 

要調整

機械学習

AtCoder

・確率統計学

 

どこでも

HTB

・バグバウンティ

 

となりそう

これをもとにタイムプランを立ててみる

 

以上