【参加記録】AtCoder Beginner Contest 113
はじめに
AtCoder Beginner Contest 113に参加した記録です.
A - Discount Fare
X + Y/2を出力すれば良い.
A問題でしたが,制約をちゃんと見ていなかったのは気をつけたいです.
X,Y = map(int,input().split()) print(X + int(Y/2))
B - Palace
T−H[i]*0.006を計算してAとの差の絶対値が最小になるiを求めれば良い.
計算結果をintでキャストしたものを提出してしまったため1WA.
焦りすぎたせいで提出までに少し時間がかかってしまったのも反省点.
N = int(input()) T,A = map(int,input().split()) H = [int(i) for i in input().split()] res = - 1 res_val = 100000 for i in range(N): av_temp = T - H[i] * 0.006 if res_val > abs(av_temp - A): res = i res_val = abs(av_temp - A) print(res+1)
C - ID
入力のPとYの組み合わせに市の番号を追加したものをソートしたり,県ごとに何回市が存在したかをカウントしていくリストを作成したりして解きました.
解法はそこそこで思いつけましたが,Pythonはリスト関係の処理が遅いらしいため,どのように書くか迷って時間を潰してしまいました.(そもそもappendを多用してるのが悪そう)
N,M = map(int,input().split()) PY = [] tmp = [] cheker = [] res = [] for i in range(M): tmp = list(map(int,input().split())) tmp.append(i) PY.append(list(tmp)) res.append('') sorted_py = sorted(PY, key=lambda x: x[1]) checker = [0 for i in range(N)] for i in range(M): index = sorted_py[i][0]-1 checker[index] += 1 res[sorted_py[i][2]] = str(sorted_py[i][0]).zfill(6) + str(checker[sorted_py[i][0]-1]).zfill(6) for i in range(M): print(res[i])
D - Number of Amidakuji
手付かず.
コメント
C問題がなんとか解けて良かったです.
次回もC問題が解ければレートが緑になる可能性があるので頑張りたいところです.
【精進記録】AtCoder Beginner Contest 066 C - pushpush
問題
解法
TLEしか出せなかったので解説を見てAC.
最初に追加した要素ほど数列の中央側になっていくので,要素のindexの偶奇に気をつけて数列の前と後ろに交互に要素を追加していけば良い.
解法自体は思いついたが単純にPythonのリストに対してappend()で後ろに追加,insert()で先頭に追加,という方法をしていたのがよくなかった.
特にinsertは計算量がO(n)なので遅いらしい.
参考:
解説を見たところ,C++の場合はdequeというライブラリを使うと簡単にできると記されていたので,Pythonにも存在するか調べたところ,collectionモジュールにdequeが含まれていたのでこれを利用しました.
insert()の代わりにdequeのappendleft()を使えば計算量がO(1)になるようです.
コード
from collections import deque N = int(input()) A = [int(i) for i in input().split()] B = deque(maxlen=2*10**5) if N % 2 == 0: for i in range(N): if i % 2 == 0: B.append(A[i]) else: B.appendleft(A[i]) else: for i in range(N): if i % 2 == 0: B.appendleft(A[i]) else: B.append(A[i]) print(*B)
Submission #3525231 - AtCoder Beginner Contest 066
コメント
dequeの存在を知れたのが良かった.
標準ライブラリに含まれているデータ構造などは調べておいたほうが良さそう.
加えて,問題を解いて練習するのと同時にそろそろアルゴリズムとデータ構造についても少しづつ練習していく必要がありそう.
【精進記録】AtCoder Regular Contest 091 C - Flip,Flip, and Flip......
問題
解法
解法を思いつくまでにそこそこ時間がかかった&コーナーケースで躓いたけどなんとか解説を見ずにAC.
N = 1かつM = 1 の場合は1,N = 1 かつM ≠ 1の場合は(M-2),M = 1かつN ≠ 1の場合は(N-2)となる.
この場合以外のN ≧ 2 かつM ≧ 2の場合,裏返す回数を数えると四隅が4回,四隅を除く辺部分が6回,それ以外のカードは9回裏返されることになるため,9回裏返されるカードの数を数えれば良い.
9回裏返される部分は外周以外のカードなので,(N-2)*(M-2)となる.
裏返す回数を図示してみることで解法に気づくことができた.
ただ,提出したコードでは無駄にN = 2またはM = 2の場合の条件も書いてしまった.
図示して検討したパターン
コード
N,M = map(int,input().split()) if N == 2 or M == 2: print(0) exit() if N == 1: if M == 1: print(1) else: print(M-2) exit() if M == 1: print(N-2) exit() print((N-2)*(M-2))
コメント
前回の問題でも思ったが,わからない場合はとにかく図示してみるのが有効そう.
【論文・文献メモ】Enhanced Deep Residual Networks for Single Image Super-Resolution【EDSR】
はじめに
大雑把に読んだ際のメモとなっているのでMDSRや実験内容についてなど端折っている部分が多いです.
また,Google翻訳に頼りまくっている&知識不足による誤りがある可能性がかなり大きいです.
論文
[1707.02921] Enhanced Deep Residual Networks for Single Image Super-Resolution
概要
一枚の低解像度画像から高解像度画像を生成する単画像超解像手法についての論文.
NTIRE2017 Super-Resolution Challengeで優勝した手法.
従来のResNet構造の不要なモジュールを排除して最適化をおこなった.
特定のスケールの超解像を行うEDSRと単一モデルで様々な高解像度画像を生成するMDSRを提案.
関連研究
- 多くの深層学習による超解像では入力画像はネットワークに入力する前にバイキュービック補間によってアップサンプリングされる
- 補間されたものを入力するのではなくネットワークの最後にアップサンプリングモジュールを使用することもできる
- 特徴サイズが減少するため計算量を削減できる
- しかし,VDSRのように単一のフレームワークでマルチスケールの問題に対処できない
- 本研究ではマルチスケール学習の計算効率のジレンマを解決する
- 一般的な画像修復には損失関数にMSE,L2 lossが用いられている
手法
- より単純なResNet構造による拡張バージョンを提案
- 元のネットワークより計算効率が向上
Residual blocks
SRResNetはResNetを利用することに成功したが,より良いResNet構造を採用することによってさらに性能を向上させる
- batch normalization layersを削除
- batch normalization layersはネットワークから範囲の柔軟性を取り除いてしまう
- GPU使用量を減らせる
- 畳み込み層の後にスケーリングレイヤーを設置
- 多数のフィルタを使用する場合に学習を大幅に安定させる
- SRResNetと同様に外側にReLU活性化層を持たない
シングルスケールのモデル(EDSR)
- モデルのパフォーマンスを向上させる最も簡単な方法はパラメータを増やすこと
- B:層の数,F:特徴チャンネルの数
- O(BF2)パラメータでおおよそO(BF)メモリを消費するのでBの代わりにFを増やすとモデル容量を最大にできる
- あるレベル以上の特徴マップの数を増やすと学習が不安定になる
- residual scalingを0.1で採用することで解決
- ベースラインモデルではF=64しかないためスケーリングレイヤがない
- 最終的なモデルではB=32,F=256,スケーリング係数0.1とした
マルチスケールのモデル(MDSR)
参考
www.slideshare.net