絶記

絶起の記録です

2020/5/31バチャ反省

百年くらい競プロしていなかったのでバチャをしました。最近レートを上げる気力が無いのでコンテストに出ずあとで解いたりしています。そのうちやる気が出たら再開します。

バチャ

リンク

茶色diff*6, 緑diff*4問でやってみました。

結果

f:id:nanigasi_san:20200531020746p:plain 1時間9完でした。Lampムズ過ぎてウケる。全体的には茶色でバグらせがちだったかな？

解説

すぬけ君の塗り絵 2 イージー

方針と実装

黒ではなく、白の範囲について考えます。すなわち、白の長方形を構成する4頂点を更新していきます。では実装していきます(雑)

まず、xyそれぞれの左端と右端を初期化します。左端をl、右端をrとすると x_l = 0, x_r = W, y_l = 0, y_r = Hです。

次に、各aについて問題文の通りに更新していきます。

最終的な4頂点からなる長方形の面積が答えですが、左端が右端を超えているときに辺の長さを0にする処理を忘れるとバグるので気を付けましょう

提出

atcoder.jp

Attention

西と東を間違えていて一生バグらせていました(恥ずかしい)

方針と実装

N \leqq 3\times10^ 5なので、全点に対して毎回計算していてはO(N^ 2)になってしまい間に合いません。こういう時は前計算してから各点について細かい更新をしていくのがセオリーです。

ある人がリーダーになった時に、その人が振り向かせる必要があるのは「自分より西にいて西を向いている人」と「自分より東にいて東を向いている人」です。

一番西にいる人がリーダーの時を考えると、「自分より西にいて西を向いている人」は当然0人です(まず人がいません)。「自分より東にいて東を向いている人」の人数は、「東を向いている人」から自分が東を向いているかどうかを引くことで求められます。

すると、一番西の人がリーダーの時の答えは「0(自分より西にいる西を向いている人数)」 + 「全体のうち東を向いている人数」 - 「自分が東を向いていたら1, 西を向いていたら0」とおけます。

答えを計算したあとは、自分が西を向いていたら「自分より西にいる西を向いている人数」に1を足します。次の人にとって自分は「自分より西にいる西を向いている人」だからです。

二番目以降の人については、

  • 自分が東を向いていたら「自分より東の東を向いている人数」を1減らす
  • 答えを小さい方に更新する(どのリーダーについても、西西+東東で求められます)
  • 自分が西を向いていたら「自分より西の西を向いている人数」を1増やす

を繰り返していくことで、答えが求まります。

提出

atcoder.jp

怪文書

方針と実装

各文字列で使われている文字と回数を集合に見立てて、その積集合を取ればよいです。

Pythonのsetは重複を許さないので、Counterを使いました。

バグったポイントとしては、更新するときにA-Zの全てのアルファベットについて更新していかないとダメです(初回だけ出てきたアルファベットがあると、それが使用可能と判定されてしまう)

提出

atcoder.jp

引越しできるかな？

方針と実装

ある目線から見たときに最悪の状態を再現して、それの最大値を取ります。

めちゃくちゃふわっとした言い方になってしまいました。x <= y <= zになるように箱をみて、それぞれの軸について最大値であるようなサイズの箱を用意すればよさそうです(証明ができません、直感で戦っていこうな)

実装するうえでは、荷物のサイズをソートして箱のサイズをmaxで更新していきます。

提出

atcoder.jp

Streamline

方針と実装

ある点X _ iからX _ {i+1}に行くためのコストはX _ {i+1}-X _ iです。ランダムにいくより一番近い点に行ったほうが全体的なコストが抑えられるのは自明なので、Xは事前にソートしておきましょう。

次に、N個の駒があるということについて考えてみます。Xはソート済みなので、当然各駒が交差するような動き方は最適ではありません。[1, 2, 3, 4]と並んでいるときに、(1->3)と(4->2)という動き方をさせるよりは(1->2)と(3->4)の方がコストが小さく済むからです。こう考えると、M個のマスからなるM-1個のコストを、全体でN個に分割できるということが分かります。この時、分割された狭間については移動が必要ないので、その分のコストを消費する必要がありません。(上の例でいう(2->3))

次に、各iについてX _ {i+1}-X _ iのコスト(M-1個になります)を計算します。すると、この問題は「M-1個のコストがあり、それをN個まで消すことができる。残ったコストの総和を求めよ」と言い換えることができます。

終わりです。

提出

atcoder.jp

Make a Rectangle

方針と実装

長い奴から使っていきます

提出

atcoder.jp

Boxes and Candies

方針と実装

まず、左端にx個以上あってはいけません。max(a _ 0, x)に調整します。

a _ 1以降については、 a _ i + a _ {i-1} \leqq xを満たすようにa _ iを調整していけばよいです。このようにしていくと、「xを超えているときはxに」「超えていないならそのまま」にするので、必要以上に削ること無く条件を満たすことができます。

提出

atcoder.jp

2017-like Number

方針と実装

list _ i := iが2017に似た数かどうか(0, 1)となるような配列を計算し(僕はエラトステネスの篩を使いました)、これの累積和を取ります。

この前処理によって、各クエリについて累積和[r-累積和[l-1]]で計算ができます。

提出

atcoder.jp

Switches

方針と実装

bit全探索によって全通りのスイッチを試すことができ、それぞれ問題文の通りに計算して全部の電球がついた回数が答えです。

提出

atcoder.jp

感想

Lampは知らん

水色そろそろ解いたほうがいいな

PAST2-H (1-9 Grid)をDPと拡張BFSで通す

これは何か

PAST2をやっていたらHが全く解けず、競プロ鯖で聴いたら強い方がたくさん教えてくれたので2つの解法についてコードとともに解説する記事です！

問題リンク

atcoder.jp

問題文と制約

f:id:nanigasi_san:20200523022316p:plain
問題文
f:id:nanigasi_san:20200523022302p:plain
制約

自分の考察

解こうとしながらいくつか考えてたことがありました。そのうちいくつかは的外れだったのですが、一応書いておきます。

(少なくとも方針は)合っていた考察

経路に出てくる1~9のループは一順

問題文より、経路に1~9のループが1巡以上含まれていないといけませんが、これが二巡するとしたら1順目の9の次に最短経路でGに行けばよいので、もし二巡目以降が9->Gの最短経路と同じなら無視してもよく、それ以外なら通らない方が経路が短くなります。

グリッド上のBFSを使って解く

グリッド上のある点sからある点tに行くのは、BFSで最短距離が求められます。

ここで罠があって、いつもグリッド上を探索するときは障害物(つまりは通れない点)があるのでBFSが必要ですが、今回の場合は障害物がないので、最短距離は必ずabs(s_x - t_x)+abs(s_y - t_y)で表せます。これを使うと後述するDPをすることができます。

BFSをしながらDFSをすると解ける

後述しますがこの発想に至る前に一度「S->1」の最短経路を求める、その1の座標を使って「1->2」の最短経路を求める....といった方針でWAしました。サンプルは通っていたのでもっと一般化することで通せると思い、これにたどり着きました。ざっくり言うと「Sから出発して、1を見つけたらそこからいける2を探す」というのを再帰的に続けて、最終的に「8から出発して、9を見つけたらそこからいけるGを探す」「そのGに至るまでの列挙された経路のコストの最小値が答え」という感じです。

結論から言うとこれは合っているのですが、直感に頼って出てきた方針だったので実装が浮かびませんでした...(競プロ鯖の方の力を借りてこれでACすることもできました。)

間違っていた考察

貪欲にBFS

ダメです。反例は 1S213456789G です(初手で右に行くのが最適だが貪欲BFSでは左に行ってしまう)

ここで諦める

分からなくなった、というか、「BFSしながらDFS」の実装ができなくて諦めました。

解説を開いたら「DPだよ」って書いてありましたが、グラフ問として解きたかったので競プロ鯖で質問してみました。(DP解法についても下の方にまとめてあります)

f:id:nanigasi_san:20200523024153p:plain
暖色の方が丁寧に教えてくださってめちゃくちゃわかりやすかったです

  • なぜ貪欲BFSが通らないのか
  • BFSでやるのはひと工夫いる

ということを教わり、square1001氏がまずは JOI - チーズという問題を解くといい、と教えてくれました。

これは今回の各数字が一つしかないバージョンだったので、僕が考えた貪欲BFSでも通りました。これは目標がN個ある場合、N回のBFSが必要になる解法です

ところがsquare1001氏によると

  • この問題は一回のBFSでも解ける
  • その解法がこのPAST2-Hにつながるヒントになる

ということだったので、考えてみました。有向グラフとして見るとか、始点から各目標への経路のうち交差している部分を引く、とかいろいろ考えたのですが結局わかりませんでした。ギブアップです。ということで以下答え合わせです。

以下解法の話です(ただし、まずはチーズについての解答です)

グラフを拡張する

「グラフを拡張してBFS」というのが答えでした。最初どういう意味かよくわからなかったのですが、しの氏に丁寧に解説を受けてやっと理解できました。

僕のやった貪欲BFSというのはつまり、点sから点tへの最短経路を求めるたびにグラフを使い捨てて新しいものに変えていました。絵で描くと下のようなイメージです f:id:nanigasi_san:20200523025611p:plain

これを、縦に積みます f:id:nanigasi_san:20200523025816p:plain

ここで大事なのですが、本質的には横に並べても縦に並べても違いありません。これはイメージの問題であって、本当のバグっていた点は「使い捨てにしていた=一枚のグラフで1ペア分の最短経路しか計算していなかった」です。すなわち、この操作の本質は「N個のグラフ」として扱っていたものを「一つのグラフ」として統合して考えるということです。元のグラフから見ると頂点と辺を拡張しているといえるので、「グラフの拡張」と表現されているようです。

さて、では一つのグラフとしてみることで何ができるようになったかを見ていきます。(まだ話は「チーズ」についてです)

先ほどは(S, 1)や(1, 2)などのペアそれぞれについてグラフを用意してBFSをしていましたが、この操作のおかげで一つのグラフの探索で始点から終点までの最短経路が求められるようになっています。
三次元グリッドの探索なので二次元の時と比べて実装を少しだけ変更する必要があります。具体的には

  • 頂点の表現方法
  • queueへの頂点の追加

が少しだけ変わります。どういうことか説明していきます。

頂点の表現方法

このグラフでは同じグリッドが何枚も重なっています。それぞれのグリッドの頂点は(x, y)の二次元タプルで表されますが、ここに階層の情報を追加する必要があるので、

頂点(x, y, level) := 下からlevel層目の(x, y)

を表すと定義します。これが一つ目の(小さな、しかし大事な)変更点です

queueへの頂点の追加

もう一つの変更点は、queueへの頂点の追加の際の条件分岐と追加する情報そのものです。僕は普段二次元グリッドに対するBFSの頂点追加部分を以下のように書いています

nxy = (nx, ny) # (x, y)から行ける点
if nxy in seen:
    continue
elif graph[nx][ny] == ".":
    dis[nxy] = dis[(x, y)] + 1
    if nxy not in seen:
        todo.append(nxy)
        seen.add(nxy)

これを以下のように変更します

if (nx, ny, level) in seen:
    continue
elif graph[nx][ny] == "X":
    continue
elif graph[nx][ny] == str(N) and level==N-1:
    return dis[(x, y, level)] + 1
elif graph[nx][ny] == str(level+1):
    nxy = (nx, ny, level+1)
    dis[nxy] = dis[(x, y, level)] + 1
    if nxy not in seen:
        todo.append(nxy)
        seen.add(nxy)
else:
    nxy = (nx, ny, level)
    dis[nxy] = dis[(x, y, level)] + 1
    if nxy not in seen:
        todo.append(nxy)
        seen.add(nxy)

5つの条件分岐と処理をざっくり説明すると、

  1. その頂点が訪問済み
    • 何もしない
  2. その頂点が障害物(侵入不可能)
    • 何もしない
  3. その頂点の値がゴールの値 かつ 今いる階層がゴールの層-1
    • その頂点までの最短距離を返す
  4. (2に当てはまらない かつ )その頂点の値が今いる層+1
    • 今いる頂点(x, y, level)から一層上の点(nx, ny, level+1)に辺を張る
    • その頂点が訪問済みで無いなら
      • その頂点をqueueに追加する
      • その頂点を訪問済みにする
  5. それ以外
    • 今いる頂点(x, y, level)から同じ層の点(nx, ny, level)に辺を張る
    • その頂点が訪問済みで無いなら
      • その頂点をqueueに追加する
      • その頂点を訪問済みにする

といった感じです。

ちなみに僕の実装だと制約的にMLEを起こすのでPythonの場合delをしないと通らないという欠陥があります(3次元リストを使うなどでどうにかしてください)

ここまで前置きです

前置きがめちゃくちゃ長くなってしまいました。では実際にPAST2-Hを通していきましょう

僕が把握している二つの解法でこの問題を解いていきます。まずはここまで用意を進めた拡張グラフに対するBFSからです。

拡張したグラフに対するBFS

BFS部分の実装

def bfs_gird(graph, start, x_lim, y_lim):
    seen = {start}
    todo = deque()
    todo.append(start)
    dis = {start: 0}

    one_steps = ((1, 0), (-1, 0), (0, 1), (0, -1))
    while todo:
        x, y, level = todo.popleft()
        for dx, dy in one_steps:
            nx, ny = x + dx, y + dy
            if not ((0 <= nx < x_lim) and (0 <= ny < y_lim)):
                continue
            if (nx, ny, level) in seen:
                continue
            elif graph[nx][ny] == "G" and level==9:
                return dis[(x, y, level)] + 1
            elif graph[nx][ny] == str(level+1):
                nxy = (nx, ny, level+1)
                dis[nxy] = dis[(x, y, level)] + 1
                if nxy not in seen:
                    todo.append(nxy)
                    seen.add(nxy)
            else:
                nxy = (nx, ny, level)
                dis[nxy] = dis[(x, y, level)] + 1
                if nxy not in seen:
                    todo.append(nxy)
                    seen.add(nxy)

    return -1

簡単に言うと「S(始点)の座標(x, y, level)とグラフ」を与えて、存在するなら「S->1->2->3->4->->6->7->8->9->G」となる経路のうち最短のものの手数をBFSで探索して返します。存在しない場合(この順でGにたどり着けなかった)場合は-1を返します。

実装を見ればわかると思いますが、同じグリッドが10層(始点がS~9)重なっているのでグラフを表す二次元リスト自体を10倍する必要はありません。

提出とソースコード

atcoder.jp

N, M = map(int, input().split())
graph = [list(input()) for _ in range(N)]

from collections import deque


def bfs_gird(graph, start, x_lim, y_lim):
    seen = {start}
    todo = deque()
    todo.append(start)
    dis = {start: 0}

    one_steps = ((1, 0), (-1, 0), (0, 1), (0, -1))
    while todo:
        x, y, level = todo.popleft()
        for dx, dy in one_steps:
            nx, ny = x + dx, y + dy
            if not ((0 <= nx < x_lim) and (0 <= ny < y_lim)):
                continue
            if (nx, ny, level) in seen:
                continue
            elif graph[nx][ny] == "G" and level==9:
                return dis[(x, y, level)] + 1
            elif graph[nx][ny] == str(level+1):
                nxy = (nx, ny, level+1)
                dis[nxy] = dis[(x, y, level)] + 1
                if nxy not in seen:
                    todo.append(nxy)
                    seen.add(nxy)
            else:
                nxy = (nx, ny, level)
                dis[nxy] = dis[(x, y, level)] + 1
                if nxy not in seen:
                    todo.append(nxy)
                    seen.add(nxy)

    return -1
for i in range(N):
    for j in range(M):
        if graph[i][j] == "S":
            start = (i, j, 0)
print(bfs_gird(graph, start, N, M))

関数の返す値は問題文で要求されているものそのものなので、Sの座標を探して関数に渡し(ここで(S_x, S_y, 0)にすることを忘れないようにしましょう)、返り値を出力すればよいです。

計算量(合っていないかもしれませんが一応考えます)

ちゃんとした解析の仕方をしらないので直感的に考えます。

ある層iから層i+1までBFSをするとき、最悪なのは始点と終点が対角にある、例えば(0, 0)から(N, M)に思えます。その時は層iのグリッドすべてを探索することになります。僕はBFSの訪問済み頂点の管理にsetを使っているので、1頂点ごとに挿入にO(log(NM))かかって全体でO(NMlog(NM))でしょうか？ N, M\leqq50なので、10層分探索することを考えても十分余裕そうです。

実際53msで収まっています(Pythonでの話で、PyPyでは97msでした)

DP

実はこれが想定解です。正直検索すればたくさん解説が出てくると思うので後回しにしてしまいました。

公式解説

f:id:nanigasi_san:20200523041832p:plain

考察と方針

2点間の距離

かなり前半で示した(そして多分ここまで読むと昔のことなので忘れていると思う)のですが、今回のグリッドは障害物が無いので、ある頂点sから頂点tまでの最短距離はabs(s_x - t_x)+abs(s_y - t_y)で表されます。これは以下のような関数で求められます

def distance(s, t):
    return abs(s[0]-t[0]) + abs(s[1]-t[1])

組み合わせの全列挙

素直に考えれば1~9の値を持つ座標をそれぞれまとめて、それらの全ての組み合わせ(1, 2, 3, ..., 8, 9となる組み合わせのことです)に対してコストを計算すれば答えが出ることが分かります。和がSになるN個の数があるとき、それらの総積が最大になるのは(多分)それぞれS/Nとおいたときなので、1~9の各iについてNM/9個あるとすると、計算量は O((NM)^ 9)です。これでは到底間に合わないので、これを削っていきます。

各ステップで最適なもののみを選び取る

簡単のために、始点Sには0, 終点Gには10が書いてあるものとします。

0 -> 1

まず初めに、始点の0が書いてあるマスから1が書いてあるマスまでの最短経路を列挙してみます。0のマスの座標が(x_0, y_0)であり、1が書かれたマスがA_1個あるとすると、A_1通りの(座標, Sからの距離)のペアが作れます。0からそれぞれの座標までの最短距離は先ほど示した式で求めることができます。

1 -> 2

次に、1の書いてあるマスから2が書いてあるマスまでの最短経路の組み合わせを考えていきます。1が書いてあるマスはA_1個あり、2が書いてあるマスはA_2個あるとします。1が書いてあるマスから2が書いてあるマスへの最短経路はA_1 * A_2通りあることが分かります。A_1個のiそれぞれについて(2の書いてあるマスの座標, 1の書いてあるマスiからの最短距離)が計算できるからです。

このままでは結局O((NM)^ 9)になってしまいます

i -> i+1

ではここで一般化してiが書いてあるマスからi+1が書いてあるマスへの最短経路の数を数えてみましょう。素直に考えると、当然A_1からA_i+1までの総積です。

これを改善するために気づかないといけないのは、「iからi+1への遷移を考えるとき、i-1からiへの遷移がどうであったかは関係がない」ということです。

i-1が書いてあるマスからiが書いてある特定マスへの遷移はA_i-1通りありますが、そのiのマスからi+1の書いてある特定のマスへの遷移の時に使うのは、A_i-1通りある中の最小のコストだけでよい、ということです。なぜなら、どの座標から来ていたとしてもその後の遷移には影響が無いからです。

この性質を使うと、iの書いてあるマスからi+1の書いてあるマスへの遷移について考えるときにA_1からA_iまでの総積通り考えなければいけなかったものが、A_i-1*A_i通りだけ考えればよいことになりました。

説明がすこし複雑になってしまいましたが、この遷移は漸化式に落とし込むことができ、DPをすることができます。

漸化式

DP[x][y] := あるiが書いてあるマス(x, y)についての、i-1が書いてあるマスからの(Sからの移動の)累計移動回数の最小値

のように定義できます。(初期値は十分に大きい値にしましょう)

DP[x_0][y_0] = 0

とするのを忘れないようにしましょう。

提出とソースコード

atcoder.jp

N, M = map(int, input().split())
graph = [input() for _ in range(N)]
def distance(a, b):
    return abs(a[0]-b[0]) + abs(a[1]-b[1])
points = [[] for _ in range(11)]
for i in range(N):
    for j in range(M):
        if graph[i][j] == "S":
            points[0].append((i, j))
        elif graph[i][j] == "G":
            points[10].append((i, j))
        else:
            points[int(graph[i][j])].append((i, j))
inf = float("inf")
dp = [[inf for _ in range(M)] for _ in range(N)]
start = points[0][0]
dp[start[0]][start[1]] = 0
for i in range(1, 11):
    for point in points[i]:
        for prev in points[i-1]:
            dp[point[0]][point[1]] = min(dp[point[0]][point[1]], dp[prev[0]][prev[1]]+distance(point, prev))
goal = points[10][0]
print(dp[goal[0]][goal[1]] if dp[goal[0]][goal[1]] != inf else -1)

簡単に解説すると、マスiが書いてある座標をpoints[i]に入れていって、i=1から10まで更新していきます。

最後にDP配列のゴールの座標にアクセスしてinfのままだったら-1, それ以外ならその値を出力します。

計算量解析

最初に述べた通りあるiが書いてあるマスは最悪で\frac{NM}{9}なので、毎回それの二乗回ループを回すことになってO((NM)^ 2)になります

さいごに

めちゃくちゃ長くなってすいません

優先度付きキュー(二分ヒープ)と隣接リストを使ったダイクストラ法(Python3)

ダイクストラ法については各自参照してください。この記事では実装のみ取り扱います

螺旋本(P309~314)の「優先度付きキューを用いたダイクストラ法」の実装をしたので、それについてソースコードと一緒に書いていきます

提出リンク

実行時間 メモリ使用量 コード長
2450[ms] 90060[kb] 922[b]

ソースコード(関数部分のみ)

from heapq import heapify, heappush, heappop

inf = float("inf")
def dijkstra(graph, start):  # graphは隣接リスト
    vsize = len(graph)
    dist = [inf] * vsize  # 始点からの最短距離 
    seen = [False] * vsize
    pq = []
    heapify(pq)

    dist[start] = 0
    heappush(pq, (0, start))  # heapではtuple[0]で比較されるのでこの順番で追加する
    while pq:
        cost, u = heappop(pq)
        seen[u] = True
        if dist[u] < cost:
            continue
        for v, w in graph[u]:
            temp_cost = dist[u] + w
            if not seen[v] and temp_cost < dist[v]:
                    dist[v] = temp_cost
                    heappush(pq, (dist[v], v))
    return dist

計算量

Pythonのheapqの実装は二分ヒープらしいので、Wikipediaを参考にすると、O((E+V)logV)のようです。

経路復元

必要になりそうなのでそのうち書きます

最短全域木を根に向かって追っていけばよさそう？

2020/2/25バチャ反省

バチャリンク

緑問題解けるようになろうと思って緑問題を4問選んでやってみました。
nabefutaとSatoooonくんと3人でやったんですけど、なんとびっくり三人とも30~35分で全完でした

f:id:nanigasi_san:20200225191837p:plain
順位表

思ったよりだいぶ解けてびっくりしましたね。ペナありならビリですけど

解説を書いていきます

1問目 互除法

f:id:nanigasi_san:20200225192036p:plain

考察A

フィボナッチ数列を使います。

なぜフィボナッチ数列がこれに使えるのかというと、問題文にあるコードの

int gcd(int a, int b) {
    if (b == 0) return a;
    counter++;
    return gcd(b, a%b);

の部分に理由があります。

以下では実装と同じ目線で話すために0-indexedを採用しています

フィボナッチ数列を数列Fと置いた際に、gcd(F_i, F_(i-1))の挙動は以下のようになります。

  1. F_(i-1)が0の時：終了します。counterの値は増えません
  2. F_(i-1)が1の時：gcd(1, 0)が呼ばれます。counterの値は1増えます
  3. F_(i-1)が2以上の時：gcd(F_(i-1), F_(i-2))が呼ばれます(これの証明は、F_i % F_(i-1)がこの二つの差分(つまりF_(i-2))に等しくなるからです。フィボナッチ数列はその定義より一項前の倍を超える値になることがなく、この性質が使えます)。counterの値は1増えます。
  4. なお、gcd(F_i, F_(i+1)) [i>1]が呼ばれた際は、a, bが入れ替わってgcd(F_(i+1), F_i)が呼ばれます。(この性質により二通りの答えが生まれます)

考察B(公式想定解)

さて、挙動3について考えていきます。 gcd(F_i, F_(i-1))を呼んだとき、gcd(F_(i-1), F_(i-2))が呼ばれるわけですが、これはi>2のどのiから始めてもgcd(F_2, F_1)であるgcd(2, 1)になります。

ここで、

  1. gcd(2, 1)はcounterを1増やし関数を終了させる
  2. gcd(F_i, F_(i-1))がgcd(F_2, F_1)にたどり着くまでにcounterはi-2増える

の二点より、gcd(F_i, F_(i-1)) [i>2]が終了した時点で、counterはi-1であることがわかります。

よって、counterをKにするには

gcd(F_(K+1), F_K)

を呼べばいいことがわかります。
即ち、

a=F_(K+1), b = F_K

です。

考察C(別解)

挙動4を使うともう一つの解が見つかります。それは

a = F_(K-1), b = F_K

なのですが、これは挙動4より最初にa, bの反転が起こりcounterが増加、そこから考察Bの通りK-1増加するので全体でK増加する、ということです。

これだとK=1の時に考察Bのi>2(i-1>1)を破りますが、挙動2よりbが1の時はaに依存せず1回で終わるので、問題ありません。

実装(考察Cを採用)

fib = [1, 1]
for i in range(50):
    fib.append(fib[-1]+fib[-2])
K = int(input())
print(fib[K-1], fib[K])

2問目 Insertion

f:id:nanigasi_san:20200225230237p:plain

考察

まず、辞書順で小さいということがどうかを考えます。(と)では(のほうが小さいので、(ができるだけ先に、)ができるだけ後に来るようにすればよいです。 これはまぁ簡単で、以下の流れで最適解が出ます。

  1. Sを左から見ていく
  2. (があったら変数rに1足す
  3. )があったら、
    1. rが1以上の場合：rを一つ減らす(括弧の対応付け)
    2. rが0の場合：先頭に(を追加(括弧の対応を無理やり生やす)
  4. さいごにrの数だけ)を配列の最後に追加

するだけです。これで括弧の対応を守ったまま(を最初に、)を最後に持っていくことができました。

実装

N = int(input())
S = list(input())
stack = []
ans = S[::1]
r = 0
for c in S:
    if c == "(":
        r += 1
    if c == ")":
        if r > 0:
            r -= 1
        else:
            ans.insert(0, "(")
for _ in range(r):
    ans.append(")")
print("".join(ans))

3問目 引越しできるかな？

f:id:nanigasi_san:20200225232029p:plain

考察

今城くんが注文しなければならないダンボールの容積の最小値はいくらでしょうか

という部分から、最適な選択したときに必要となる箱の体積を求めればいいことがわかります。

これは各箱を最適に重ね合わせるときの各軸(x, y, z)の最大値の積であることがわかります(イメージをすると自明だと思います)

では、「最適に重ね合わせる」がどういうことかを考えていきます。

これは、「ソートしてから各軸に対応させたindexに応じて値を更新していく」という風に表せます。具体的には、

  1. x軸に1番目に大きいものを
  2. y軸に2番目に大きいものを
  3. z軸に3番目に大きいものを

という風にしていくことです。何故これが最適かというと、数式での証明が浮かびません。どうしましょう

良いたとえを思いつきました。

例えば箱の中にたくさんの積み木があるとして、それらすべてを十分な時間揺らした場合、それらは最初の乱雑な状態より小さい体積に収まっています。

それと同じで、今回の場合はx > y > zの順に安定するようにする、と考えます。

実装

C = int(input())
a, b, c = 0, 0, 0
for _ in range(C):
    N, M, L = sorted(list(map(int, input().split())))
    a = max(a, N)
    b = max(b, M)
    c = max(c, L)
print(a*b*c)

4問目Digits in Multiplication

f:id:nanigasi_san:20200226001224p:plain

考察

2つの正の整数の組(A, B)がN=A*Bを満たすように動くとき

回りくどい言い方をされていますが、これはつまりNの約数A, Bのペアということです。

つまり、Nの約数のペア全通りについて関数Fを計算し、最小値を出力すればよいです。

Nの約数のペアを求める

一瞬O(N)に見えますが、約数のペアは約数iについてN//iでだせるので、sqrt(N)まで探索すればよく、O(sqrt(N))になります。

今回はN = 1010までなので、最悪で105回となり間に合います。

10進数の数の桁を求める

ある10進数の整数Xについて、その桁数はint(log10(X))+1で求めることができます。

よって関数Fの実装は以下のようになります

def F(A, B):
    return max(int(log10(A))+1, int(log10(B))+1)

あとは用意したペアすべてについて計算をしながら最小値を更新していけばよいです。

実装

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append((i, n//i))

    divisors.sort()
    return divisors

from math import log10
N = int(input())
div = make_divisors(N)

def F(A, B):
    return max(int(log10(A))+1, int(log10(B))+1)
ans = 10**9
for a, b in div:
    ans = min(ans, F(a, b))
print(ans)

終わりに

疲れた～～～！！！今日のバチャは全体的に爆速でとても楽しかったです！今回の解説で一番楽しかったのは1問目の「フィボナッチ数列を使える理由」のところですね、自分で気づいて天才かと思った！！！

2020/2/23 バチャ反省

はじめに

緑上位に行きたいのでバチャを立てて参加しました。 難易度でいうと700~900の茶色上位~緑色下位です。

バチャリンク

結果

f:id:nanigasi_san:20200223203420p:plain
結果

nabefutaくんに負けました～～
2完...
1問ずつ通して解説していきます。

1問目 塗り絵

問題文

f:id:nanigasi_san:20200223233755p:plain

考察A(問題文をかみ砕く)

解説ACをしました

まず、

(x1, x2)からの距離がr以下の部分を赤く塗ります。

より、赤く塗られた部分=(x1, y1)を中心とした半径rの円であることがわかります。
次に、

x2 <= x <= x3, y2 <= y <= y3を満たす(x, y)を青く塗ります。

より、青く塗られた部分=(x2, y2), (x2, y3), (x3, y2), (x3, y3)を頂点とする長方形であることがわかります。

考察B(問題文の再把握)

考察Aより、問題文の

赤く塗られた部分と青く塗られた部分が存在するかどうかをそれぞれ判定してください。 というものが何を表しているかを考えることができます。

これはそれぞれ

  • 赤く塗られた部分がある = 円が長方形に完全に内包されていない
  • 青く塗られた部分がある = 長方形が円に完全に内包されていない

という風に言い換えることができます。なぜなら、その色がない時、もう片方の色に完全に重なっている=内包されているといえるからです。

これを踏まえて問題文を見ると、

  1. 円が長方形に完全に内包されていたらNO, それ以外ならYESを出力
  2. 長方形が円に完全に内包されていたらNO, それ以外ならYESを出力

をすればいいことがわかります。この時注意しなければならないのが、完全に内包されているかの真偽と出力のYES/NOが逆になっていることです

考察C(条件の整理)

では、どうすれば完全に内包されているかがわかるかを考えていきます。

円が長方形に完全に内包されているか

これは円のxの最大値最小値、yの最大値最小値が長方形のxの最大値最小値、yの最大値最小値に内包されているかを考えればよいです。分割して考えると、

  1. 円のxの最小値(x1-r)が長方形のxの最小値(x2)以上か
  2. 円のxの最大値(x1+r)が長方形のxの最大値(x3)以下か
  3. 円のyの最小値(y1-r)が長方形のyの最小値(y2)以上か
  4. 円のyの最大値(y1+r)が長方形のyの最大値(y3)以下か

になります。この四点だけ見ればよい理由のイメージとしては、長方形に比べて十分に小さい、長方形に完全に内包された円があるとき、それを拡大していくと最初に長方形の辺に触れるのがこの四点のどれかになるから、といった感じです。

よって、これをすべて満たしていたらNO, 一つでも満たしていなかったらYESを出力します

長方形が円に完全に内包されているか

これは長方形の各頂点が円に内包されているかを見ればよいです。理由としては上と同じで、円に比べて十分に小さい、円に完全に内包された長方形を考えると、それを拡大していくと最初に円に触れるのが各頂点のどれかだからです。

さて、ある頂点(x, y)が円に内包されているかを考えるのは、

(x, y)と(x1, x2)の距離がr以下か

と表すことができます。円は(x1, y1)からの距離がrの範囲なので、当然といえます。 なので、各頂点に対して距離を計算し、r以下かを判定すればよいです。

これをすべて満たしていたらNO, 一つでも満たしていなかったらYESを出力すればよいです。

実装

x1, y1, r = map(int, input().split())
x2, y2, x3, y3 = map(int, input().split())
if (x1 - r >= x2) and (x1 + r <= x3) and (y1 - r >= y2) and (y1 + r <= y3):
    print("NO")
else:
    print("YES")

def check_dis(x, y):
    dis = ((x - x1)**2 + (y - y1)**2)**0.5
    return dis <= r

if check_dis(x2, y2) and check_dis(x2, y3) and check_dis(x3, y2) and check_dis(x3, y3):
    print("NO")
else:
    print("YES")

2問目 □□□□□

問題文

　 高橋君は大きさ 1 メートル四方のタイルを n 枚持っています。
　高橋君はこれらのタイルのうちいくつかを、重ならないように隙間なく並べて大きな長方形を作ろうとしています。
　出来上がる長方形はできるだけ正方形に近いほうがよいですが、同時に、使わずに余るタイルの枚数ができるだけ少なくなるようにしたいと考えています。
　長方形の縦と横の長さの差の絶対値と、余ったタイルの枚数の和を最小でいくつにできるでしょうか。

考察A(雑な推理)

とりあえず、

  1. 縦と横の差分だけで見るとa*aの形が一番うれしい
  2. あまりだけで見るとa*b<=n以下の範囲でa*bが最大になる形が一番うれしい

ということがわかります。

考察B(諦め)

Aより、a*aのかたちに近く、かつa*bを最大化すればいいっぽいことがわかりました。
困りました、これ以上わかりません。

某「全探索するか～」

というわけで、sqrt(n)の周辺±1000位を全探索してみることにしました。

実装

from math import sqrt, floor
n = int(input())
ans = 10**10
for i in range(max(1, floor(sqrt(n))-1000), min(n+1, floor(sqrt(n))+1000)):
    for j in range(max(1, floor(sqrt(n))-1000), min(n+1, floor(sqrt(n))+1000)):
        if i*j <= n:
            ans = min(abs(i-j)+n-i*j, ans)
        else:
            break
print(ans)

ちゃんと通ってうれしいです。

3問目 Rain Flows into Dams

問題文

f:id:nanigasi_san:20200223230645p:plain

考察

解説ACをしました。

A_i :=ダムiにある水
X_i := 山iに振った水

降った水の総和とダムにある水の総和が等しいので、

S = A_1 + A_2 + ... + A_N = X_1 + X_2 + ... + X_N

が成り立ちます。 問題文より、

(X_i + X_(i+1)) / 2 = A_i

が成り立ち、2をかけて

X_i + X_(i+1) = 2 * A_i

になります。
Xを求めていきます。

X_1 = S - (X_2 + X_3 + ... + X_N)

ですが、

X_(n*2) + X_(n*2+1) = 2 * A_(n*2)

の性質を使うと、

X_2 + X_3 + ... + X_N =2 * (A_2 + A_4 + ... A_(N-1))

になります。この時、制約よりNは奇数なのでN-1が必ず偶数になり、式が成り立ちます。

これでX_1が求まり、同様にしていけばX_Nまで求まりますが時間計算量O(N2)かかってしまい、TLEしてしまいます。
ここで

X_i + X_(i+1) = 2 * A_i

より

X_(i+1) = 2 * A_i - X_i
X_i = 2 * A_(i-1) - X_(i-1)

の漸化式が立ち、楽に計算ができます。 これでX_2からX_NまでをO(N)で計算することができました

実装

N = int(input())
Alist = list(map(int, input().split()))
S = sum(Alist)
Xlist = [0] * N
Xlist[0] = S - 2 * sum([Alist[_] for _ in range(1, N, 2)])
print(Xlist[0], end=" ")
for i in range(1, N):
    Xlist[i] = 2*Alist[i-1] - Xlist[i-1]
    print(Xlist[i], end=" ")
print()

4問目 Binomial Coefficients

問題文

f:id:nanigasi_san:20200224004157p:plain

考察

解説ACです。
証明は以下の通りなんですが、 f:id:nanigasi_san:20200224005030p:plain 結論だけ言うと「nCrの最大化をするとき、nはalistのうち最大のもの、rはalistのうち最もn/2に近いもの」というらしいです。

これを実装していきます。 まず、nCrで考えるとnが入力と被ってしまうのでそれぞれm, ansと置きます。mは最大値をとるだけなので、固定です。alistの中から、ansを探索していくことがわかりました。

alistのうち最もa/2に近いものを探すには、差分をsbnとして、十分に大きい初期値を設定してから各aについて

abs(m/2 - a)

がsbn以下かを判定すればよく、sbn以下だったansをaに更新し、sbnをm/2- aに更新していけばよいです。

注意するべき点として、a==mの時は更新できません(i!=jなので)

実装

n = map(int, input().split())
alist = list(map(int, input().split()))
m = max(alist)
sbn = 10**10
for a in alist:
    if abs(m/2 - a) < sbn and a != m:
        ans = a
        sbn = abs(m/2 - a)
print(m, ans)

5問目 Special Trains

問題文

f:id:nanigasi_san:20200223224308p:plain

考察

駅Xからの経路を実際にシミュレーションをすればよさそうです。ある駅iから駅i+1に行く手順は共通で、以下の通りです。

  1. 今の時間がS_iより小さければ、S_iにします、大きければ、そのまま進めます
  2. now%F_i == 0なら、列車が出ます、それ以外なら、now + F_i - now % F_iまで待つ必要があります。
  3. 列車に乗るので、now + C_iまで時間が動きます。

これを繰り返すことで、移動がシミュレーションできます。 コードにすると、以下のようになります。

now = max(now, C_i)
if now % F_i != 0:
    now += F_i - F_i % now
now += C_i

後はこれを始点iからNまで、iそれぞれについてシミュレーションしていけばいいです。
この時、NからNの経路は存在しないので素直に0を出力します

実装

N = int(input())
CSFlist = [list(map(int, input().split())) for _ in range(N-1)]
def calc_time(start):
    now = 0
    for i in range(start, N-1):
        C, S, F = CSFlist[i]
        now = max(now, S)
        if now % F != 0:
            now += F - now % F
        now += C
    return now
for _ in range(N-1):
    print(calc_time(_))
print(0)

終わりに

解説記事をバチャに対して書くのは初めてなんですが、すごい勉強になって最高ですね

これからもできるだけ書いていこうと思います！

キーエンス プログラミング コンテスト 2020 参加記

2020/1/18のキーエンス プログラミング コンテスト 2020の参加記です。

ちゃんと理解して進みたいので解法とか考察を書きます。

---ここでコンテスト---

終わりました。順位表です。

f:id:nanigasi_san:20200119140517p:plain
順位表

50分AC2完で、レートは微減...ちょっと辛いです。 流れとしては

  1. Aを通す
  2. Bを見る
  3. 「あ、これ本で見たことあるな」となって実装を始める
  4. 一生通らない
  5. 順位表見たらみんなC通してるので簡単なのかな？と気づく
  6. Cがギャグだった
  7. Bは通らない

でした。

それぞれの問題をどう通したかを書いていきます。厳密性は問うことはあっても責めないでくれると嬉しいです。

A問題

ざっくり言うと「H * Wのマス目を縦横一列ずつ塗りつぶすとき、最小で何回やればNマス以上塗りつぶせるか？」という問題です。

まず、方針として「縦か横を選んでその方向だけを塗りつぶす」ということがわかります。なぜなら、最高効率で埋めるためには「被りが無い」ことが必要(多分)だからです。
よって、縦か横のどちらかを選ぶことになりますが、これはもちろん長い方を選ぶことになります。 なぜなら、その方が短い手数で埋めることができるからです。

長さXの列(または行)を選んでNマスを埋めるのに必要な手数は、ceil(N / X)で表せます。(ceilは切り上げ関数)。よって答えは以下のようになります。

H = int(input())
W = int(input())
N = int(input())
big = max(H, W)
from math import ceil
print(ceil(N / big))

B問題

日本語が弱いので問題文は自分で読んでください。
これを見たときの某「あ、これ見たことあるな、まふゆちゃんがくれた本だ」

なんか名前がついているらしくて、区間スケジュールというらしいです。
方針としては、Xでソートしてから右端を更新していけばいいです。イメージ的には、実際のエリアにロボットを一つずつ置いていくイメージです。

どういうことかというと、

  1. 与えられたX, Lをペアにしてまとめてから、Xでソートします。
  2. 右端を適当に設定します。
  3. XLをループで回していきます。
  4. その時見ているロボットの左端はX - Lです。右端はX + L + 1です。一つ前の右端が今の左端と被っていなければ(左端 > 右端)、普通に置きます(ansを1増やす)。 被っていたら、右端が小さい方に置換します。それでよい理由は後で説明します。
  5. さいごにansを出力すればよいです。

右端更新らへんの理由

  • もし後の奴のほうが右端が長い場合
    • 普通に邪魔なので置きません。右はできるだけ短い方がいいですもんね。
  • 前の奴のほうが右端が長い場合
    • この場合、右端を短くしたいのは当然として、あとの奴の左端が前の左端より必ず右側にあることがわかるので問題が無く、置換します。

コードはこれでACしました(コンテスト終わって1分後にACしました、カス)

N = int(input())
XLlist = [tuple(map(int, input().split())) for _ in range(N)]
XLlist.sort(key=lambda x: x[0])
ans = 1
x, l = XLlist[0]
rl = x + (l - 1)
for x, l in XLlist:
    ll = x - l
    if ll <= rl:
        rl = min(rl, x + l - 1)
    else:
        ans += 1
        rl = x + l - 1

print(ans)

C問題

草

二つの和にする必要はありません、SをK個用意して、それ以外は適当に埋めればよいです。ちなみにS + 1とかS - 1にすると10**9, 1で落ちるので、適当に処理してください(値を決めてもよいし、modをとってもよさそうです)

N, K, S = map(int, input().split())
ans = [str(ele) for ele in ([S] * K + [(S - 1) if S != 1 else 10**9] * (N - K))]
print(" ".join(ans))

感想

いや悔しい

Bは見えたのに< と <=で通らなかったのは本当につらい

今からABCがあるので頑張ります！

インターンに行った―ン！(強打)

インターンに行ったーんよ。

8/26~9/7までの13(素数)日間、岐阜にある核融合研究所(NIFS)でインターンをしてきました。
疲れた

今は成果発表会が終わって、避難訓練をしてきたところです。暑い

これは何を書くか

体験入学までは書きましたが、インターンでやったこともそれの発展なのでツイートを追って何があったかだけ適当にまとめて寝ます。寝たいんだ

体験入学のブログはここでーす、こっここっこ－！
長いので読んで

注意

ツイートがほとんどなので、いいねとかすると戻っちゃうのでこれをブラウザで開いて読んだほうがいいです

以下適当まとめ(あふぃ)

8/30(体験入学最終日)

いやマジでこれ楽しいからほんとにこれ楽しいよ
昼休みとかにいきなり「さぁ始まりましたバルストス世界選手権決勝！！！この世界のトップまで駆け抜けてきたのはこの男ォ！某～！！！！」とか言い出していきなり世界選手権決勝(初戦)が始まったり次の日には銀河系最強を決めるとか言ってやってたりした。
俺の反射神経はこのゲームが育てたといっても過言ではない。バルストス！

写真撮ってもらったので貼りました。

サチロボの査読が来てたので流れで萌えボイス収録してもらおうと思ったけどダメでした。
今度メロンパンとかで釣ってツンデレボイスが手に入る予定です(わーい)

この日で体験入学終わりだったので一人でパーティしてた。虚無

草

草。頑張れ俺

みんな違ってみんな草

サチが唐突に超有名おねショタ本をリプしてきて本気でビビりました。エロ漫画とは知らなかったらしい

自分のツイートまとめてるみたいで悲しくなってきた

これは自伝です。書いていてつらくなったので書ききれなかった。書いてあるようなことばっか考えてるので女の子と仲良くなれない

ここらへんで日が変わった

8/31(体験入学最終日の次の日=土曜日)

モバイルバッテリー適当に扱ってたらケーブルが壊れてiPhoneが充電できない事態に。
さすがに死ぬので一週間修行していた山を(徒歩で)降りて人里に向かいました

うるせぇさっさと行け

🐒 🐒 えっちょっとやだ....キレイ....（さっさと買いに行け） この後ファミマに行ったらあったので普通に買いました

こしょ攻め？こっしょりこしょこしょ！

これは言葉に敏感な男

これはギフケルベロス
学名は確かはNanka-atta-hana

で、宿に帰ってきました

これは意味わからん。前後のツイートに田中出てきてないからなんかあったのかもな。誰だか知らんが。
田中のバーカ！

このあと鬼滅の刃見はじめたら面白すぎて日が変わってた。

9/1

気づいたら青春の八月は終わって九月に。彼女できないどころかあった女子がサチとぽっぽさん(部活)しか浮かばない。というかプライベートで外に出た記憶もない。あれ、おれ、なにえお .
.
.
.
.
.
.
.
.
.
.
とか言ってたらかんたろうがマイクラやろうぜ！とか言ってきたのでバイトのメンバーでマイクラが開始。一時間くらいやったところで通話でバイトの話とか人生の話とか苦手なツイッタラーとか裏垢界隈の話をしてました。久しぶりに色々話した。

終盤は俺が推してるエロ同人の批評会が始まった

ワイがワイワイしてる間に朝の三時で草

--ここらへんで寝落ち--

起床。三食くらいほとんど食べて無くて足が減り始めた(俺はおなかに脂肪が全くないので減るとしたら足くらいしかない)

強く生きるには自分を見失わない心が必要

誰もいなくなったロビーで一人ノスタルジックになってた。
まぁ、正直人がいるときは「お前ら体験入学で女子をナンパすんのやめろセックスすんならさっさと部屋いけ」とか思ってたけどな

アイス食べてからウキウキで温泉に行きました

--ここらへんで死ぬ--

マジで電気風呂ヤバい

よくゲームである「バインド！」みたいな束縛魔法あるじゃん？あれ
まじで体が締め付けられて呼吸が止まるし、体が動かなくなるから抜けられない。すとんりばーさんに人体の説明聴きながら何が起こってたかを考察して、リベンジを誓ってご飯食べに行った。(リベンジの話は9/5を見て)

はいどーん(丼)

気づいたら帰宿

来ませんでした

寝ました。

9/2

起きました

初日から朝ごはんがなくて泣いた(これは言ってくれなかった研究所を恨む)

のでコンビ二に行きました。

でまぁインターン(広義)が始まりました。
先週までは先生がずっといたんですが、なんかいなくなりました。

そうですね、一日に15~30分くらい来て、あとはずっと一人で研究してた

Pythonがグラフ作成で活きましたね。あとデータの管理と簡易計算はExcelが便利。実験する人はExcel慣れたほうがいい

まずは人間になろうな

たくさんツイートしていましたがシミュレーション中に呟いてたので進捗はしっかり出ていました。

とかやってるうちに定時が来たので帰りました

この日はYouTubeでピアノの動画とかヨルシカ(最近好きになってきている)を聴いていたら朝で寝た。

9/3

毎朝１人でつらかった

どうせ話してもうまく説明できないし興味ないだろうしググってもヒットしないので内容は深く言いませんが、buneman instabilityというのをやった。進捗なし

コンビニで一人で慰めてた。大丈夫、明日はきっとうまくいくよ

まぁじに「眼鏡っ娘について書いてよ」といわれたのでブログを書きました。

めっちゃ反響が(身内で)あって、書いた甲斐があるなぁと思いました。ここまで読んでるような人はかなりの暇人だと思うので進む前に読んでください。1分で読めるので

読んだ？どうせ読まずにこれ見てるだろてか1行下だしな見えるよな。

めっちゃ読まれて、固定にしてた記事を一瞬で越えた

まぁじに「醤油について書いて」って言われたのでブログを書きました。

いなみちゃんさんに「天才」といわれてフォローされました。天才なのかもしれん。この二個のブログは気に入ってるから読んでくれ同じく1分で読める

面白くもない長い文章読んでて飽きない？書いてる方も飽きてきてる

9/4

なんでこんなにギャグセンスがあるんだろうね。gift(独.毒)だ

--研究を頑張った--

--夜が来た--

そろそろ飽きてきました。今自分のツイートを日付で検索して(多すぎるので普通にプロフィールを見ても出てこない)打ってるんですが、RTが出てこないから微妙
まぁもう少しだよ この日の議題は女子とのかかわり方。 ちょっｗオタク殿～w氏呼びでござるかwww これはただの天才

唐突にMomoko_さんなりすまししたりしてた(無理でした)

9/5

この日は9/6の成果発表会に向けたスライド制作

朝からアホ

Ctrl+Shift押しながらホイール回すとターミナルが透明になった

大体データがそろったのでスライド制作開始

OCのスタッフなのでTシャツゲット
めっちゃうれしかった

天才的なネタフリ、俺じゃなきゃ見逃しちゃうね

違いました

顎を破壊したりしましたがおおむね平和的に温泉に向かいました。

おいバカ学べ

ばかだ.....

晩御飯の用意の中で悟りを開き

理由もなくデブ活をしました、

9/6

で、練習して時間が近づいてきました。

机の下でスマホ触ってたからだれか呼んでくれたのかもしれん。 体験入学/インターン担当してくれた先生が三人、それ以外が１人なので聞きに来てくれた方は1名です。 まぁ無事終わりました。

もう書くことが無いですね、この後避難訓練と明日のオープンキャンパスの手伝いの内容確認していま研究室でこれを書いています。時間が俺に追いついた。

明日はインターンって感じではないのでブログはここまでとします！終わり！楽しかった！

終わりに

来年もきたいけど金がない