d_tail's blog

備忘や記録

トップ > プログラミング

【精進記録】AtCoder Regular Contest 091 C - Flip,Flip, and Flip......

AtCoder プログラミング

問題

beta.atcoder.jp

解法

解法を思いつくまでにそこそこ時間がかかった&コーナーケースで躓いたけどなんとか解説を見ずに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の場合の条件も書いてしまった．

図示して検討したパターン

f:id:d_tail:20181103164338p:plain

コード

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が用いられている
    • L2を伴う学習はPSNR及びSSMIに関して他の関数より良いことを保証するものではないということが報告されている

手法

  • より単純なResNet構造による拡張バージョンを提案
  • 元のネットワークより計算効率が向上

Residual blocks

SRResNetはResNetを利用することに成功したが，より良いResNet構造を採用することによってさらに性能を向上させる

  • batch normalization layersを削除
    • batch normalization layersはネットワークから範囲の柔軟性を取り除いてしまう
    • GPU使用量を減らせる
  • 畳み込み層の後にスケーリングレイヤーを設置
    • 多数のフィルタを使用する場合に学習を大幅に安定させる
  • SRResNetと同様に外側にReLU活性化層を持たない

f:id:d_tail:20181102164305p:plain

シングルスケールのモデル(EDSR)

  • モデルのパフォーマンスを向上させる最も簡単な方法はパラメータを増やすこと
  • B:層の数，F:特徴チャンネルの数
  • O(BF2)パラメータでおおよそO(BF)メモリを消費するのでBの代わりにFを増やすとモデル容量を最大にできる
  • あるレベル以上の特徴マップの数を増やすと学習が不安定になる
    • residual scalingを0.1で採用することで解決
  • ベースラインモデルではF=64しかないためスケーリングレイヤがない
  • 最終的なモデルではB=32，F=256，スケーリング係数0.1とした

f:id:d_tail:20181102165549p:plain

マルチスケールのモデル(MDSR)

f:id:d_tail:20181102165623p:plain

参考

www.slideshare.net

musyoku.github.io

hi-king.hatenablog.com

qiita.com

letslearnai.com

【精進記録】AtCoder Beginner Contest 092 C - Traveling Plan

AtCoder プログラミング

問題

beta.atcoder.jp

解法

しばらく考えて解けなかったので解説を見てAC．

本来の計画の総コストを計算し，取りやめた地点iについて，地点i-1からiへ向かうコストとiから地点i+1へ向かうコストを引いた後に，地点i-1からi+1へのコストを足せば良い．

入力例1のi=2の場合を図示して見た．

f:id:d_tail:20181101202444j:plain

f:id:d_tail:20181101202451j:plain

コード

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]))

コメント

難しく考えすぎていたのがよくなかった．
単純にできる方法から順に考えていくように気をつけたい．

とりあえず数式で考えたり図示するとわかりやすくなりそう．

【Git】個人的によく使う基本的なGitコマンド/参考サイトまとめ

プログラミング Git メモ
  • はじめに
  • Gitコマンド
    • git add
    • git commit
    • git push
    • git branch / git checkout
  • 参考サイト

はじめに

以前からGit自体はソースコードの管理のために使用していましたが，ほとんどの場合GUIでGitを扱うことができるようになるSourcetreeを用いていました．

しかし，最近はGUIを使えない環境でGitを使用する機会が増えたため，Gitコマンドを扱う必要がある場面が多くなってきました．

Gitコマンドはまだうろ覚えなので使う際には調べる必要があるのですが，その際に毎回ググるのも大変なので，個人的によく使用する基本的なGitコマンドや参考にするサイトをまとめておきたいと思います．

続きを読む