【精進記録】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 の場合は１，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
【精進記録】AtCoder Beginner Contest 092 C - Traveling Plan
問題
解法
しばらく考えて解けなかったので解説を見てAC．
本来の計画の総コストを計算し，取りやめた地点iについて，地点i-1からiへ向かうコストとiから地点i+1へ向かうコストを引いた後に，地点i-1からi+1へのコストを足せば良い．
入力例1のi=2の場合を図示して見た．
コード
N = int(input()) A = [int(i) for i in input().split()] A.insert(0,0) A.append(0) S = 0 for i in range(1,N+2): S += abs(A[i]-A[i-1]) for i in range(1,N+1): print(S + abs(A[i-1]-A[i+1]) - abs(A[i-1]-A[i]) - abs(A[i]-A[i+1]))
コメント
難しく考えすぎていたのがよくなかった．
単純にできる方法から順に考えていくように気をつけたい．
とりあえず数式で考えたり図示するとわかりやすくなりそう．
