2020-08-05

Data Science: R Basics受講してみた

統計でRを使いたいと思っていたので、前から気になっていたData Science: R Basicsを受講開始しました。セクション４までありますが、１を終えた感想は、

RやRStudioのインストールから教えてくれる。
使い方は基本から教えてくれ、分かりやすい。
Data Campのプラットフォームで練習できる。

極めてコンパクトにまとまっているので、すべてを含めて、６時間くらいで終えられそうな感じです。

2020-08-03

AtCoder茶色になりました。

ついに灰色脱出！

本日、ABD問題を解いて、茶色になれました。

Cはオイラーの定理で制約があるのか！全然しらなかった。

Eも冷静に二分探索すれば解ける問題でした。

次は４問解きたい！

2020-08-01

edxでCS50受講しました！

f:id:poohandduffy:20200801043224p:plain

こんな感じの認定書もらいました。

内容は、C言語の基本、パイソン、SQLがカバーされていて、毎回ぎりぎりなんとかなる程度の難易度の課題が出され、提出して正解しないと修了できません。正直時間はかかりましたが、コンピューターサイエンスの未経験でもこのレベルまでできるようになるとは、素晴らしい講座だと思います。こんな講座が無料で受けられるなんて本当に素晴らしい！Cを学ぶことで、パイソンで以下に楽させてもらっているか、コンピューターに負荷がかかっているか分かりました。

最後の選択プロジェクトでは、いくつかのプロジェクトから選択できます。最初、アンドロイドのアプリを作成するプロジェクトを選択したのですが、ゼロからJAVAを学んで、アプリを作るところまでを一回でカバーするのはさすがに無理で、LUAという言語でゲームを作って終了しました。

次は、CS50's Introduction to Artificial Intelligence with Pythonを受けてみようと思います。

2020-06-14

東京海上日動プログラミングコンテスト2020 C問題解けず…

東京海上日動プログラミングコンテスト2020、２完して少しレートが上がりました。３問目は、プログラム自体は書けたのですが、タイムアウトしてしまいました。終わった後も検討したのですが、改善せず。誰か教えてください！！

f:id:poohandduffy:20200614114052p:plain

問題文

数直線上に電球が $N$ 個並んでおり、電球には左から順に $1$ から $N$ までの番号がついています。電球 $i$ は座標 $i$ にあります。

電球には光の強さを表す非負整数値が定まっており、座標 $x$ に光の強さ $d$ の電球があるとき、その電球は座標 $x - d - 0.5$ から座標 $x + d + 0.5$ までの区間を照らします。初めは電球 $i$ の光の強さは $A_{i}$ です。そこで、以下の操作を $K$ 回繰り返し行います。

$1$ 以上 $N$ 以下の各整数 $i$ に対し、操作時に座標 $i$ を照らしている電球の個数を $B_{i}$ とする。そして、各電球 $i$ の光の強さを $B_{i}$ に変更する。

$K$ 回の操作を行った後の各電球の光の強さを求めてください。

制約

$1 ≦ N ≦ 2 \times 10^{5}$
$1 ≦ K ≦ 2 \times 10^{5}$
$0 ≦ A_{i} ≦ N$

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $K$ 
 $A_{1}$   $A_{2}$   $\dots$   $A_{N}$

出力

$K$ 回の操作を行った後の電球 $i$ の光の強さ $A {^{'}}_{i}$ を、以下の形式で標準出力に出力せよ。

 $A {^{'}}_{1}$   $A {^{'}}_{2}$   $\dots$   $A {^{'}}_{N}$

入力例 1 Copy

Copy

5 1
1 0 0 1 0

出力例 1 Copy

Copy

1 2 2 1 2

始めに座標 $1$ を照らしている電球は電球 $1$ のみであるので、操作後の電球 $1$ の強さは $1$ になります。また、始めに座標 $2$ を照らしている電球は電球 $1$ と電球 $2$ であるので、操作後の電球 $2$ の強さは $2$ になります。

入力例 2 Copy

Copy

5 2
1 0 0 1 0

出力例 2 Copy

Copy

3 3 4 4 3

イモス法で解いたのですが…


import sys
n, k = map(int, sys.stdin.readline().rstrip().split())
an = list(map(int, sys.stdin.readline().rstrip().split()))

import numpy as np

t= min(k, 45)

for _ in range(t):
　bn = [0]*n
　for i in range(n):
　　bn[max(i - an[i], 0)] += 1

　　if i+ an[i]+1 <n:
　　　bn[i+an[i]+1] -=1
　an = np.cumsum(bn)

print(*an)

2020-06-01

ABC 169　４完しました。

ABCDの４完をして、パフォーマンス９６６。１０級に昇級しました。

f:id:poohandduffy:20200601010007p:plain

Cが最後までなぜか通らなくて、Decimalを使って解決しました。

import decimal
d = decimal.Decimal('1.1')

素因数復習！

n= int(input())

factors=[]

for i in range(2, int(n**(0.5))+2):
    if n%i == 0:
        cnt=0
        while n%i==0:
            cnt+=1
            n //=i
        factors.append([i,cnt])
if n!=1:
    factors.append([n, 1])

print(factors)

2020-05-31

AtCoderコンテスト２回目

NOMURAプログラミングコンテスト2020でABを完答して、レートが88に上がりました！

f:id:poohandduffy:20200531052043p:plain

C問題は、最後に解法（ノードの上限に制約があること）を思いついたのですが、時間切れ。

明日もあるので、頑張ります！

2020-05-26

うぉー、ついに自力で解けないB問題に遭遇。ABC 128 B

最後に残していたB問題。う、解けない…

リストinリストのソートです。

B - Guidebook /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : $200$ 点

問題文

あなたは美味しいレストランを紹介する本を書くことにしました。あなたは $N$ 個のレストラン、レストラン $1$ 、レストラン $2$ 、 $\dots$ 、レストラン $N$ を紹介しようとしています。レストラン $i$ は $S_{i}$ 市にあり、あなたは $100$ 点満点中 $P_{i}$ 点と評価しています。異なる $2$ 個のレストランに同じ点数がついていることはありません。

この本では、次のような順でレストランを紹介しようとしています。

市名が辞書順で早いものから紹介していく。
同じ市に複数レストランがある場合は、点数が高いものから紹介していく。

この本で紹介される順にレストランの番号を出力してください。

制約

$1 \leq N \leq 100$
$S$ は英小文字のみからなる長さ $1$ 以上 $10$ 以下の文字列
$0 \leq P_{i} \leq 100$
$P_{i}$ は整数
$P_{i} \neq P_{j}$ $(1 \leq i < j \leq N)$

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $S_{1}$   $P_{1}$ 
 $:$ 
 $S_{N}$   $P_{N}$

出力

$N$ 行出力せよ。 $i$ 行目 ( $1 \leq i \leq N$ ) には、 $i$ 番目に紹介されるレストランの番号を出力せよ。

入力例 1 Copy

Copy

6
khabarovsk 20
moscow 10
kazan 50
kazan 35
moscow 60
khabarovsk 40

出力例 1 Copy

Copy

$3$ 種類の市名は辞書順で kazan $<$ khabarovsk $<$ moscow です。それぞれの市について、点数が高いレストランから順に紹介されていきます。よって、レストランは $3, 4, 6, 1, 5, 2$ の順に紹介されていきます。

こちらのサイトからカンニング。

scrapbox.io

N = int(input())
L = []

for i in range(N):
S, P = input().split()
P = int(P)
L.append([S, P, i])

L = sorted(L, key=lambda x: (x[0], -x[1]))

for i in range(N):
print(L[i][2] + 1)

なるほど！sortedってそんな風につかえるのか！

まあ、最悪、２回ソートすればできるっちゃできる。